List und default methods

Ich habe für das List Interface mal einen Vorschlag für ein paar Default-Methoden:


    public default A head() throws NoSuchElementException {
        return headOpt().orElseThrow(() -> new NoSuchElementException("head() call on empty List"));
    }

    public default Optional<A> headOpt() {
        return getOpt(0);
    }

    public List<A> tail() throws NoSuchElementException;

    public Optional<List<A>> tailOpt();

    public default A last() throws NoSuchElementException {
        return lastOpt().orElseThrow(() -> new NoSuchElementException("last() call on empty List"));
    }

    public default Optional<A> lastOpt() {
        return getOpt(size() - 1);
    }

    public List<A> init() throws NoSuchElementException;

    public Optional<List<A>> initOpt();

    public default A get(int index) throws IndexOutOfBoundsException {
        return getOpt(index).orElseThrow(
                () -> new IndexOutOfBoundsException(String.format("get(%d) call on list of size %d", index, size()))
        );
    }

    public Optional<A> getOpt(int index);

    public int size();

    public default boolean isEmpty() {
        return size() == 0;
    }

    public List<A> with(int index, A value);

    public List<A> concat(List<? extends A> that);

    public List<A> take(int count);

    public List<A> drop(int count);

    public <B> List<B> map(Function<? super A, ? extends B> fn);

    public <B> List<B> flatMap(Function<? super A, ? extends Iterable<? extends A>> fn);

    public List<A> filter(Predicate<? super A> predicate);
}```

Da ginge noch einiges mehr, aber wie weit soll man gehen? Und: wie testet man die Default-Methoden am geschicktesten?

Inwieweit macht es überhaupt Sinn, Default-Methoden zu verwenden?

Den Vorschlag habe ich noch nicht commited. Allerdings habe ich die Methoden noch etwas umsortiert und die xxxOpt-Varianten für `init` und `last` eingefügt.

*** Edit ***

Es fehlen auch noch `foldl` und `foldr`.

[QUOTE=cmrudolph]Ich habe für das List Interface mal einen Vorschlag für ein paar Default-Methoden:


    public default A head() throws NoSuchElementException {
        return headOpt().orElseThrow(() -> new NoSuchElementException("head() call on empty List"));
    }

    public default Optional<A> headOpt() {
        return getOpt(0);
    }

    public List<A> tail() throws NoSuchElementException;

    public Optional<List<A>> tailOpt();

    public default A last() throws NoSuchElementException {
        return lastOpt().orElseThrow(() -> new NoSuchElementException("last() call on empty List"));
    }

    public default Optional<A> lastOpt() {
        return getOpt(size() - 1);
    }

    public List<A> init() throws NoSuchElementException;

    public Optional<List<A>> initOpt();

    public default A get(int index) throws IndexOutOfBoundsException {
        return getOpt(index).orElseThrow(
                () -> new IndexOutOfBoundsException(String.format("get(%d) call on list of size %d", index, size()))
        );
    }

    public Optional<A> getOpt(int index);

    public int size();

    public default boolean isEmpty() {
        return size() == 0;
    }

    public List<A> with(int index, A value);

    public List<A> concat(List<? extends A> that);

    public List<A> take(int count);

    public List<A> drop(int count);

    public <B> List<B> map(Function<? super A, ? extends B> fn);

    public <B> List<B> flatMap(Function<? super A, ? extends Iterable<? extends A>> fn);

    public List<A> filter(Predicate<? super A> predicate);
}```

[/quote]

