Suppression de la duplication de code

Question

J'essaye de créer une petite bibliothèque de programmation fonctionnelle pour Java (juste pour gratter ma propre démangeaison). Tout en définissant le higher-order functions pours, Set s et Map s j'ai rencontré ce problème: Les fonctions qui prennent une collection, et retournent une collection de même type ont presque la même mise en œuvre, et doivent encore être redéfinies pour chacun des structure de données - List s, Set s, et Map s.

Par exemple, voici la mise en œuvre de map fonction pour List s, et 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; 
} 

fonction filter:

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; 
} 

Comme on peut le voir dans cet exemple, les corps des implémentations pour Set et List sont presque les mêmes.

Il y a beaucoup de nombreuses fonctions comme map et filter dans ma bibliothèque, et chacun de ceux-ci est défini trois fois pour chaque type de collections que je suis intéressé par (à savoir List, Set et Map). Cela conduit à beaucoup de duplication de code, et l'odeur du code. Je voulais savoir s'il y avait un moyen en Java de m'aider à éviter toute duplication de code.

Toute aide sera grandement appréciée. Merci.

EDIT:

Func1 est une interface définie comme:

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

Answer 1

Java n'a pas polymorphisme d'ordre supérieur (aka plus-types) donc ce n'est pas possible dans le système de types. De nombreux programmeurs Java recourent au langage XML et/ou à la réflexion (c'est-à-dire qu'ils échappent au système de types) pour remédier à cette lacune. Scala peut gérer cela et ce que vous décrivez s'appelle un foncteur covariant. Ce type de données plutôt fondamental (avec beaucoup plus) a été implémenté dans la bibliothèque Scalaz et inclut des implémentations pour java.util. *. En outre, il existe beaucoup plus de foncteurs covariants qui ne sont pas des collections et beaucoup plus de foncteurs qui ne sont pas covariants.

Si vous souhaitez approfondir ce concept particulier, vous pouvez choisir Google pour les «20 exercices Scala intermédiaires».

Answer 2

efficacement une liste est juste un Monad pour un type T, lui donnant la capacité de stocker plusieurs instances du type. C'est pourquoi toutes les lois habituelles des monades s'appliquent ici, donc vous pouvez implémenter toutes les opérations en utilisant un membre bind et return. Je suis désolé je n'ai pas le temps d'expliquer plus loin pour l'instant, mais dans l'espace. NET nous avons SelectMany et Enumerable.Repeat (1, élément) pour les mêmes fins. Il y a beaucoup d'informations disponibles à ce sujet.

Tout opérateur (tel que filter dans votre exemple) peut être implémenté en utilisant respectivement SelectMay bind.

Answer 3

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)); 
    } 
} 

Travail effectué.

Remarquez, c'est typique des API Java, de passer le mutable dans la collection, plutôt que de créer un nouveau dans la méthode. Personnellement, je ne suis pas un fan de la mutabilité au niveau de la collection, mais c'est ce que nous devons travailler avec (en Java).

(Je ne suis pas intéressé par A et B comme paramètres génériques avec ce genre de choses.)

Ou vous pouvez utiliser une usine.

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; 
} 

(Si vous pouvez mettre en place avec la verbosité inutile des classes internes anonymes)

S'il n'y avait pas Collection alors vous besoin de mettre un peu d'adaptateur (laid) dans

pour être complet (mais pas testé, pourrait faire avec quelques modifications), une solution désagréable en utilisant l'héritage.

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; 
    } 
} 

Answer 4

Je ne crois pas que le système de type Java soit assez sophistiqué pour résoudre ce problème, mais c'est le cas de Scala. Avec la version 2.8 de la bibliothèque de collections, ils ont construit un système pour créer automatiquement une collection du type approprié en fonction de la collection avec laquelle vous travaillez. Donc, si vous appelez filter sur un List, il renvoie un nouveau List. Appelez filter sur un Set et vous obtiendrez un Set de retour. Il le fait tout en ayant seulement une seule implémentation de filter.

Pour en savoir plus, consultez les articles Traversable et les autres choses qui l'utilisent. Je crois que CanBuildFrom est l'endroit où une grande partie de la magie se produit.

Answer 5

Je ne pense pas que vous pouvez faire mieux que ce que Tom a suggéré dans his answer. Java ne prend pas en charge les types plus élevés, ce qui peut vous aider à faire abstraction du type de collection et éviter ainsi de dupliquer le même code pour chacun des types de collection. Scala prend en charge cette fonctionnalité, et il est largement utilisé dans sa bibliothèque standard. This paper par Adriaan Moors explique comment Scala évite ce genre de duplication de code à l'aide de types plus élevés.

Deux captures d'écran du document susmentionné:

---

---