9

Ich versuche, eine kleine funktionale Programmierbibliothek für Java zu erstellen (nur um mein eigenes Jucken zu kratzen). Bei der Definition der für List s, Set s und Map s habe ich auf dieses Problem gestoßen: Die Funktionen, die eine Sammlung nehmen und eine Sammlung des gleichen Typs zurückgeben, haben fast die gleiche Implementierung, und müssen für jeden neu definiert werden Datenstruktur - List s, Set s und Map s.Entfernen von Code-Duplizierung

Zum Beispiel, hier ist die Umsetzung der map Funktion für List s und Set s:

public static <A, B> List<B> map(
    List<? extends A> xs, 
    Func1<? super A, ? extends B> transformer 
) { 
    List<B> ys = new ArrayList<B>(); 
    for(A a : xs) { 
    ys.add(transformer.apply(a)); 
    } 
    return ys; 
} 

public static <A, B> Set<B> map(
    Set<? extends A> xs, 
    Func1<? super A, ? extends B> transformer 
) { 
    Set<B> ys = new HashSet<B>(); 
    for(A a : xs) { 
    ys.add(transformer.apply(a)); 
    } 
    return ys; 
} 

A filter Funktion:

public static <A> List<A> filter(
    List<? extends A> xs, 
    Func1<? super A, Boolean> predicate 
) { 
    List<A> ys = new ArrayList<A>(); 
    for(A a : xs) { 
    if(predicate.apply(a)) { 
     ys.add(a); 
    } 
    } 
    return ys; 
} 

public static <A> Set<A> filter(
    Set<? extends A> xs, 
    Func1<? super A, Boolean> predicate 
) { 
    Set<A> ys = new HashSet<A>(); 
    for(A a : xs) { 
    if(predicate.apply(a)) { 
     ys.add(a); 
    } 
    } 
    return ys; 
} 

Wie aus diesem Beispiel zu sehen sind, der Körper der Implementierungen für Set und List sind fast gleich.

Es gibt viele viele Funktionen wie map und filter in meiner Bibliothek, und jeder von denen definiert ist dreimal für jede Art von Sammlungen mich interessiert (das heißt List, Set und Map). Dies führt zu viel Code-Duplikation und Code-Geruch. Ich wollte wissen, ob es einen Weg in Java gibt, der mir helfen würde, die gesamte Code-Duplizierung zu vermeiden.

Jede Hilfe wird sehr geschätzt. Vielen Dank.

EDIT:

Func1 ist eine Schnittstelle wie folgt definiert:

interface Func1<A, B> { 
    public B apply(A a); 
} 
+0

Es sieht so aus, als könnten Sie einfach die 'Collection'-Schnittstelle verwenden, um separate Fälle für die' List'- und 'Set'-Schnittstellen zu eliminieren. –

+0

@Bears: Das Problem ist das: 'map' für' List' sollte eine 'List' zurückgeben,' map' für 'Set' sollte ein' Set' usw. zurückgeben –

+0

Also implementieren Sie für 'Collection' mit dem' List' oder 'Set' als Argument und rufen Sie diese Implementierung aus Ihren' List' und 'Set' Komfortklassen auf. – rsp

Antwort

4

Java nicht höhere Ordnung Polymorphismus hat (auch bekannt als höhere Arten), so die ist innerhalb des Typsystems nicht möglich. Viele Java-Programmierer greifen auf XML und/oder Reflektion zurück (d.h. entgehen dem Typsystem), um diesen Mangel zu beheben.

Scala kann damit umgehen und was Sie beschreiben, nennt man einen kovarianten Funktor. Dieser ziemlich grundlegende Datentyp wurde (zusammen mit vielem mehr) in der Scalaz-Bibliothek implementiert und enthält Implementierungen für java.util. *.

Weiter gibt es viel mehr kovariante Funktoren, die keine Sammlungen und viele weitere Funktoren sind, die nicht kovariant sind.

Sie können für "20 Intermediate Scala Übungen" googlen, wenn Sie dieses spezielle Konzept weiter erkunden möchten.

1

effektiv eine Liste nur eine Monade für einen Typen ist T, ihm die Fähigkeit zu geben, mehrere Instanzen des Typs zu speichern. Deshalb gelten hier alle üblichen Monaden-Gesetze, so dass Sie alle Operationen mit einem bind und return Mitglied implementieren können.

Es tut mir leid, ich habe nicht die Zeit, für jetzt weiter zu erklären, aber im .NET Raum haben wir SelectMany und Enumerable.Repeat (1, Element) für die gleichen Zwecke. Dazu gibt es viele Informationen.

Jeder Operator (z. B. filter in Ihrem Beispiel) kann mit SelectMay bzw. bind implementiert werden.

+0

Danke für die Antwort Johannes, aber ich verwende hier keine funktionalen Datenstrukturen. 'List' und' Set' in meinen Beispielen sind 'java.util.List' bzw.' java.util.Set'. –

+0

sicher, aber diese implementieren etwas wie IEnumerable oder ICollection (die Sammlung Monad in diesem Fall) –

+0

Können Sie bitte etwas Code hinzufügen, um Ihren Standpunkt zu erklären? –

6
public static <A, B> List<B> map(
    List<? extends A> xs, 
    Func1<? super A, ? extends B> transformer 
) { 
    List<B> ys = new ArrayList<B>(); 
    map(xy, transformer, ys); 
    return ys; 
} 

