Eliminar la duplicación de código

Question

Estoy intentando crear una pequeña biblioteca de programación funcional para Java (solo para borrar mi propio picor). Mientras defino el higher-order functions para List s, Set sy Map s me he encontrado con este problema: las funciones que toman una colección, y devuelven una colección del mismo tipo tienen casi la misma implementación, y aún tienen que redefinirse para cada una de las estructura de datos - List s, Set s, y Map s.

Por ejemplo, aquí es la implementación de map función para List s, y 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; 
} 

Un filter de función:

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

Como puede verse en este ejemplo, los cuerpos de las implementaciones para Set y List son casi las mismas.

Hay muchas muchas funciones como map y filter en mi biblioteca, y cada uno de los tres veces se define para cada tipo de colecciones Me interesa (es decir List, Set y Map). Esto conduce a una gran cantidad de duplicación de código y código de olor. Quería saber si hay alguna forma en Java que me ayude a evitar toda la duplicación de código.

Cualquier ayuda será muy apreciada. Gracias.

EDIT:

Func1 es una interfaz define como:

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

Answer 1

Java no tiene polimorfismo de orden superior (aka-altos tipos) por lo que este no es posible dentro del sistema de tipo. Muchos programadores de Java recurren a XML y/o reflexión (es decir, escapan del sistema de tipos) para abordar esta deficiencia.

Scala puede ocuparse de esto y lo que usted describe se llama functor covariante. Este tipo de datos bastante fundamentales (junto con mucho más) se ha implementado en la biblioteca de Scalaz e incluye implementaciones para java.util. *.

Además, hay muchos más funtores covariantes que no son colecciones y muchos más funtores que no son covariantes.

Si lo desea, puede buscar en Google "20 ejercicios intermedios de Scala" si desea explorar este concepto en particular.

Answer 2

efectivamente una lista es sólo una Mónada para un tipo T, dándole la capacidad de almacenar múltiples instancias del tipo. Es por eso que todas las leyes habituales de mónadas se aplican aquí, por lo que puede implementar todas las operaciones utilizando un miembro bind y return.

Disculpa, no tengo tiempo para explicar más por ahora, pero en el espacio .NET tenemos SelectMany y Enumerable.Repeat (1, element) para los mismos fines. Hay mucha información disponible sobre eso.

Cualquier operador (como filter en su ejemplo) se puede implementar utilizando SelectMay unirse respectivamente.

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

Trabajo realizado.

Nota, es típico de las API de Java, pasar el mutable de la colección, en lugar de crear uno nuevo en el método. Personalmente, no soy partidario de la mutabilidad a nivel de colección, pero es con lo que tenemos que trabajar (en Java).

(No me gustan A y B como parámetros genéricos con este tipo de cosas.)

O puede utilizar una fábrica:.

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 se puede poner con el nivel de detalle sin sentido de las clases internas anónimas)

Si no fuera por Collection Entonces será que tenga que poner un poco de adaptador (feo) en

para completar (aunque no probado, podría hacer con algunos retoques), una solución desagradable utilizando la herencia:.

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

No creo que el sistema de tipos de Java sea lo suficientemente sofisticado para abordar esto, pero Scala sí lo es. Con la versión 2.8 de la biblioteca de colecciones, crearon un sistema para crear automáticamente una colección del tipo apropiado en función de la colección con la que está trabajando. Por lo tanto, si llama al filter en un List, devuelve un nuevo List. Llame al filter en un Set y obtendrá un Set de vuelta. Hace esto mientras todavía tiene una única implementación de filter. Para obtener más información, consulte Traversable y las cosas que lo utilizan. Creo que CanBuildFrom es donde sucede gran parte de la magia.

Answer 5

No creo que pueda hacer nada mejor que lo que Tom ha sugerido en his answer. Java no es compatible con tipos de alto nivel, una función que puede ayudarlo a abstraerse sobre el tipo de colección y así evitar duplicar el mismo código para cada uno de los tipos de colección.

Scala admite esta característica y se usa ampliamente en su biblioteca estándar. This paper de Adriaan Moors explica cómo Scala evita este tipo de duplicación de código con la ayuda de tipos de alto nivel.

dos capturas de pantalla del documento antes mencionado:

---

---