Warum endet dieser Haskell-Filter?

Question

Ich verstehe nicht, warum der folgenden Haskell Code unter GHCi endet:

let thereExists f lst = (filter (==True) (map f lst)) /= [] 
thereExists (\x -> True) [1..] 

ich den Anruf nicht immer vollständig zu filtern erwartet habe, da sein zweites Argument unendlich ist, und ich hätte nicht gedacht, den Vergleich könnte stattfinden bis die lhs komplett berechnet war. Was ist los?

Answer 1

Der Vergleich kann stattfinden, bevor die LHS vollständig berechnet ist. Sobald filter ein Element erzeugt hat, kann /= daraus schließen, dass die Liste nicht gleich [] sein kann und sofort True zurückgeben.

/= auf Listen ist so etwas wie dies umgesetzt:

(/=) :: Eq a => [a] -> [a] -> Bool 
[] /= []   = False 
[] /= (y:ys)  = True 
(x:xs) /= []  = True 
(x:xs) /= (y:ys) = (x /= y) || (xs /= ys) 

Da Haskell faul ist, werden wir nur die Argumente so viel bewerten, wie notwendig ist, welche Seite die rechte Hand zu wählen, die wir verwenden werden. Auswertung Ihres Beispiel geht in etwa so:

filter (== True) (map (\x -> True) [1..]) /= [] 
==> (True : (filter (== True) (map (\x -> True) [2..]))) /= [] 
==> True 

Sobald wir wissen, dass das erste Argument von /= ist (1 : something), es für /= im Code über die dritte Gleichung übereinstimmt, so können wir True zurück.

Wenn Sie jedoch versuchen, thereExists (\x -> False) [1..] wird es in der Tat nicht beenden, weil in diesem Fall filter wird nie Fortschritte in Richtung auf die Herstellung eines Konstruktors machen, gegen die wir abgleichen können.

 filter (== True) (map (\x -> False) [1..]) /= [] 
==> filter (== True) (map (\x -> False) [2..]) /= [] 
==> filter (== True) (map (\x -> False) [3..]) /= [] 
... 

und so weiter unendlich.

Abschließend kann thereExists auf einer unendlichen Liste True in endlicher Zeit, aber nie False zurückgeben.