Dlaczego produkt [0 ..] nie ocenia wartości "natychmiast"?

Question

Próbuję zrozumieć lenistwo. Ponieważ 0 pomnożone przez dowolną liczbę to 0, nie powinno być product [0..] oszacować na 0? Próbowałem też foldl (*) 1 [0..] i zdefiniować własne produkt jako

myProduct 0 _ = 0 
myProduct _ 0 = 0 
myProduct a b = a*b 

Dlaczego nie fałda zatrzymać jak tylko 0 znajduje?

Answer 1

Ponieważ operator zwielokrotniający nie wie, że jest połączony łańcuchem, a funkcja zwijania nie zna szczególnego zachowania operatora wielokrotnego dla dowolnego argumentu. Dzięki tej kombinacji musi wyczerpać listę, aby zakończyć zgięcie. W rzeczywistości z tego powodu foldl nie działa w ogóle na nieskończonych listach. foldr ma, ponieważ może rozwinąć funkcję od początku listy.

foldl (*) 1 [0..] -> (((..(((1*0)*1)*2)*3....)*inf 

Najbardziej oddalone mnożenie w folderze case nie może zostać znalezione, ponieważ lista jest nieskończona. Dlatego nie może śledzić łańcucha, aby stwierdzić, że wynik wynosi zero. Może i obliczyć produkt na liście, a produkt pozostaje na poziomie zero, ale nie zakończy się. Jeśli używasz scanl zamiast tego możesz zobaczyć te produkty pośrednie.

foldr (*) 1 [0..] -> 0*(1*(2*(3*((...((inf*1)))...))) 

Zewnętrzna mnożenia w przypadku foldr znajduje się natychmiast, ponieważ reszta listy jest w rzeczywistości lewej jak leniwe thunk. To działa tylko jeden krok:

foldr (*) 1 [0..] -> 0*(foldr (*) 1 [1..]) 

Więc ponieważ operator mnożenia myProduct zwyczaj nie jest ścisłe w drugim argumencie, jeśli pierwszy argument jest zerowy, foldr myProduct 1 [0..] może wypowiedzieć.

Na marginesie funkcja produktu preludium jest ograniczona do list skończonych (i może być zaimplementowana z foldl). Nawet jeśli użyjemy foldr, prawdopodobnie nie będzie to skrót, ponieważ standardowy operator mnożenia jest ścisły; inaczej byłoby kosztowne obliczeniowo w przypadku, gdy produkty nie są ani zerowe, ani powiązane.

-- sum and product compute the sum or product of a finite list of numbers. 

sum, product  :: (Num a) => [a] -> a 
sum    = foldl (+) 0 
product   = foldl (*) 1 

Ponadto istnieje powód, dla którego nie używa foldr; jak mogliśmy zauważyć w funkcji rozszerzeń i skanowania, lewe fałdy można obliczyć, gdy zużywają listę. Prawy zagięcie, jeśli operator nie jest skrótem, musi zbudować wyrażenie tak duże, jak sama lista, aby rozpocząć obliczenia. Ta różnica polega na tym, że jest to najbardziej wewnętrzne wyrażenie, które rozpoczyna obliczenia w ścisłym przypadku, ale najbardziej zewnętrzne wyrażenie, które daje wynik, pozwalając na leniwy przypadek. Lazy vs. non-strict w wiki Haskell może wyjaśnić lepiej niż ja, a nawet wspomnieć, że dopasowanie wzorców, które zostały użyte do opisania skrótu w myProduct, może być ścisłe.

Answer 2

Po przełączeniu pierwsze dwie linie:

myProduct _ 0 = 0 
myProduct 0 _ = 0 
myProduct a b = a*b 

drugi argument zawsze będą oceniane przed pierwszym i nieskończony foldr nie będą już działać.

Ponieważ jest niemożliwe do zdefiniowania myProduct który działa leniwie dla obu argumentów (nie oceniając drugie, jeśli pierwsza jest 0 i nie oceniając pierwsze jeśli drugi jest 0) może jesteśmy lepiej z konieczności * zawsze oceniać zarówno jego argumenty.

Answer 3

Możesz mieć to wygląda następująco:

myproduct xs = foldr op id xs 1 
    where 
    op x r acc = if x==0 then 0 else acc `seq` r (acc*x) 

Jest to prawo krotny że mnoży liczby od lewej, działające w stałej przestrzeni, i zatrzymuje, gdy tylko 0 spotyka.