An sich richtig, aber `head` und `tail` sind normalerweise die primitiven Operationen auf einer immutablen Liste, deshalb würde ich es eher andersherum machen, nämlich `get` und `getOpt` mittels Default-Methoden implementieren (wie z.B: auch `drop`, `take` u.s.w



> Da ginge noch einiges mehr, aber wie weit soll man gehen?


Es fehlen noch völlig Methoden zum Aufbauen einer Liste. takeWhile und dropWhile würde ich auch noch dazunehmen, außerdem reverse.


> Und: wie testet man die Default-Methoden am geschicktesten?


Über die Standard-Implementierung.


> Inwieweit macht es überhaupt Sinn, Default-Methoden zu verwenden?


Ich denke hier macht es schon Sinn. Insbesondere wenn wir bei Listen mehrere (wahrschienlich anonyme) Implementierungen haben, die Laziness unterstützen.


> Den Vorschlag habe ich noch nicht commited. Allerdings habe ich die Methoden noch etwas umsortiert und die xxxOpt-Varianten für `init` und `last` eingefügt.


Lass mich noch mal drüberschauen, ich poste einen Entwurf.




> Es fehlen auch noch `foldl` und `foldr`.


Sind als `foldLeft` und `foldRight` vorhanden. Finde ich lesbarer, und bisher haben wir das meiste ausgeschrieben (mti Ausnahme von xxxOpt), können wir aber diskutieren.

*** Edit ***

public interface List extends Iterable {

public A head() throws NoSuchElementException;

@SuppressWarnings("unchecked")
public static <A> List<A> empty() {
    return (List<A>) Nil.NIL;
}

public static <A> List<A> cons(A head, List<A> tail) {
    return new Cons<>(head, tail);
}

public static <A> List<A> of(A... values) {
    List<A> result = empty();
    for (int i = values.length - 1; i >= 0; i--) {
        result = cons(values**, result);
    }
    return result;
}

public default Optional<A> headOpt() {
    return isEmpty() ? Optional.<A>empty() : Optional.of(head());
}

public List<A> tail() throws NoSuchElementException;

public default Optional<List<A>> tailOpt() {
    return isEmpty() ? Optional.<List<A>>empty() : Optional.of(tail());
}

public default A last() throws NoSuchElementException {
    if (isEmpty()) {
        throw new NoSuchElementException("last() called on Nil");
    }
    A value = null;
    for(A a : this) {
        value = a;
    }
    return value;
}

public default Optional<A> lastOpt() {
    if (isEmpty()) {
        return Optional.empty();
    }
    A value = null;
    for(A a : this) {
        value = a;
    }
    return Optional.of(value);
}

public default List<A> init() throws NoSuchElementException {
    if (isEmpty()) {
        throw new NoSuchElementException("init() called on Nil");
    }
    return reverse().tail().reverse();
}

public default Optional<List<A>> initOpt() {
    if (isEmpty()) {
        return Optional.empty();
    }
    return Optional.of(reverse().tail().reverse());
}

public default A get(int index) throws IndexOutOfBoundsException {
    List<A> current = this;
    for (int i = 0; i < index && !current.isEmpty(); i++) {
        current = current.tail();
    }
    if (current.isEmpty()) {
        throw new IndexOutOfBoundsException();
    }
    return current.head();
}

public default Optional<A> getOpt(int index) {
    List<A> current = this;
    for (int i = 0; i < index && !current.isEmpty(); i++) {
        current = current.tail();
    }
    if (current.isEmpty()) {
        return Optional.empty();
    }
    return Optional.of(current.head());
}

public default int size() {
    return foldLeft(0, (n, a) -> n + 1);
}

public default boolean isEmpty() {
    return false;
}

public default List<A> with(int index, A value) throws IndexOutOfBoundsException {
    int i = 0;
    List<A> result = empty();
    for(A a : this)  {
        cons(i++ == index ? value : a, result);
    }
    if (i < index) {
        throw new IndexOutOfBoundsException();
    }
    return result.reverse();
}

public default List<A> concat(List<A> that) {
    List<A> result = that;
    for (A a : this.reverse()) {
        result = cons(a, result);
    }
    return result;
}

public default List<A> take(int count) {
    List<A> result = empty();
    int index = 0;
    for (A a : this) {
        if (index++ >= count) {
            break;
        }
        result = cons(a, result);
    }
    return result.reverse();
}

public default List<A> takeWhile(Predicate<A> predicate) {
    List<A> result = empty();
    for (A a : this) {
        if (! predicate.test(a)) {
            break;
        }
        result = cons(a, result);
    }
    return result.reverse();
}

public default List<A> drop(int count) {
    List<A> current = this;
    for (int index = 0; index < count && !current.isEmpty(); index++) {
        current = current.tail();
    }
    return current;
}

public default List<A> dropWhile(Predicate<A> predicate) {
    List<A> current = this;
    while(! current.isEmpty() && predicate.test(current.head())) {
        current = current.tail();
    }
    return current;
}

public default List<A> reverse() {
    List<A> result = empty();
    for (A a : this) {
        result = cons(a, result);
    }
    return result;
}

public default <B> List<B> map(Function<? super A, ? extends B> fn) {
    List<B> result = empty();
    for (A a : this) {
        cons(fn.apply(a), result);
    }
    return result.reverse();
}

public default <B> List<B> flatMap(Function<? super A, ? extends Iterable<? extends B>> fn) {
    List<B> result = empty();
    for (A a : this) {
        for(B b : fn.apply(a)) {
            cons(b, result);
        }    
    }
    return result.reverse();
}

public default List<A> filter(Predicate<? super A> predicate) {
    List<A> result = empty();
    for (A a : this) {
        if (predicate.test(a)) {
            cons(a, result);
        }
    }
    return result.reverse();
}

public default <B> B foldLeft(B start, BiFunction<? super B, ? super A, ? extends B> fn) {
    B value = start;
    for(A a : this) {
        value = fn.apply(value, a);
    }
    return value;
}

public default <B> B foldRight(BiFunction<? super A, ? super B, ? extends B> fn, B start) {
    B value = start;
    for(A a : this.reverse()) {
        value = fn.apply(a, value);
    }
    return value;
}

@Override
public default Iterator<A> iterator() {
    return new Iterator<A>() {
        
        private List<A> current = List.this;
        
        @Override
        public boolean hasNext() {
            return ! current.isEmpty();
        }

        @Override
        public A next() {
            if (! hasNext()) {
                throw new NoSuchElementException();
            }
            A value = current.head();
            current = current.tail();
            return value;
        }
    };
}

}


public class Nil implements List {

final static Nil<?> NIL = new Nil<>();

private Nil() {
}

@Override
public Iterator<A> iterator() {
    return Collections.emptyIterator();
}

@Override
public A head() throws NoSuchElementException {
    throw new NoSuchElementException("head() call on Nil");
}

@Override
public List<A> tail() throws NoSuchElementException {
    throw new NoSuchElementException("tail() call on Nil");
}

@Override
public boolean isEmpty() {
    return true;
}

public String toString() {
    return "[]";
}

}


public class Cons implements List {

private final A head;
private final List<A> tail;

Cons(A head, List<A> tail) {
    this.head = Objects.requireNonNull(head);
    this.tail = Objects.requireNonNull(tail);
}

public A head() {
    return head;
}

public List<A> tail() {
    return tail;
}

public String toString() {
    StringBuilder sb = new StringBuilder();
    for(A a : this) {
        sb.append(sb.length() == 0 ? "[" : ",").append(a);
    }
    return sb.append("]").toString();
}

}



Im Repo-Code sind noch ein paar Fehlerchen drin. Das hier ist alles ungetestet.

Ich habe es noch nicht gründlich gesichtet, aber ich würde die Methoden aufeinander abstützen, um die Duplizierung zu vermeiden:

    return getOpt(index).orElseThrow(() -> new IndexOutOfBoundsException());
}```

Morgen werde ich noch einmal etwas detaillierter auf deinen Beitrag eingehen.

@Landei
Ich bin deinen Code mal in Ruhe durchgegangen. Ich habe einige Änderungen vorgenommen. Dabei habe ich festgestellt, dass wir für solche Arbeiten branchen sollten (u. a. wegen diff). Vorschlag für einen Branchnamen: feat/list.
Ich habe den Branch jetzt noch nicht erstellt, weil der Großteil des Codes von dir stammt und daher auch dein Name neben dem Commit stehen sollte.
Tests habe ich noch nicht geschrieben, das mache ich aber gleich noch.


    @SuppressWarnings("unchecked")
    public static <A> List<A> empty() {
        return (List<A>) Nil.NIL;
    }

    public static <A> List<A> cons(A head, List<A> tail) {
        return new Cons<>(head, tail);
    }

    @SafeVarargs
    public static <A> List<A> of(A... values) {
        List<A> result = empty();
        for (int i = values.length - 1; i >= 0; i--) {
            result = cons(values**, result);
        }
        return result;
    }

    public A head() throws NoSuchElementException;

    public default Optional<A> headOpt() {
        return Optional.of(head());
    }

    public List<A> tail() throws NoSuchElementException;

    public default Optional<List<A>> tailOpt() {
        return Optional.of(tail());
    }

    public default A last() throws NoSuchElementException {
        return lastOpt().get();
    }

    public default Optional<A> lastOpt() {
        A value = null;
        for (A a : this) {
            value = a;
        }
        return Optional.of(value);
    }

    public default List<A> init() throws NoSuchElementException {
        return initOpt().get();
    }

    public default Optional<List<A>> initOpt() {
        return Optional.of(reverse().tail().reverse());
    }

    public default A get(int index) throws IndexOutOfBoundsException {
        return getOpt(index).orElseThrow(IndexOutOfBoundsException::new);
    }

    public default Optional<A> getOpt(int index) {
        List<A> current = this;
        for (int i = 0; i < index && !current.isEmpty(); i++) {
            current = current.tail();
        }
        if (current.isEmpty()) {
            return Optional.empty();
        }
        return Optional.of(current.head());
    }

    public default int size() {
        return foldLeft(0, (n, a) -> n + 1);
    }

    public default boolean isEmpty() {
        return false;
    }

    public default List<A> with(int index, A value) throws IndexOutOfBoundsException {
        int i = 0;
        List<A> result = empty();
        for (A a : this) {
            cons(i == index ? value : a, result);
            i++;
        }
        if (i < index) {
            throw new IndexOutOfBoundsException();
        }
        return result.reverse();
    }

    public default List<A> concat(List<A> that) {
        List<A> result = that;
        for (A a : this.reverse()) {
            result = cons(a, result);
        }
        return result;
    }

    public default List<A> take(int count) {
        List<A> result = empty();
        int index = 0;
        for (A a : this) {
            if (index >= count) {
                break;
            }
            index++;
            result = cons(a, result);
        }
        return result.reverse();
    }

    public default List<A> takeWhile(Predicate<A> predicate) {
        List<A> result = empty();
        for (A a : this) {
            if (!predicate.test(a)) {
                break;
            }
            result = cons(a, result);
        }
        return result.reverse();
    }

    public default List<A> drop(int count) {
        List<A> current = this;
        for (int index = 0; index < count && !current.isEmpty(); index++) {
            current = current.tail();
        }
        return current;
    }

    public default List<A> dropWhile(Predicate<A> predicate) {
        List<A> current = this;
        while (!current.isEmpty() && predicate.test(current.head())) {
            current = current.tail();
        }
        return current;
    }

    public default List<A> reverse() {
        List<A> result = empty();
        for (A a : this) {
            result = cons(a, result);
        }
        return result;
    }

    public default <B> List<B> map(Function<? super A, ? extends B> fn) {
        List<B> result = empty();
        for (A a : this) {
            cons(fn.apply(a), result);
        }
        return result.reverse();
    }

    public default <B> List<B> flatMap(Function<? super A, ? extends Iterable<? extends B>> fn) {
        List<B> result = empty();
        for (A a : this) {
            for (B b : fn.apply(a)) {
                cons(b, result);
            }
        }
        return result.reverse();
    }

    public default List<A> filter(Predicate<? super A> predicate) {
        List<A> result = empty();
        for (A a : this) {
            if (predicate.test(a)) {
                cons(a, result);
            }
        }
        return result.reverse();
    }

    public default <B> B foldLeft(B start, BiFunction<? super B, ? super A, ? extends B> fn) {
        B value = start;
        for (A a : this) {
            value = fn.apply(value, a);
        }
        return value;
    }

    public default <B> B foldRight(BiFunction<? super A, ? super B, ? extends B> fn, B start) {
        B value = start;
        for (A a : this.reverse()) {
            value = fn.apply(a, value);
        }
        return value;
    }

    @Override
    public default Iterator<A> iterator() {
        return new Iterator<A>() {

            private List<A> current = List.this;

            @Override
            public boolean hasNext() {
                return !current.isEmpty();
            }

            @Override
            public A next() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                A value = current.head();
                current = current.tail();
                return value;
            }
        };
    }
}```