public static <A, B> Set<B> map(
    Set<? extends A> xs, 
    Func1<? super A, ? extends B> transformer 
) { 
    Set<B> ys = new HashSet<B>(); 
    map(xy, transformer, ys); 
    return ys; 
} 
private static <A, B> map(
    Collection<? extends A> xs, 
    Func1<? super A, ? extends B> transformer, 
    Iterable<B> ys 
) { 
    for(A a : xs) { 
    ys.add(transformer.apply(a)); 
    } 
} 

Arbeit erledigt.

Hinweis: Es ist typisch für Java-APIs, die Mutable der Auflistung zu übergeben, anstatt eine neue in der Methode zu erstellen. Persönlich bin ich kein Fan von Mutabilität auf der Sammlungsebene, aber es ist, womit wir arbeiten müssen (in Java).

(Ich bin nicht scharf auf A und B als generische Parameter mit dieser Art von Sachen.

)

Oder Sie könnten eine Fabrik benutzen.

public static <A, B> List<B> map(
    List<? extends A> xs, 
    Func1<? super A, ? extends B> transformer 
) { 
    return map(xs, transformer, new CollectionFactory<B, List<B>>() { 
     public List<B> create() { return new ArrayList<B>(); } 
    }); 
} 

public static <A, B> Set<B> map(
    Set<? extends A> xs, 
    Func1<? super A, ? extends B> transformer 
) { 
    return map(xs, transformer, new CollectionFactory<B, Set<B>>() { 
     public Set<B> create() { return new HashSet<B>(); } 
    }); 
} 

private interface CollectionFactory<E, C extends Collection<E>> { 
    C create(); 
} 

private static <A, B, C extends Collection<B>> C map(
    Iterable<? extends A> xs, 
    Func1<? super A, ? extends B> transformer, 
    CollectionFactory<B, C> factory 
) { 
    C ys = factory.create(); 
    for(A a : xs) { 
    ys.add(transformer.apply(a)); 
    } 
    return ys; 
} 

(Wenn du mit dem sinnlosen Wortschwall von anonymen inneren Klassen setzen kann)

Wenn es nicht für Collection dann würden Sie müssen einige (hässlich) Adapter setzen

Der Vollständigkeit (wenn auch nicht getestet, mit ein paar Veränderungen machen könnte), eine unangenehme Lösung unter Verwendung von Vererbung.

Set<String> strs = hashSets().map(things, formatter); 

... 

public static <E> Functions<E, Set<E>> hashSets() { 
    return new Functions<E, Set<E>>() { 
     protected Set<E> createCollections() { 
      return new HashSet<E>(); 
     } 
    }; 
} 

public abstract class Functions<E, C extends Collection<E>> { 
    protected abstract C createCollection(); 

    public <S> C map(
     Set<? extends S> xs, 
     Func1<? super S, ? extends E> transformer 
    ) { 
     C ys = createCollection(); 
     for(S a : xs) { 
     ys.add(transformer.apply(a)); 
     } 
     return ys; 
    } 

    public <S> C filter(
     List<? extends S> xs, 
     Func1<? super S, Boolean> predicate // Predicate<? super S> might be nicer!! 
    ) { 
     C ys = createCollection(); 
     for(A a : xs) { 
     if(predicate.apply(a)) { 
      ys.add(a); 
     } 
     } 
     return ys; 
    } 
} 
+0

Die API ist die gleiche, die neue Kartenmethode ist privat –

+0

Es ist immer noch eine Menge Code-Duplizierung. Für jede neue Methode, die ich hinzufügen möchte, müsste ich die private Implementierung mit 'Collections' schreiben und dann eine bequeme Methode für jeden Datentyp. Komm schon, es muss einen besseren Weg geben, dies zu tun. :( –

+0

@ one-zero-zero-one Sie würden eine Methode mit dem gemeinsamen Code und eine Methode benötigen, die entscheidet, welche Implementierung zu verwenden, ja. Sie könnten einfach die Implementierungsmethode verwenden. Sie könnten Vererbung verwenden, aber für diese Art von statische Methoden, würde ich das als unangenehm bezeichnen –

2

Ich glaube nicht, dass das Java-Typ-System hochentwickelt genug ist, um dies anzugehen, aber Scala ist es. Mit der 2.8-Version der Sammlungsbibliothek wurde ein System erstellt, mit dem automatisch eine Sammlung des entsprechenden Typs basierend auf der Sammlung erstellt wird, mit der Sie arbeiten. Wenn Sie also filter unter List aufrufen, wird eine neue List zurückgegeben. Rufen Sie filter auf einem Set und Sie erhalten eine Set zurück. Es tut dies, während es immer noch nur eine einzige Implementierung von filter gibt.

Um mehr zu erfahren, werfen Sie einen Blick auf Traversable und die Sachen, die es verwendet. Ich glaube, dass CanBuildFrom viel von der Magie passiert.

4

Ich glaube nicht, dass Sie besser als das tun können, was Tom in his answer vorgeschlagen hat. Java unterstützt keine höherwertigen Typen - eine Funktion, mit der Sie den Sammlertyp abstrahieren können und somit vermeiden, dass für jeden Sammlungssatz derselbe Code dupliziert wird.

Scala unterstützt diese Funktion und wird in der Standardbibliothek häufig verwendet. This paper von Adriaan Moors diskutiert, wie Scala diese Art der Code-Duplizierung mit Hilfe von höher-kinded Typen vermeidet.

Zwei Screenshots aus dem oben erwähnten Papier:


alt text


alt text

+2

Einverstanden Tom (oben) ist falsch. –