W Haskell, wydajności i gdzie wiązanie

Question

Ja tylko nauka Haskell i napisał dwa programy z witryny samouczka, tak że

maximumnowhere :: (Ord a) => [a] -> a 
maximumnowhere [] = error "empty" 
maximumnowhere [x] = x 
maximumnowhere (x:xs) = if x > maximumnowhere xs then x else maximumnowhere xs 

i

maximumwhere :: (Ord a) => [a] -> a 
maximumwhere [] = error "empty" 
maximumwhere [x] = x 
maximumwhere (x:xs) = if x > maximum' then x else maximum' where maximum' = maximumwhere xs 

Myślałem, te dwa programy są dość równoważne, ponieważ myślałem, że miejsce wiązania tylko zastępuje zmienną zawartością. ale kiedy uruchomiłem go w ghci, pierwszy był znacznie wolniejszy od drugiego, szczególnie w przypadku macierzy o długości powyżej 25 lat. Prawdopodobnie, gdzie powiązanie powoduje ogromną różnicę wydajności, ale nie wiem dlaczego. Czy ktoś może mi to wyjaśnić?

Answer 1

Nie, nie są one równoważne. let i where wprowadzenie sharing, co oznacza, że ​​wartość jest oceniana tylko raz. Kompilator na ogół nie podzieli wyniku dwóch identycznych wyrażeń, chyba że je przekażesz, ponieważ nie może ogólnie stwierdzić, czy wymiana czasu w przestrzeni czy czasie jest korzystna czy nie.

Tak więc, pierwszym program do połączeń na dwa rekurencyjne iteracji, co O (2^n), a drugi ma tylko jeden za iteracji tj O (n). Różnica między nimi jest ogromna. Na n = 25, pierwsze efekty programu w ponad 33 mln wywołań rekurencyjnych podczas gdy drugi ma tylko 25.

Więc morał tej historii jest to, że jeśli chcesz dzielić, trzeba poprosić o to przy użyciu let lub where.