```public class Nil<A> implements List<A> {

    final static Nil<?> NIL = new Nil<>();

    private Nil() {
    }

    @Override
    public A head() throws NoSuchElementException {
        throw new NoSuchElementException("head() call on Nil");
    }

    @Override
    public Optional<A> headOpt() {
        return Optional.empty();
    }

    @Override
    public List<A> tail() throws NoSuchElementException {
        throw new NoSuchElementException("tail() call on Nil");
    }

    @Override
    public Optional<List<A>> tailOpt() {
        return Optional.empty();
    }

    @Override
    public A last() throws NoSuchElementException {
        throw new NoSuchElementException("last() call on Nil");
    }

    @Override
    public Optional<A> lastOpt() {
        return Optional.empty();
    }

    @Override
    public List<A> init() throws NoSuchElementException {
        throw new NoSuchElementException("init() call on Nil");
    }

    @Override
    public Optional<List<A>> initOpt() {
        return Optional.empty();
    }

    @Override
    public A get(int index) throws IndexOutOfBoundsException {
        throw new IndexOutOfBoundsException("get() call on Nil");
    }

    @Override
    public Optional<A> getOpt(int index) {
        return Optional.empty();
    }

    @Override
    public boolean isEmpty() {
        return true;
    }

    @Override
    public Iterator<A> iterator() {
        return Collections.emptyIterator();
    }

    public String toString() {
        return "[]";
    }
}```

