Komponierbarkeit mit Bedarfsauswertung
Heute soll es um eine Eigenschaft gehen, die in einigen funktionalen Programmiersprachen helfen, die Funktionen höchst wiederverwendbar zu gestalten - ohne immense Einbußen in der Geschwindigkeit hinnehmen zu müssen. Es handelt sich dabei um die Bedarfsauswertung (engl. lazy evaluation) Inspiriert hat mich hierbei der Artikel Heap, heap, hooray! von Tobias Schlitt, der folgendes Problem in PHP löst: Gib mir die k kleinsten Elemente aus einem Stream. Durch Haskells Bedarfsauswertung kann ich vom Stream abstrahieren und das Problem als Liste auffassen. Das Problem heißt dann: Gib mir die k kleinsten Elemente einer Liste. Hierfür werde ich den naiven Ansatz verwenden und zeigen, dass Naivität in Haskell nicht immer bestraft wird.
Der Code besteht aus den Standardfunktionen take und partition sowie aus einem selbstimplementierten Quicksort. Für das Verständnis habe ich die (interne) Implementierung der beiden Funktionen und eine Eigenschaft von partition angegeben.
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
-- partition satisfies: partition p xs == (filter p xs, filter (not . p) xs)
partition p xs = foldr (select p) ([],[]) xs
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort greater
where (smaller,greater) = partition (<= x) xs
bottom k = take k . qsort
Anhand dieser Funktionen lässt sich eine Auswertungsreihenfolge finden, mit der man die drei kleinsten Elemente der Liste [8,2,1,17,18,12,4,13,5,20,10,11,14,15,19,3,6,7,16,9] ermitteln kann.
bottom 3 [8,2,1,17,18,12,4,13,5,20,10,11,14,15,19,3,6,7,16,9]
~> { Def. bottom }
take 3 . qsort $ [8,2,1,17,18,12,4,13,5,20,10,11,14,15,19,3,6,7,16,9]
~> { Def. $ }
take 3 $ qsort [8,2,1,17,18,12,4,13,5,20,10,11,14,15,19,3,6,7,16,9]
~> { Def. qsort }
take 3 $ qsort smaller ++ [8] ++ qsort greater
~> { smaller auswerten }
take 3 $ qsort [2,1,4,5,3,6,7] ++ ...
~> { Def. qsort }
take 3 $ qsort smaller ++ [2] ++ qsort greater ++ ...
~> { smaller auswerten }
take 3 $ qsort [1] ++ [2] ++ qsort greater ++ ...
~> { Def. qsort }
take 3 $ qsort [] ++ [1] ++ qsort [] ++ [2] ++ qsort greater ++ ...
~> { Def. qsort }
take 3 $ [] ++ [1] ++ [] ++ [2] ++ qsort greater ++ ...
~> { ++ anwenden }
take 3 $ [1,2] ++ qsort greater ++ ...
~> { take solange anwenden wie möglich }
1:2:(take 1 $ qsort greater ++ ...)
~> { greater auswerten }
1:2:(take 1 $ qsort [4,5,3,6,7] ++ ...)
~> { Def. qsort }
1:2:(take 1 $ qsort smaller ++ [4] ++ qsort greater ++ ...)
~> { smaller auswerten }
1:2:(take 1 $ qsort [3] ++ ...)
~> { Def. qsort }
1:2:(take 1 $ qsort [] ++ [3] ++ qsort [] ++ ...)
~> { Def. qsort }
1:2:(take 1 $ [] ++ [3] ++ [] ++ ...)
~> { ++ anwenden }
1:2:(take 1 $ [3] ++ ...)
~> { Def. take }
1:2:3:(take 0 $ ...)
~> { Def. take }
1:2:3:[]
~> { Listenkonstruktor }
[1,2,3]
Die Variablen smaller bzw. greater werden erst ausgewertet, wenn sie wirklich benötigt werden, d.h. konkret wurden nur die ersten drei Elemente der Liste sortiert - und nicht die gesamte Liste. Wenn die Anzahl der gesuchten Elemente deutlich kleiner als die Liste, spart man (im Allgemeinen) deutlich mehr Zeit, als man bei einem naiven Ansatz erwarten würde.
Nichtsdestotrotz kann dieser Code nicht mit einer imperativen Implementierung, die für einen bestimmten Einsatz konzipiert wurde, mithalten. Dafür sind Funktionen durch die Bedarfsauswertung besser komponierbar mit verhältnismäßig kleinen Geschwindigkeitseinbußen.