Dlaczego ta funkcja rekurencyjna w Haskell jest taka powolna?

Question

Próbuję naśladować Sieve, aby znaleźć wszystkie najlepsze mniej niż niektóre liczby przy użyciu Haskell. Znalazłem inny program Haskell, który używa metody Sieve z wielką szybkością. Jednak następująca funkcja rekursywna, którą napisałem, jest bardzo powolna. Kod jest następujący:

sieve' :: Integer -> Integer -> [Integer] 

sieve' n 1 = [2 .. n] 

sieve' n (k + 1) | [x | x <- sieve' n k, x == k + 1] == [] = sieve' n k 

    |otherwise = [x | x <- sieve' n k, x == k + 1 || not (mod x (k + 1) == 0)] 



sieve :: Integer -> [Integer] 

sieve n = sieve' n n 

Sito 20 trwa około 2 minuty. Sieve 30 wciąż się nie zakończyła, pisząc to pytanie.

Czy ktoś może wyjaśnić, dlaczego ta funkcja rekursywna jest tak powolna. Dziękuję za pomoc, którą możesz udzielić.

Answer 1

Twoja druga klauzula funkcji sieve' powoduje dwukrotne wywołanie rekursywne (sieve' n k), dzięki czemu algorytm działa w czasie wykładniczym.

Aby rozwiązać ten problem można powiązać termin do jakiejś nazwy, zapewniając w ten sposób to ocenić raz:

sieve' n (k + 1) | [x | x <- rec, x == k + 1] == [] = rec 
    |otherwise = [x | x <- rec, x == k + 1 || not (mod x (k + 1) == 0)] 
    where 
    rec = sieve' n k 

Update w odpowiedzi na komentarz pytając dlaczego kompilator nie robi tego automatycznie:

Ten rodzaj transformacji, nazywany CSE (wspólne eliminowanie podwyrażeń), nie jest ogólnie optymalizacją, lecz raczej kompromisem między wykorzystaniem czasu i przestrzeni, więc decyzję należy pozostawić programistom.

Googling dla „CSE” ujawnia kilka ciekawych rozmów, z których jeden Referencje this very good example od 1987 roku książce Simon Peyton Jones nazywa „Wdrożenie Programowanie funkcyjne Języki” (Oh my, ta książka jest niemal tak stara jak ja)