```class Cons<A> implements List<A> {

    private final A head;
    private final List<A> tail;

    Cons(A head, List<A> tail) {
        this.head = Objects.requireNonNull(head);
        this.tail = Objects.requireNonNull(tail);
    }

    public A head() {
        return head;
    }

    public List<A> tail() {
        return tail;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (A a : this) {
            sb.append(sb.length() == 0 ? "[" : ",").append(a);
        }
        return sb.append("]").toString();
    }
}```

Zu den Änderungen:
Ich habe um Redundanzen zu vermeiden die get-Methode auf die getOpt-Methode mittels `getOpt.orElseThrow(IndexOutOfBoundsException::new)` abgestützt.
Außerdem habe ich die Verzweigungen bei den `if (isEmpty())`-Fällen entfernt. Dadurch ist die `Nil`-Klasse um Trivialmethoden gewachsen, die `Optional.empty()` oder eine passende Exception werfen.
Ansonsten habe ich die Methoden nur umsortiert, sodass sie in einer halbwegs konsistenten Reihenfolge stehen.

*** Edit ***

Ein weiterer Punkt, den ich gerne noch zur Diskussion stellen möchte:
Als ich die isEmpty-Verzweigungen aufgesplittet habe, fragte ich mich, ob die Defaultimplementierung nicht eigentlich eher in die Cons-Klasse gehört und die Methode im List-Interface abstrakt bleiben sollte. Das wäre mMn plausibel, wenn man leere und befüllte Listen gleichberechtigt betrachten würde.
Der andere Ansatz ist allerdings, dass man sagt: "eine Liste ist standardmäßig nicht leer". Daher auch isEmpty mit Defaultwert false und die Defaultimplementierungen im Interface.
Die einzige Option, die ich nicht so prickelnd finde (daher habe ich den Code auch geändert) ist, beide Implementierungen im Interface zu haben. Vor allem wirkt es etwas merkwürdig, wenn die Defaultmethode eine Exceptionmessage "xxx() call on Nil" zurückgibt. Die Verzweigungen kann und sollte man durch Vererbung vermeiden.

*** Edit ***

Und noch etwas, was beim Tests schreiben hochgekommen ist. List sollte wohl equals und hashCode implementieren, oder?

*** Edit ***

Für equals wäre eine zip-Methode extrem handlich. Dann könnten zip, equals und hashCode etwa so aussehen:

in List:
```public default <B> List<Pair<A, B>> zip(List<B> other) {
    if (this.size() != other.size()) {
        throw new IllegalArgumentException("list sizes must match");
    }
    List<Pair<A, B>> result = List.empty();
    Iterator<B> otherIterator = other.iterator();
    for (A a : this) {
        result = cons(Pair.of(a, otherIterator.next()), result);
    }
    return result.reverse();
}```

in Cons:
```@Override
public boolean equals(Object obj) {
    if (this == obj) {
        return true;
    }
    if (!(obj instanceof List<?>)) {
        return false;
    }
    List<?> that = (List<?>) obj;
    for (Pair<A, ?> pair : this.zip(that)) {
        if (!pair.get1().equals(pair.get2())) {
            return false;
        }
    }
    return true;
}

@Override
public int hashCode() {
    return this.foldLeft(0, (a, b) -> 31 * a.hashCode() + b.hashCode());
}```

In Nil brauchen equals und hashCode nicht überschrieben zu werden, weil es nur eine Instanz gibt. Die Defaultimplementierung ist daher ausreichend.

*** Edit ***

Beim Tests schreiben ist mir aufgefallen, dass wir noch über die Semantik der leeren Liste diskutieren müssen. Ich glaube es wäre handlicher, wenn init und tail auch auf einer leeren Liste einen vernünftigen Rückgabewert haben, nämlich die leere Liste.
Das verschlankt das API und ist auch eigentlich plausibel.

*** Edit ***

