Verwenden Sie falten weniger effizient als Standard-Rekursion

Question

Ich gehe gerade durch das Lernen Sie ein Haskell Buch und ich bin neugierig, wie dieses besondere Beispiel funktioniert. Das Buch zeigt zunächst eine Implementierung von findKey traditionelle Rekursion:

findKey :: (Eq k) => k -> [(k,v)] -> Maybe v 
findKey key [] = Nothing 
findKey key ((k,v):xs) = if key == k 
          then Just v 
          else findKey key xs 

Das Buch dann mit einer kürzeren Implementierung folgt bis mit foldr

findKey :: (Eq k) => k -> [(k,v)] -> Maybe v 
findKey key = foldr (\(k,v) acc -> if key == k then Just v else acc) Nothing 

Mit der Standard-Rekursion, sollte die Funktion sofort zurück, sobald es trifft das erste Element mit dem angegebenen Schlüssel. Wenn ich die foldr Implementierung richtig verstehe, wird sie jedes Mal über die gesamte Liste iterieren, auch wenn sie mit dem ersten Element übereinstimmt, auf das sie gestoßen ist. Das scheint kein sehr effizienter Weg zu sein, mit dem Problem umzugehen.

Gibt es etwas, über das ich nicht weiß, wie die foldr Implementierung funktioniert? Oder gibt es irgendeine Art von Magie in Haskell, die diese Implementierung nicht ganz so ineffizient macht, wie ich denke?

Answer 1

1. foldr wird mit Standardrekursion geschrieben.

2. Der rekursive Aufruf von foldr ist in acc versteckt. Wenn Ihr Code acc nicht verwendet, wird er nie berechnet (weil Haskell faul ist). So ist die foldr Version effizient und wird auch früh zurückkehren.

Hier ist ein Beispiel dieser demonstriert:

Prelude> foldr (\x z -> "done") "acc" [0 ..] 
"done" 

Dieser Ausdruck "done" sofort zurückkehrt, obwohl die Eingabeliste unendlich lang ist.

---

Wenn foldr ist definiert als:

foldr f z (x : xs) = f x (foldr f z xs) 
foldr _ z [] = z 

, dann geht die Auswertung über

f x (foldr f z xs) 
    where 
    f = \x z -> "done" 
    x = 0 
    z = "acc" 
    xs = ... -- unevaluated, but is [1 ..] 

die

ist

(\x z -> "done") 0 (foldr (\x z -> "done") "acc" [1 ..]) 

die in "done" dreht, weil Die erste Funktion verwendet z nicht, so dass der rekursive Aufruf nie benötigt wird.

Answer 2

Wenn ich die foldr-Implementierung richtig verstehe, wird sie jedes Mal über die gesamte Liste iterieren, auch wenn sie mit dem ersten Element übereinstimmt, auf das sie gestoßen ist.

Das ist falsch. foldr wertet die Liste nur so oft wie nötig aus.

z.

foldr (&&) True [True, False, error "unreached code here"] 

kehrt False da der Fehler nie ausgewertet wird, genau wie in

(True && (False && (error "unreached code here" && True))) 

der Tat, da das Ende der Liste nie erreicht ist, können wir auch schreiben

foldr (&&) (error "end") [True, False, error "unreached code here"] 

und Erhalten Sie immer noch False.

Answer 3

Hier ist Code, der zeigt, dass foldr tut in der Tat "Kurzschluss" die Auswertung von findKey:

import Debug.Trace 

findKey :: (Eq k) => k -> [(k,v)] -> Maybe v 
findKey key = foldr (\(k,v) acc -> if key == k then Just v else acc) Nothing 

tr x = trace msg x 
    where msg = "=== at: " ++ show x 

thelist = [ tr (1,'a'), tr (2,'b'), tr (3, 'c'), tr (4, 'd') ] 

Ein Beispiel für findKey in GHCI ausgeführt wird:

*Main> findKey 2 thelist 
=== at: (1,'a') 
=== at: (2,'b') 
Just 'b' 
*Main> 

Answer 4

Denken Sie an foldr die Verwendung von folgende Definition (unter Verwendung der Standardrekursion):

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f e [] = e 
foldr f e (x:xs) = f x (foldr f e xs) 

Die dritte Zeile zeigt, dass die zweite Implementierung für findKey beim Finden der ersten Übereinstimmung zurückkehrt.

---

Als Nebenbemerkung: Angenommen, Sie hatte die folgende Definition (die nicht identisch Funktionalität hat) für findKey (als Übung Sie die Definition mit foldr umschreiben möchten):

findKey :: (Eq k) => k -> [(k,v)] -> [v] 
findKey key [] = [] 
findKey key ((kHead, vHead):rest) = if (key == kHead) then vHead:(findKey key rest) else findKey key rest 

Jetzt Sie könnten denken, dass dies die gesamte Eingabeliste durchlaufen würde. Abhängig davon, wie Sie diese Funktion aufrufen, kann es vorkommen, dass sie die gesamte Liste durchläuft, aber gleichzeitig auch effizient die erste Übereinstimmung ergibt. Aufgrund lazy evaluation Haskells des folgenden Code:

head (findKey key li) 

werden Sie das erste Spiel (unter der Annahme, dass es eine ist) mit der gleichen Effizienz wie Ihr erstes Beispiel.

Answer 5

foldr f z [a,b,c,...,n]     == 
a `f` (b `f` (c `f` (... (n `f` z) ...))) == 
f a (foldr f z [b,c,...,n])    == 
f a acc where acc = foldr f z [b,c,...,n] 

So wenn Ihre f kehrt vorforcingacc, acc nicht gezwungen bleibt, das heißt kein Teil der Liste Argument über seine Kopfelement a zugegriffen wird, wie z.B. wenn Sie

f a acc = ... 

Wenn auf der anderen Seite Ihre f ist ihr zweites Argument zwingen, z.B.wenn es als

f a (x:xs) = ... 

definiert ist dann die accwird vor f gezwungen beginnt seine Arbeit, und die Liste wird vor der Verarbeitung vollständig zugegriffen werden beginnt - ganz, weil acc = f b acc2 und dass Aufruf von f muss erzwingen sein zweites Argument, acc2, so kann sein Wert, acc, gezwungen werden (pattern-matched mit (x:xs), das ist); und so weiter.