Usuwanie powielania kodu

Question

Próbuję utworzyć małą funkcjonalną bibliotekę programowania dla Javy (tylko po to, aby zadrapać własną swędzenie). Podczas definiowania higher-order functions dla,S i, s natknąłem się na ten problem: Funkcje, które pobierają kolekcję i zwracają kolekcję tego samego typu, mają prawie taką samą implementację, a jednak muszą zostać przedefiniowane dla każdego z nich. struktura danych - List s, Set s oraz Map s.

Na przykład tutaj jest wdrożenie map funkcji dla List S i 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; 
} 

filter funkcyjne:

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

Jak widać z tego przykładu, organy implementacji dla Set i List są prawie takie same.

Istnieje wiele wiele funkcji, takich jak map i filter w mojej bibliotece, a każdy z nich jest zdefiniowany trzykrotnie dla każdego typu zbiorów Jestem zainteresowany (tj List, Set i Map). Prowadzi to do wielu powielania kodu i zapachu kodu. Chciałem wiedzieć, czy jest jakiś sposób w Javie, który pomógłby mi uniknąć duplikacji kodu.

Każda pomoc zostanie bardzo doceniona. Dzięki.

EDIT:

Func1 jest interfejsem zdefiniowane jako:

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

Answer 1

Java nie posiada polimorfizm wyższego rzędu (aka wyższej rodzaje), więc to nie jest możliwe w systemie typu. Wielu programistów Javy odwołuje się do XML i/lub refleksji (tj. Ucieka od systemu typu) w celu rozwiązania tego problemu.

Scala może sobie z tym poradzić, a to, co opisujesz, nazywa się kowariantnym funktorem. Ten raczej podstawowy typ danych (wraz z wieloma innymi) został zaimplementowany w bibliotece Scalaz i zawiera implementacje dla java.util. *.

Co więcej, istnieje wiele innych kowariantnych funktorów, które nie są kolekcjami i wieloma innymi funktorami, które nie są kowariantne.

Możesz chcieć używać google w "20 ćwiczeniach pośrednich Scala", jeśli chcesz dalej eksplorować tę koncepcję.

Answer 2

Skutecznie lista jest tylko monady dla typu T, dając jej możliwość przechowywania wielu wystąpień tego typu. Dlatego wszystkie obowiązujące tutaj prawa monad mają zastosowanie tutaj, więc możesz zaimplementować wszystkie operacje przy użyciu członka bind i return.

Przykro mi, ale nie mam czasu na dalsze wyjaśnienia, ale w przestrzeni .NET mamy SelectMany i Enumerable.Repeat (1, element) w tych samych celach. Dostępnych jest wiele informacji na ten temat.

Każdy operator (na przykład filter w twoim przykładzie) może być zaimplementowany przy użyciu odpowiednio SelectMay.

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

Wykonane zadanie.

Uwaga, to typowe dla API Javy, aby przekazać zmienną w kolekcji, zamiast utworzyć nową w metodzie. Osobiście nie jestem fanem zmienności na poziomie kolekcji, ale właśnie z tym musimy pracować (w Javie).

(Nie jestem zwolennikiem A i B jako ogólnych parametrów z tego rodzaju rzeczy.)

Albo można użyć fabrykę.

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

(jeśli można pogodzić się z bezsensowną szczegółowość anonimowych klas wewnętrznych)

Gdyby to nie było dla Collection wtedy dalszy trzeba włożyć trochę (brzydki) adapter w

dla kompletności (choć nie testowane, może zrobić z kilku poprawek), nieprzyjemny rozwiązanie z użyciem dziedziczenia.

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

Nie wierzę, że system typu Java jest wystarczająco wyrafinowany, aby rozwiązać ten problem, ale Scala jest. W wersji 2.8 biblioteki zbiorów zbudowano system, który automatycznie tworzy kolekcję odpowiedniego typu w oparciu o kolekcję, z którą pracujesz. Tak więc, jeśli wywołasz filter na List, zwraca ona nowy List. Zadzwoń pod numer filter pod numerem Set, a otrzymasz numer Set. Robi to, mając wciąż tylko jedną implementację filter.

Aby dowiedzieć się więcej, zobacz Traversable i rzeczy, które go używają. Wierzę, że CanBuildFrom to miejsce, w którym dzieje się wiele magii.

Answer 5

Nie sądzę, że można zrobić lepiej niż to, co Tom zasugerował w his answer. Java nie obsługuje typów o wyższym typie - funkcja, która może pomóc w abstrakcji nad typem kolekcji, a tym samym uniknąć duplikowania tego samego kodu dla każdego z typów kolekcji.

Scala obsługuje tę funkcję i jest szeroko stosowana w standardowej bibliotece. This paper autorstwa Adriaana Moorsa omawia, w jaki sposób Scala unika tego rodzaju duplikacji kodu przy pomocy typów wyższych typów.

dwa screeny z wyżej wymienionym artykule:

---

---