Ist jetzt ganz schön was zusammengekommen. Einige kleinere Bugs sind noch aufgefallen (hauptsächlich vergessene `return = cons(...)`). Für ungetesteten Code also ein gutes Ergebnis ;-)
Ich habe jetzt ohne auf eine Antwort zu warten einfach wie vorgeschlagen einen Branch `feat/list` erstellt und auch die List, Cons und Nil-Klassen eingecheckt, weil ich das Arbeitsergebnis vernünftig gesichert wissen will.
Jetzt ist erstmal gut für heute :-)

Sorry, ich hatte einen Kurztrip über Pfingsten - hätte ich mal erwähnen sollen. Der Feature-Branch ist eine gute Idee, und wer als Committer drinsteht, ist mir recht egal. Ohne mir den Code im Einzelnen durchgesehen zu haben, klingt das alles recht vernünftig. Nur bei der zip-Methode möchte ich Einspruch einlegen: Üblicherweise sind ungleich lange Listen dabei durchaus erlaubt, die längere wird dann entsprechend “abgeschnitten”. Wir können gern eine “sichere” Variante von zip anbieten (“safeZip” oder “strictZip” oder so?), aber das Standardverhalten sollte unbedingt unterstützt werden.

Mir ist es auch egal, wer irgendwo namentlich auftaucht. Aber es gibt nunmal einige, die sehr viel Wert auf ihre “Credits” legen, daher wollte ich dir das Recht nicht verwehren.

Das “Standardverhalten” einer zip-Methode war mir nicht bekannt. Ich hatte nur ganz kurz nach “zip method” gesucht und bin bei der Doku einer F#-Methode gelandet, aus deren Signatur ich das Verhalten einer derartigen Methode interpretiert habe. Dass das nicht unbedingt zum Standardverhalten geführt hat, ist nicht allzu verwunderlich :wink: Und weil ich am Freitag so im Fluss war, hab ich einfach mal gemacht.
Ein “strictZip” (den Namen finde ich treffender als safeZip) wäre ja nur ein einfacher Wrapper, der vorher prüft, ob die Listen gleich lang sind. Also eigentlich nur ein Split der Methode, die ich eingecheckt habe.

Oh, da gab es noch mehr Probleme: Auch tail() und init() sollen für leere Listen eine NoSuchElementException werfen. Ich habe das mal korrigiert und tailOpt() und initOpt() hinzugefügt. Nebenbei bemerkt bekommt man das “alte” Verhalten von tail(), wenn man einfach drop(1) schreibt, insofern ist das kein Verlust.

Ich habe noch zip() korrigiert, und einige Kleinigkeiten: Bei List.equals() habe ich den size()-call herausoptimiert, weil sonst die Listen zweimal durchgegangen worden wären. hashCode ließ sich etwas vereinfachen.

Außerdem habe ich wie vorgeschlagen alle Implementierungen von head(), init(), tail(), last() und deren Opt-Varianten von List nach Cons und Nil verschoben, es ist so tatsächlich übersichtlicher.

Das war auch mit das erste, was mir aufgefallen ist. Damit erreicht man schnell eine hohe Mächtigkeit, und die Default-Methoden machen umso mehr Sinn, je mehr Methoden man implementiert, die sich nur auf default-Methoden “abstützen”. Ähnlich wie bei AbtractList, wo man nur “size()” und “get()” implementieren muss, und alles andere automatisch da ist, weil es nur darauf aufbaut.

Ansonsten muss ich jetzt erstmal “reinkommen”, ich hatte den “Anfang” des Projektes ja nicht richtig mitbekommen, und muss erstmal lesen (Code+Threads) und den Überblick bekommen. Deswegen ist alles, was ich sage, mit vieeel Vorbehalt zu sehen.

Was mir beim ersten Drüberschauen aufgefallen war, war z.b. die Frage, ob
return this.foldLeft(0, (a, b) -> 31 * a.hashCode() + b.hashCode());
nicht eine NullPointerException wirft, wenn jemand so frech ist, eine “null” in eine Liste zu packen.

Zu dem “zip” und “strictZip”: Ich stelle mir bei solchen Dingen eine Frage, die mit dem “aufeinander Abstützen” verwandt ist: Welche Variante kann die andere leicht emulieren? Oder anders: Welche API hat ein gutes “Power-To-Weight-Ratio”? Oder ganz konkret:
[ol]
[li]Wird es sowas wie Collections#nCopies für die List geben? [/li][li]Wird es sowas wie List#sublist für die List geben? [/li][/ol]
Ich fände beides ziemlich wichtig.

EDIT: Bzgl. des equals: Da fand ich etwas irritierend, dass man zippen MUSS, um die Gleichheit zu erkennen. Dass man nicht am Anfang einmal if (this.size() != other.size()) return false; schreibt, ist eine Sache, aber nachdem man das gemacht hat, sollte die Gleichheit doch mit sowas wie

return head().equals(other.head()) && tail().equals(other.tail());

erledigt sein?!? Aber nochmal: Alles unter Vorbehalt, ich hab’ mir den “echten” Code noch nichtmal angesehen :o

Finde ich gut, Übersichtlichkeit und Performance sollten aber Vorrang haben.

Ansonsten muss ich jetzt erstmal “reinkommen”, ich hatte den “Anfang” des Projektes ja nicht richtig mitbekommen, und muss erstmal lesen (Code+Threads) und den Überblick bekommen. Deswegen ist alles, was ich sage, mit vieeel Vorbehalt zu sehen.

Kein Problem

