Czy można napisać funkcję czynnikową tak szybko, jak "podręcznik" w inny sposób?

Question

widzę to jako ogólną formę silni funkcji w Haskell:

factorial :: (Integral a) => a -> a 
factorial n = product [1..n] 

Rozumiem, że jest to najbardziej elegancki sposób, ale kiedy napisać własny funkcji rekurencyjnej, aby to zrobić, to znacznie wolniej:

factorial :: (Integral a) => a -> a 
factorial 1 = 1 
factorial n = n * factorial (n - 1) 

Czy pierwsze rozwiązanie nie musi zrobić prawie wszystkiego, co robi pierwszy, wewnętrznie? Jak to jest o wiele szybciej? Czy można napisać coś tak szybko, jak pierwsze rozwiązanie bez użycia fantazyjnej listy lub funkcji produktu?

Answer 1

Pierwsza wersja jest łatwiejsza do GHC zoptymalizować niż drugi. W szczególności product uses foldl:

product = foldl (*) 1 

i po nałożeniu na [1..n] (który jest tylko 1 `enumFromTo` n) podlega fusion. W skrócie, GHC ma starannie opracowane zasady ponownego zapisu, które mają na celu optymalizację pośrednich struktur danych z fragmentów kodu, w których tworzone listy są natychmiast zużywane (w przypadku factorial, foldl (*) 1 jest konsumentem i 1 `enumFromTo` n producentem).

Pamiętaj, że możesz zrobić to, co robi GHC (factorial = foldl (*) 1 . enumFromTo 1) i uzyskać tę samą wydajność.

---

Twoja druga funkcja nie jest nawet rekurencyjna. Że część można naprawić dość łatwo przez przechodzącą w akumulatorze:

factorial :: (Integral a) => a -> a 
factorial n = go n 1 
    where 
    go 0 m = m 
    go n m = go (n-1) (n*m) 

w parze z tym, jest fakt, że dla większości typów liczbowych będziemy chcieli arytmetyczną być surowe. Sprowadza się to do dodania BangPatterns do n i m.

Answer 2

Może coś takiego:

f n = foldl (*) 1 [1..n] 

można zmienić foldl na foldr lub foldl”zmieni prędkość