Alle Kombinationen von Werten einer Liste
Sascha.M...@gmail.com
ich möchte gerne alle Kombinationen von Werten einer Liste ermitteln,
ich weiß aber nicht, wie ich das effizient implementieren kann.
Habt ihr Lösungen für das Problem?
Vielen Dank und Grüße,
Sascha
Achim Peters
> ich möchte gerne alle Kombinationen von Werten einer Liste ermitteln,
Also alle Permutationen? Oder auch Kombinationen, in denen nicht alle
Werte vorkommen.
> ich weiß aber nicht, wie ich das effizient implementieren kann.
> Habt ihr Lösungen für das Problem?
Permutationen lassen sich sehr schön rekursiv lösen.
Ist Deine Liste einelementig, bist Du fertig. Ansonsten:
Vertausche der Reihe nach das erste Element mit allen weiteren
Bilde jedesmal alle Permutationen der Elemente ab dem zweiten.
HTH
Bye
Achim
Sascha.M...@gmail.com
nee, keine Permutationen, die Reihenfolge der Ergebnisse ist egal,
d.h. {a, b, c} = {b, c, a}. Ausserdem sollen auch Kombinationen
auftreten, in denen nicht alle Werte vorkommen.
Vielen Dank und Grüße,
Sascha
On 4 Jul., 15:33, Achim Peters <achimpet...@gmx.de> wrote:
Ralf Ullrich
Ich gehe mal (anders als Achim) davon aus du meinst diese Bedeutung des
Wörtchens "Kombinationen":
http://de.wikipedia.org/wiki/Kombinatorik#Kombination_ohne_Zur.C3.BCcklegen
Dann könntest du das so machen wie im angehängten (ungetesteten) Code, den
du aber besser nicht als Lösung deiner Hausaufgabe einreichst, wenn dir
eine gute Note lieb ist.
Hmm. Obwohl, vielleicht gibt's ja Extrapunkte für Eleganz und Schönheit,
und schön isses ja wohl, zu schreiben:
List<E> list = ...
for (List<E> combination : new Combinator<E>(list)) {
// do something with every possible combination
}
;-)
cu
package de.jnana.dclj.algo.combi;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
public class CombinatorDemo {
public static <E> void main(String[] args) {
List<E> list = null;
for (List<E> combination : new Combinator<E>(list)) {
// do something with every possible combination
}
}
public static class Combinator<E> implements Iterable<List<E>> {
final List<E> data;
public Combinator(List<E> data) {
this.data = new ArrayList<E>(data);
}
@Override
public Iterator<List<E>> iterator() {
return new Iterator<List<E>>() {
private BigInteger a = BigInteger.ZERO;
private BigInteger b;
@Override
public boolean hasNext() {
if (b == a) {
a = BigInteger.ONE.add(b);
}
return a.bitLength() <= data.size();
}
@Override
public List<E> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
b = a;
List<E> rv = new ArrayList<E>(a.bitCount());
int l = a.bitLength();
for (int i = 0; i < l; i++) {
if (a.testBit(i)) {
rv.add(data.get(i));
}
}
return rv;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
}
Achim Peters
Bitte kein TOFU (Text oben, Fullquote unten) posten, sondern
abschnittsweise sinnvoll gekürzt quoten, dann antworten, dann wieder
quoten, etc. Siehe auch http://learn.to/quote
> nee, keine Permutationen, die Reihenfolge der Ergebnisse ist egal,
> d.h. {a, b, c} = {b, c, a}. Ausserdem sollen auch Kombinationen
> auftreten, in denen nicht alle Werte vorkommen.
Wieso "außerdem"? Ausser der Ursprungsliste sind es dann ja
_ausschließlich_ Kombinationen, in denen nicht alle Werte vorkommen,
wenn ich Dich richtig verstehe.
Aus {a, b, c} soll dann
{a}
{b}
{c}
{a, b}
{a, c}
{b, c}
{a, b, c}
und
{}
werden?
Bye
Achim
Sascha.M...@gmail.com
> Sascha.Moeller...@gmail.com wrote:
> >Hallo,
>
> >ich möchte gerne alle Kombinationen von Werten einer Liste ermitteln,
> >ich weiß aber nicht, wie ich das effizient implementieren kann.
> >Habt ihr Lösungen für das Problem?
>
> >Vielen Dank und Grüße,
> >Sascha
>
> Ich gehe mal (anders als Achim) davon aus du meinst diese Bedeutung des
> Wörtchens "Kombinationen":
>
Hallo,
damit funktioniert es, wunderbar, danke sehr. Und nein, es ist keine
Hausaufgabe, die ich abgeben muss :-)
Frank Buss
> nee, keine Permutationen, die Reihenfolge der Ergebnisse ist egal,
> d.h. {a, b, c} = {b, c, a}. Ausserdem sollen auch Kombinationen
> auftreten, in denen nicht alle Werte vorkommen.
Du meinst also die Potenzmenge einer Menge. In Haskell könnte man es z.B.
so lösen:
powerset [] = [[]]
powerset (x:xs) = let p = powerset xs in p ++ map (x:) p
(hier gefunden:
http://www.polyomino.f2s.com/david/haskell/hs/CombinatoricsGeneration.hs.txt
)
Verwendung:
powerset [1,2,3]
[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
In Java geht das genauso, ist nur ein klein wenig umständlicher:
public class Powerset {
public static IntLists powerset(IntList list) {
Iterator<Integer> it = list.listIterator();
if (it.hasNext()) {
Integer x = it.next();
IntList xs = list.rest();
IntLists p = powerset(xs);
return p.append(p.mapPrepend(x));
} else {
IntLists result = new IntLists();
result.add(new IntList());
return result;
}
}
public static void main(String args[]) {
int[] list = new int[] { 1, 2, 3 };
IntList ilist = new IntList();
for (Integer i : list) ilist.add(i);
IntLists p = powerset(ilist);
System.out.println(p);
}
}
Ausgabe: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
Zusätzlich musste ich noch folgende Hilfsklassen verwenden:
class IntList extends LinkedList<Integer> {
// liefert eine neue IntList mit allen Elementen bis auf das erste
public IntList rest() {
Iterator<Integer> it = listIterator();
IntList result = new IntList();
if (it.hasNext()) it.next();
while (it.hasNext()) result.add(it.next());
return result;
}
}
class IntLists extends LinkedList<IntList> {
// liefert ein neues IntLists objekt, mit den Elementen dieses
// IntLists-Objekt und den Elementen des übergebenen Objekts angehangen
public IntLists append(IntLists lists) {
IntLists result = new IntLists();
result.addAll(this);
result.addAll(lists);
return result;
}
// liefert ein neues IntLists objekt, bei dem bei jedem IntList-Objekt
// i vorne angehangen wurde
public IntLists mapPrepend(Integer i) {
IntLists result = new IntLists();
for (IntList list : this) {
IntList newList = new IntList();
newList.add(i);
newList.addAll(list);
result.add(newList);
}
return result;
}
}
Und jetzt beantworte bitte die Frage, warum immer noch so viele Leute Java
statt Haskell verwenden :-)
--
Frank Buss, f...@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Jens Müller
> Hallo,
>
> ich möchte gerne alle Kombinationen von Werten einer Liste ermitteln,
Also die Potenzmenge, wie schon geschrieben hätte.
> ich weiß aber nicht, wie ich das effizient implementieren kann.
Je nachdem, was Du damit vorhast, würde ich uU davon absehen, das
Ergebnis zu materialisieren ...
Ralf Ullrich
>[Haskell]
>
>powerset [] = [[]]
>powerset (x:xs) = let p = powerset xs in p ++ map (x:) p
>
[...]
>Verwendung:
>
>powerset [1,2,3]
>[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
Dann mach doch gleich Prolog, um es etwas klassischer zu halten:
combination([], []).
combination([H|T], P) :- combination(T,P).
combination([H|T], [H|P]) :- combination(T,P).
Verwendung:
?- combination([1,2,3], R).
R=[]
R=[3]
R=[2]
R=[2,3]
...
oder auch:
?- findall(X, combination([1,2,3], X), R).
R=[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
(Komisch warum bloß kommen die Ergebnisse in der selben Reihenfolge wie
bei dir ;-) )
>Und jetzt beantworte bitte die Frage, warum immer noch so viele Leute Java
>statt Haskell verwenden :-)
Oder warum keiner Prolog verwendet?
cu
Frank Buss
> Dann mach doch gleich Prolog, um es etwas klassischer zu halten:
>
> combination([], []).
> combination([H|T], P) :- combination(T,P).
> combination([H|T], [H|P]) :- combination(T,P).
>
> Verwendung:
>
> ?- combination([1,2,3], R).
>
> R=[]
> R=[3]
> R=[2]
> R=[2,3]
> ...
Das sieht auch interessant aus. Wie würde die "Übersetzung" in Java
aussehen?
Ralf Ullrich
>Ralf Ullrich wrote:
>
>>Dann mach doch gleich Prolog, um es etwas klassischer zu halten:
>>
>> combination([], []).
>> combination([H|T], P) :- combination(T,P).
>> combination([H|T], [H|P]) :- combination(T,P).
>>
>>Verwendung:
>>
>> ?- combination([1,2,3], R).
>>
>> R=[]
>> R=[3]
>> R=[2]
>> R=[2,3]
>> ...
>
>Das sieht auch interessant aus. Wie würde die "Übersetzung" in Java
>aussehen?
Hmm. Das ist gar nicht so einfach, weil bei Prolog ja nicht zwischen In-
und Out-Parametern unterschieden wird. So könnte ich in Prolog auch die
Frage stellen, ob eine bestimmte Menge eine Kombination einer anderen ist:
?- combination([1,2,3],[3]).
true.
?- combination([1,2,3],[4]).
false.
Wobei die hier vorliegende Implementierung noch unnötigerweise die
Reihenfolge beachtet, daher:
?- combination([1,2,3],[2,3]).
true.
?- combination([1,2,3],[3,2]).
false.
Bei der Übersetzung in eine prozedurale Sprache müsste man nun eigentlich
jedes Fließmuster neu übersetzen. Was aber auch nicht so einfach ist, weil
Parameter ja auch teilweise bestimmt sein können. Zum Beispiel könnte ich
nach allen zwei-elementige Kombinationen fragen:
?- combination([1,2,3],[A,B]).
A=2, B=3.
A=1, B=3.
A=1, B=2.
no more solutions.
Beschränken wir uns aber mal auf das Fließmuster combination(i,o), also
der Frage nach allen Kombinationen einer gegebenen Menge.
Das nächste ist dann, dass diese combination(i,o)-Klausel die Lösungen ja
zunächst nacheinander abliefert, was man wohl nur mit Continuations in
schönen prozeduralen Code umschreiben kann. In Java müsste man dagegen
wohl einen Iterator bemühen und den Code der obigen drei Prolog-Zeilen
zwischen Konstruktor und den zwei Methoden hasNext() und next() verteilen.
Das sähe dann etwa so aus:
public class Combination<E> implements Iterator<List<E>> {
E head;
List<E> tail;
Iterator<List<E>> iter;
public Combination(List<E> list) {
if (list.isEmpty()) {
head = tail = null;
iter = this;
} else {
head = list.get(0);
tail = list.subList(1,list.size());
iter = new Combination(tail);
}
}
public boolean hasNext() {
return (tail!=null) || (iter==this)
|| ((iter!=null) && (iter.hasNext()));
}
public List<E> next() {
if (!hasNext() || (iter==null)) {
throw new NoSuchElementException();
}
if (iter==this) {
iter==null;
return Collections.emptyList();
}
if (!iter.hasNext()) {
iter = new Combination(tail);
tail = null;
}
List<E> rv = new ArrayList<E>();
if (tail==null) {
rv.add(head);
}
rv.addAll(iter.next());
return rv;
}
public void remove() {
throw new UnsupportedOperationException();
}
}
(Ungetestet und im Newsreader getippt.)
Am einfachsten versteht man aber ein Prolog-Programm, wenn man es wie eine
Mathematische Definition liest (was es letzlich auch ist, von so
Absonderheiten wie cut/0 mal abgesehen):
combination([], []).
Die leere Menge hat genau eine Kombination, und das ist die leere Menge.
-oder-
combination([H|T], P) :- combination(T,P).
Für eine Menge, die aus einem Element H und der Restmenge T besteht, ist
eine Menge P dann eine Kombination, wenn P eine Kombination von T ist.
-oder-
combination([H|T], [H|P]) :- combination(T,P).
Für eine Menge, die aus einem Element H und der Restmenge T besteht, ist
die Menge, die aus dem Element H und der Restmenge P besteht, dann eine
Kombination, wenn P eine Kombination von T ist.
cu
Ralf Ullrich
>Frank Buss wrote:
>
>>Ralf Ullrich wrote:
>>
>>>Dann mach doch gleich Prolog, um es etwas klassischer zu halten:
>>>
>>> combination([], []).
>>> combination([H|T], P) :- combination(T,P).
>>> combination([H|T], [H|P]) :- combination(T,P).
>>>
>>>Verwendung:
>>>
>>> ?- combination([1,2,3], R).
>>>
>>> R=[]
>>> R=[3]
>>> R=[2]
>>> R=[2,3]
>>> ...
>>
>>Das sieht auch interessant aus. Wie würde die "Übersetzung" in Java
>>aussehen?
>
>Das nächste ist dann, dass diese combination(i,o)-Klausel die Lösungen ja
>zunächst nacheinander abliefert, was man wohl nur mit Continuations in
>schönen prozeduralen Code umschreiben kann. In Java müsste man dagegen
>wohl einen Iterator bemühen und den Code der obigen drei Prolog-Zeilen
>zwischen Konstruktor und den zwei Methoden hasNext() und next() verteilen.
Mir fällt gerade ein, statt dem Pull-Modus des Iterators, könnte man ja
auch einen Push-Modus schreiben, dann allerdings sieht die Übersetzung des
Prolog-Programms geradezu simpel aus:
interface Sink<E> {
void accept(E e);
}
static <E> void combination(List<E> list, final Sink<List<E>> sink) {
// combination([], []).
if (list.isEmpty()) {
sink.accept(Collections.emptyList());
return;
}
// combination([H|T], P) :- combination(T,P).
List<E> tail = list.subList(1,list.size());
combination(tail, new Sink<List<E>>() {
void accept(List<E> p) {
sink.accept(p);
}
});
// combination([H|T], [H|P]) :- combination(T,P).
final E head = list.get(0);
combination(tail, new Sink<List<E>>() {
void accept(List<E> p) {
List<E> hp = new ArrayList<E>();
hp.add(head);
hp.addAddl(p);
sink.accept(hp);
}
});
}
Oder mit eigener Prolog-tauglicherer LinkList-Klasse:
public class LinkList<E> {
private static final LinkList<?> NIL = new LinkList();
public final E head;
public final LinkList<E> tail;
@SuppressWarnings("unchecked")
static <E> LinkList<E> nil() {
return (LinkList<E>) NIL;
}
private LinkList() {
head = null;
tail = null;
}
public LinkList(E head, LinkList<E> tail) {
if ((head==null) || (tail==null)) {
throw new IllegalArgumentException();
}
this.head = head;
this.tail = tail;
}
public boolean isNil() {
return this == nil();
}
}
static <E> void combination(final LinkList<E> list,
final Sink<LinkList<E>> sink) {
// combination([], []).
if (list.isNil()) {
sink.accept(LinkList.nil());
return;
}
// combination([H|T], P) :- combination(T,P).
combination(list.tail, new Sink<LinkList<E>>() {
void accept(LinkList<E> p) {
sink.accept(p);
}
});
// combination([H|T], [H|P]) :- combination(T,P).
combination(list.tail, new Sink<List<E>>() {
void accept(List<E> p) {
sink.accept(new LinkList<E>(list.head, p));
}
});
}
Wobei ich noch anmerken möchte, dass ich die mittlere Klausel zur
Verdeutlichung so geschrieben habe:
// combination([H|T], P) :- combination(T,P).
combination(list.tail, new Sink<LinkList<E>>() {
void accept(LinkList<E> p) {
sink.accept(p);
}
});
Obwohl folgende Optimierung in der prozeduralen Form nahe liegt:
// combination([H|T], P) :- combination(T,P).
combination(list.tail, sink);
cu
Ralf Ullrich
>Frank Buss wrote:
>
>>[Haskell]
>>
>>powerset [] = [[]]
>>powerset (x:xs) = let p = powerset xs in p ++ map (x:) p
>>
>[...]
>>Verwendung:
>>
>>powerset [1,2,3]
>>[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
Hach, kaum sind grauen Zellen mal etwas aufgelockert, erinnert man sich
doch wieder an 20 Jahre alten Käse, als wäre es erst gestern gewesen.
Inzwischen ist mir wieder eingefallen, wie man dein powerset in Prolog
ohne schwere Kaliber wie findall schreiben kann:
Zunächst mal muss ich Prolog sagen, wie man zwei Listen A und B zu einer
neuen Liste C zusammenfügt, also merge(A,B,C):
merge([], L, L).
merge([H|T], L1, [H|L2]) :- merge(T,L1,L2).
Dieses merge ist wohl das was du Haskell mit dem infix-Operator '++' als
Built-In hast?
Ebenso muss ich Prolog sagen, wie man jeder Liste in einer Liste von
Listen, jeweils ein Element voranstellt, was du wohl mit "map (x:) p" in
Haskell ausdrücken kannst:
prepend(X, [], [[X]]).
prepend(X, [H|T1], [[X|H]|T2]) :- prepend(X, T1, T2).
Und damit sieht nun powerset fast schon wie in Haskell aus:
powerset([], [[]]).
powerset([H|T], P3) :- powerset(T, P1),
prepend(H, P1, P2),
merge(P1, P2, P3).
Dass allerdings alles in Java zu übersetzen, ist mir selbst mit dem
Push-Modus-Trick und LinkList-Implementation jetzt zuviel Mühe. Aber wenn
sich jemand versuchen will, korrigiere ich es gerne. ;-)
Schön war der Ausflug in die alten Zeiten.
cu
ma...@heinerkuecker.de
> Du meinst also die Potenzmenge einer Menge. In Haskell könnte man es z.B.
> so lösen:
>
> powerset [] = [[]]
>
>
> public class Powerset {
> public static IntLists powerset(IntList list) {
Kannst Du das mal etwas genauer erklären.
Wie enstehen die Listen, die sich jeweils unterscheiden ?
Die erste Lösung von Ralf war zu verstehen.
Klar, Binärzahl, im Wertebereich werden alle Kombinationen
einmal verwendet.
Die ganzen Haskell- und Prolog-Sachen habe ich eh nicht verstanden.
Gruss
Heiner
Frank Buss
> Die erste Lösung von Ralf war zu verstehen.
> Klar, Binärzahl, im Wertebereich werden alle Kombinationen
> einmal verwendet.
>
> Die ganzen Haskell- und Prolog-Sachen habe ich eh nicht verstanden.
Es ist ein rekursiver Ansatz: Zunächst mal definieren wir, daß die
Potenzmenge einer leeren Menge eine Menge mit der leeren Menge als Element
ist. Dann definieren wir den Rekursionsschritt: Um die Potenzmenge einer
Menge m zu berechnen, berechnen wir zunächst die Potenzmenge p der Menge
m', die definiert ist als die Menge m ohne das erste Element. Das erste
Element der Menge m nennen wir x. Wir fügen dann zu jedem Element der Menge
p (was ja jeweils eine Menge ist) das Element x hinzu und liefern die
Vereinigung dieser dann entstehenden Menge mit p zurück.
Anhand von Beispielen kann man sich leicht klar machen, daß man damit die
Potenzmenge baut. Mittels vollständiger Induktion kann man das bestimmt
auch beweisen.
Dieser Algorithmus ist auch in dem englischsprachigen Wikipedia-Artikel
beschrieben, wie ich gerade sehe: http://en.wikipedia.org/wiki/Power_set
Das Haskell-Programm formuliert diesen Algorithmus sehr knapp und elegant,
mein Java-Programm macht dasselbe, nicht so elegant.
ma...@heinerkuecker.de
> Es ist ein rekursiver Ansatz: Zunächst mal definieren wir, daß die
> Dieser Algorithmus ist auch in dem englischsprachigen Wikipedia-Artikel
> beschrieben, wie ich gerade sehe:http://en.wikipedia.org/wiki/Power_set
Aha, anhand des Artikels und Deiner Erkärung habe ich es
wahrscheinlich gerafft:
0, 1, 2
1. Schritt die 0
[] leer
[0]
2. Schritt die 1
wie vorher
[] leer
[0]
+
[1]
[1,0]
3. Schritt die 2
wie vorher
[]
[0]
[1]
[1,0]
+
[2]
[2,0]
[2,1]
[2,1,0]
Alles klar.
Gute Nacht
Heiner
Michael Osipov
> Sascha.M...@gmail.com wrote:
>
>> nee, keine Permutationen, die Reihenfolge der Ergebnisse ist egal,
>> d.h. {a, b, c} = {b, c, a}. Ausserdem sollen auch Kombinationen
>> auftreten, in denen nicht alle Werte vorkommen.
>
> Du meinst also die Potenzmenge einer Menge. In Haskell könnte man es z.B.
> so lösen:
>
> powerset [] = [[]]
> powerset (x:xs) = let p = powerset xs in p ++ map (x:) p
2 Dumme, ein Gedanke!
Ralf Ullrich
>Dass allerdings alles in Java zu übersetzen, ist mir selbst mit dem
>Push-Modus-Trick und LinkList-Implementation jetzt zuviel Mühe. Aber wenn
>sich jemand versuchen will, korrigiere ich es gerne. ;-)
Nur für den Fall, dass es doch jemand versuchen will, hier noch
fairerweise der Hinweis, dass ich natürlich einen Fehler im
Prolog-Programm habe:
> prepend(X, [], [[X]]).
> prepend(X, [H|T1], [[X|H]|T2]) :- prepend(X, T1, T2).
muss lauten:
prepend(X, [], []).
prepend(X, [H|T1], [[X|H]|T2]) :- prepend(X, T1, T2).
Denn wo kein Element ist, da kann man ja auch nix davor setzen!
cu
kilian heckrodt
Das ist ein Standardproblem, zu dem sich Algorithmen googlen lassen
sollten, eventuell finden sich auch schon fertige Javaklassen.
http://www.merriampark.com/comb.htm
Ansonsten ist hier noch eine Idee fuer den Hausgebrauch:
Eine fixe Groesse von Kombinationen,d.h. Kombinationen der Groesse
k aus der Menge 1..N lassen sich leicht durch k geschachtelte Schleifen
erzeugen. Also z.B. fuer k=2
for(i=1;i<=N;i++) {
for(j=i+1;j<=N;j++) {
Ausgabe(i,j)
}
}
Dies liefert alle Kombination der Groesse 2.
Jetzt ist k ist natuerlich ein Parameter der die Werte
0..N annimmt, d.h. man hat das Problem eine beliebige
Anzahl von geschachtelten schleifen erzeugen zu muessen.
Dies laesst z.B. mit einer Rekursion bewerkstelligen und
jede Rekursionsebene stellt dann eine geschachtelte Schleife
dar. Oder man verwendet ein Array dessen Elemente den
Laufvariablen der geschachtelten Schleife ensprechen und verwaltet bzw.
inkrementiert diese selbst in einer Doppelschleife.
Irgendwo habe ich auch noch ein Codebeispiel rumliegen, falls die bisher
gesposteten Hinweise nicht reichen, kannst du ja noch mal nachfragen.
kilian heckrodt
Sorgen haben) nehme ich mal :)
Frank Buss
> powerset [] = [[]]
> powerset (x:xs) = let p = powerset xs in p ++ map (x:) p
>
> (hier gefunden:
> http://www.polyomino.f2s.com/david/haskell/hs/CombinatoricsGeneration.hs.txt
> )
>
> Verwendung:
>
> powerset [1,2,3]
> [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
Mittlerweile gibt es auch ein paar schöne Lösungen in Lisp:
http://groups.google.de/group/comp.lang.lisp/browse_thread/thread/8315b0f71dd3bc02
In Haskell geht es übrigens auch so:
powerset = filterM (const [True, False])
Allerdings ist man in den Kommentaren bei
http://programming.reddit.com/info/225f0/comments/ teilweise der Meinung,
daß das schlechter Programmierstil ist. Ich habe das in comp.lang.lisp aber
dennoch mal nach Lisp übersetzt.
Unabhängig davon sind Monaden wirklich vielseitig verwendbar, wenn man sie
erstmal verstanden hat. Kann man die auch einfach in Java umsetzen?