Was mir beim ersten Drüberschauen aufgefallen war, war z.b. die Frage, ob
return this.foldLeft(0, (a, b) -> 31 * a.hashCode() + b.hashCode());
nicht eine NullPointerException wirft, wenn jemand so frech ist, eine “null” in eine Liste zu packen.

Das habe ich gerade zu return this.foldLeft(0, (a, b) -> 31 * a + b.hashCode()); geändert. NPE kann nicht auftreten, weil wir Nullwerte in Listen abfangen (Objects.requireNonNull()).

Zu dem “zip” und “strictZip”: Ich stelle mir bei solchen Dingen eine Frage, die mit dem “aufeinander Abstützen” verwandt ist: Welche Variante kann die andere leicht emulieren? Oder anders: Welche API hat ein gutes “Power-To-Weight-Ratio”? Oder ganz konkret:
[ol]
[li]Wird es sowas wie Collections#nCopies für die List geben? [/li]> [li]Wird es sowas wie List#sublist für die List geben? [/li]> [/ol]
Ich fände beides ziemlich wichtig.

nCopies: Wenn wir auch lazy-Listen anbieten (die ja unendlich lang sein können), wäre das einfach LazyList.repeat(t).take(n). Ansonsten halt in List, aber das müssen wir halt noch entscheiden.
subList: Lässt sich durch drop(n).take(m-n) simulieren, könnte man aber “fertig” anbieten.

EDIT: Bzgl. des equals: Da fand ich etwas irritierend, dass man zippen MUSS, um die Gleichheit zu erkennen. Dass man nicht am Anfang einmal if (this.size() != other.size()) return false; schreibt, ist eine Sache, aber nachdem man das gemacht hat, sollte die Gleichheit doch mit sowas wie

return head().equals(other.head()) && tail().equals(other.tail());

erledigt sein?!? Aber nochmal: Alles unter Vorbehalt, ich hab’ mir den “echten” Code noch nichtmal angesehen :o

Schau dir die aktuelle Implementierung an, da vermeide ich sowohl zip wie auch size.

*** Edit ***

Ich habe noch 4 statische Funktionen hinzugefügt, die ich für nützlich halte:

  • lefts() sammelt von einer Either-Liste nur die “linken” Werte ein
  • rights() sammelt von einer Either-Liste nur die “rechten” Werte ein
  • leftsRights() sammelt von einer Either-Liste die “linken” und “rechten” Werte in zwei Listen ein, die als Listen-Paar zurückgegeben werden
  • unzip() sammelt von einer Paar-Liste die “ersten” und “zweiten” Werte in zwei Listen ein, die als Listen-Paar zurückgegeben werden

Theoretisch könnte man für Paare auch noch firsts und seconds (analog zu lefts und rights) einführen, und für Tripel ein unzip3 u.s.w., aber ich wollte erst mal eure Meinung einholen

Die Methoden finde ich gut. Allerdings hätte ich eine alternative Implementierung vorgeschlagen, die ohne die Collections-Klasse auskommt und mMn der direktere Weg zum Ergebnis ist. Von der Laufzeitkomplexität her sollte es sich nicht unterscheiden, ich habe es aber nicht im Detail analysiert.

    return list.foldRight((e, ls) -> e.isLeft() ? cons(e.left(), ls) : ls, List.empty());
}

public static <A, B> List<B> rights(List<Either<A, B>> list) {
    return list.foldRight((e, rs) -> e.isRight() ? cons(e.right(), rs) : rs, List.empty());
}```

Die `leftsRights`-Methode wäre so lesbarer, bräuchte aber einen Listendurchlauf mehr:
```public static <A, B> Pair<List<A>, List<B>> leftsRights(List<Either<A, B>> list) {
    return Pair.of(lefts(list), rights(list));
}```

Ich bin dagegen diese Methoden auch noch für Tripel+ zu implementieren. Zumindest nicht in List, sondern wenn dann in einer Utilityklasse.

Stimmt, da habe ich zu kompliziert gedacht. Ich finde das hier noch einfacher:

   public static <A, B> List<A> lefts(List<Either<A, B>> list) {
        return list.foldRight((e, ls) -> e.fold(left -> cons(left, ls), right -> ls), List.empty());
    }

    public static <A, B> List<B> rights(List<Either<A, B>> list) {
        return list.foldRight((e, rs) -> e.fold(left -> rs, right -> cons(right, rs)), List.empty());
    }

Die leftsRights-Methode wäre so lesbarer, bräuchte aber einen Listendurchlauf mehr:

    return Pair.of(lefts(list), rights(list));
}```

Vermutlich wäre es dann besser “umgedreht”: leftsRights implementieren und dann bei lefts und rights nur die benötigte Liste herauspicken. Aber aus Performancegründen würde ich erst einmal jede Methode separat implementieren.

Ich bin dagegen diese Methoden auch noch für Tripel+ zu implementieren. Zumindest nicht in List, sondern wenn dann in einer Utilityklasse.

Ja, das Problem sehe ich auch. Eventuell könnte man die doch etwas spezielleren Either-List-Methoden in Either packen?

Noch eine Stil-Frage: Wie gehen wir mit der Frage “statisch oder nicht” um? Manche Methoden sind klar statisch (etwa of() oder unzip()), aber bei anderen wie cons() und zip() ist das nicht so klar. Sollen wir nur das statisch machen, was **wirklich **statisch sein muss (dann müssten wir cons() ändern)? Oder gibt es ein anderes sinnvolles Kriterium?

Dann fehlt unbedingt noch die Methode List<C> zipWith(List<B>, (a,b) -> c) (von der zip() nur ein häufiger Spezialfall ist - für Tripel+ kann man sich das dann leicht selbst schreiben). Ebenfalls sehr nützlich wären static List<A> iterateN(A start, int n, a -> a) und static List<A> iterateWhile(A start, Predicate<A>, a -> a) als einfache Möglichkeit, eine rekursiv definierte Folge zu einer Liste zu machen (was auch nCopies und ähnliches abdecken würde).

Ja, finde ich auch. Da hatte ich übersehen, dass die äußeren Parameter natürlich auch in der inneren Methode verwendet werden dürfen :wink:

Den Gedanken hatte ich auch schon, man erzeugt aber unter Umständen (bei langen Listen) sehr viele unnötige Objekte.

Schwierige Frage, da muss ich auch noch etwas drüber nachdenken. Ich fände auch eine Methode zum entpacken von Optionals aus einer Liste sinnvoll:

    return that.foldRight(...);
}```
Die könnten wir auf jeden Fall nicht in Optional packen ;-)

[QUOTE=Landei;95308]Noch eine Stil-Frage: Wie gehen wir mit der Frage "statisch oder nicht" um? Manche Methoden sind klar statisch (etwa `of()` oder `unzip()`), aber bei anderen wie `cons()` und `zip()` ist das nicht so klar. Sollen wir nur das statisch machen, was **wirklich **statisch sein muss (dann müssten wir `cons()` ändern)? Oder gibt es ein anderes sinnvolles Kriterium?[/QUOTE]
Die Methoden, die eindeutig statisch sind stehen ja nicht zur Debatte.
Die Factorymethoden/"Konstruktoren" wie cons und empty sollten auch statisch bleiben. Cons würde sich wahrscheinlich etwas komisch "anfühlen", wenn es nicht statisch wäre.
Ansonsten tendiere ich aber dazu, die Methoden eher nicht statisch zu machen.

[QUOTE=Landei;95308]Dann fehlt unbedingt noch die Methode `List<C> zipWith(List<B>, (a,b) -> c)` (von der `zip()` nur ein häufiger Spezialfall ist - für Tripel+ kann man sich das dann leicht selbst schreiben). Ebenfalls sehr nützlich wären `static List<A> iterateN(A start, int n, a -> a)` und `static List<A> iterateWhile(A start, Predicate<A>, a -> a)` als einfache Möglichkeit, eine rekursiv definierte Folge zu einer Liste zu machen (was auch `nCopies` und ähnliches abdecken würde).[/QUOTE]
Da muss ich auch noch etwas drüber nachdenken. Aber das `zipWith` hört sich wirklich äußerst nützlich an. **Vielleicht** sollte man dann `zip` sogar wegwerfen. Die anderen beiden Kandidaten sehe ich da schon etwas kritischer.

Noch was ganz generelles: Wollen wir trotz Namens-Clash beim Namen “List” bleiben? Mir fällt ehrlich gesagt nichts Originelleres als ein Präfix ein, aber das wäre schon ein wichtiger Punkt.

Als nächstes stellt sich die Frage nach Utility-Klassen, vielleicht Lists für die ganzen statischen Methoden wie lefts, unpack, und eine Klasse Conversions für Methoden zur Umwandlung unserer Klassen aus/zu Java-Collections.

zip könnten wir tatsächlich droppen, wobei dann konsequenterweise auch unzip weg müsste. Bei den iterate-Methoden bin ich mir nicht sicher, aber irgend eine Form, eine Liste aus einer rekursiven Funktion aufzubauen, wäre nicht schlecht. static List<A> iterateWhile(A start, A -> Optional<A>) wäre auch denkbar, wo das Ende der Iteration durch ein leeres Optional angezeigt wird.

Auch wenn es langsam unübersichtlich wird, würde ich noch die Methoden all und any für Listen vorschlagen, die testen, ob ein übergebenes Prädikat für alle bzw. mindestens ein Element gilt, eventuell auch ein findFirst / findFirstOpt.

Ich bin für einen Namen wie “ImmutableList”. Ansonsten muss man dreimal nachsehen, ob man jetzt eine klassische Collection hat, oder eine immutable List. Die Signatur einer Konversionsmethode sähe sicherlich auch ziemlich bescheiden aus, wenn man den Namen List beibehielte.

Das hatte ich oben ja auch schon angedeutet - ich finde es sinnvoll.

Beim zip / unzip bin ich mir noch nicht ganz sicher. Das könnte auch in die Utilityklasse. Und eine iterateWhile würde ich auch in Lists (oder entsprechend ImmutableLists?) packen.

Wir können es ja erstmal reinnehmen und später dann noch einmal ausmisten, was vielleicht doch nicht mit in den Standardumfang gehören soll.

ImmutableList würde mit Guava clashen: http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/ImmutableList.html

Ist natürlich nicht so schlimm, und ich habe auch keine bessere Idee. ImList? NecoList? NCList? Alles doof…

Ohje… irgendwie komm’ ich hier nicht mehr mit/nach - hoffentlich kann ich am WE mal den (und die anderen) Threads lesen. Zu dem static würde ich ggf. morgen noch was sagen, aber zu den Namen kurz: Ein clash mit Guava ist IMHO bei weitem nicht so schlimm, wie mit der Standard-API. Bei letzterem wäre die Interoperabilität bei Methoden wie java.util.List toJavaList(neco4j.List list) ein Krampf, und solange man keine Interoperabilität mit Guava anbieten will, tritt dieser clash ja zumindest nicht in der Lib selbst auf. Sowas wie “NecoList” wäre IMHO auch OK, besser als etwas nicht-aussprechbares wie NCList, aber eine “gefestigte Meinung” hab’ ich zu alledem erstmal nicht…

Ich sehe das ähnlich wie @Marco13 : einen Clash mit Guava finde ich an der Stelle nicht ganz so schlimm. NecoList wäre aber auch ok.

Vorschlag:

  • zip, strictZip, unzip, iterateN, iterateWhile, lefts(), rights(), findFirst erst einmal weglassen / rausschmeißen

  • List umbenennen in “NecoList”

  • “all” und “any” in NecoList implementieren

  • neue Utility-Klasse “NecoLists”

  • “zipWith”, “strinctZipWith”, “toList”, “fromList” sowie “leftRights” als “eithers” in NecoLists verschieben / implementieren

  • “unpack” als “flatten” in NecoLists, sowie überschriebene Versionen, die auf List<Iterable> und List<A[]> arbeiten

(*) Kann man z.B. mit list.filter(Either::isLeft).map(Either::left) leicht selbst bauen

Hab’ jetzt endlich mal kurz über den Code geschaut, aber wirklich “produktiv” werden kann ich noch nicht (außerdem hab’ ich mir dummerweise nur den master gezogen :rolleyes: da ist natürlich fast nix drin - und an den anderen komm’ ich von hier aus gerade nicht ran…)

[QUOTE=Landei]Stimmt, da habe ich zu kompliziert gedacht. Ich finde das hier noch einfacher:
Noch eine Stil-Frage: Wie gehen wir mit der Frage “statisch oder nicht” um? Manche Methoden sind klar statisch (etwa of() oder unzip()), aber bei anderen wie cons() und zip() ist das nicht so klar. Sollen wir nur das statisch machen, was **wirklich **statisch sein muss (dann müssten wir cons() ändern)? Oder gibt es ein anderes sinnvolles Kriterium?
[/QUOTE]

Diese Frage hatte ich vor langer Zeit im anderen Forum mal gestellt: Wann nimmt man eine Methode in ein Interface auf, und wann bietet man es als statische Utility-Methode an? Kurz rekapitulierend (auf Basis des Standes von damals!) : Aus “typtheoretischer” Sicht wäre es ja “schön”, wenn ein Interface minimal wäre: Man würde nur die minimale Menge von Methoden implementieren, die unbedingt notwendig ist. Bei der Java Collections List wäre das nur get, add und size - alles andere kann auf Basis dieser beiden Methoden implementiert werden (siehe AbstractList). Damit wäre das Interface sehr leicht zu implementieren. Aber natürlich wäre eine API damit schrecklich unbequem zu verwenden. Für einfache Verwendung und Ausnutzung von Polymorphie sollte in das Interface alles aufgenommen werden “was man so braucht”. Z.B. indexOf, addAll, sort - hey, aber sort ist z.B. nicht im List-Interface, obwohl gerade da eine Polymorphe Implementierung wichtig wäre. (Jetzt ist das durch das RandomAccess interface gelöst, was ich etwas krampfig finde).

Aaaaber: Ich glaube, dass sich die Prioritäten da durch die default-Methoden deutlich verschieben. Ich denke (subjektiv und unfundiert), dass man jetzt deutlich “freier” ist in bezug auf die Frage, was man alles ins Interface mit aufnimmt und was man als statische Methode anbietet. (Die Entscheidung ist nicht mehr so endgültig…).

Deswegen denke ich: Man könnte Methoden immer als statische utility-Methoden anbieten/implementieren (wenn das ohne “Krämpfe” möglich ist). Am Beispiel der Collections: Sowas wie indexOf, addAll usw. könnten statische Utility-Methoden sein. Damit ist es später sehr leicht, die Methoden als default-Methoden ins Interface aufzunehmen - indem man die default-Methode einfach an die statische Methode weiterdelegiert. Dann wird höchstens die Frage relevant(er), ob man das gleich von Beginn an macht, UND (damit verbunden) ob man die statische Methode gleich public macht, oder nur package private. (Natürlich erstmal immer letzteres - “When in doubt, leave it out”).


Zu der Methode NecoLists#toList, die jetzt aufgezählt wurde: Ich gehe davon aus, dass das eine Konvertierung ist. Ich fände es für die Interoperabilität aber auch sehr wichtig, eine Methode NecoLists#asList anzubieten, die eine List liefert, die eine (zwangsläufig unmodifiable) View auf eine NecoList ist.

someOldMethodExpectingList(NecoLists.asList(necoList));

// Oder
someOldMethodExpectingList(necoList.asList());
// (das ist ja noch die Frage ;-))

[QUOTE=Marco13]
Zu der Methode NecoLists#toList, die jetzt aufgezählt wurde: Ich gehe davon aus, dass das eine Konvertierung ist. Ich fände es für die Interoperabilität aber auch sehr wichtig, eine Methode NecoLists#asList anzubieten, die eine List liefert, die eine (zwangsläufig unmodifiable) View auf eine NecoList ist.

someOldMethodExpectingList(NecoLists.asList(necoList));

// Oder
someOldMethodExpectingList(necoList.asList());
// (das ist ja noch die Frage ;-))
```[/QUOTE]

Es gibt eine Alternative: Man könnte NecoList auch gleich List implementieren lassen. Natürlich würden dann viele Methoden UnsupportedOperationException liefern, und es gäbe potentiell Name-Clashes, trotzdem wäre es natürlich praktisch.