stile non pointfree è sostanzialmente più lento

Question

Ho il seguente codice spesso citata per il calcolo del numero di Fibonacci n-esimo in Haskell:

fibonacci :: Int -> Integer 
fibonacci = (map fib [0..] !!) 
    where fib 0 = 0 
      fib 1 = 1 
      fib n = fibonacci (n-2) + fibonacci (n-1) 

Usando questo, posso fare chiamate come ad esempio:

ghci> fibonacci 1000 

e ricevi una risposta quasi istantanea.

Tuttavia, se modifico il codice di cui sopra in modo che non è in stile pointfree, cioè

fibonacci :: Int -> Integer 
fibonacci x = (map fib [0..] !!) x 
    where fib 0 = 0 
      fib 1 = 1 
      fib n = fibonacci (n-2) + fibonacci (n-1) 

è sostanzialmente più lento. Nella misura in cui una chiamata come

ghci> fibonacci 1000 

si blocca.

La mia comprensione era che i due codici di cui sopra erano equivalenti, ma GHCi chiede di dissentire. Qualcuno ha una spiegazione per questo comportamento?

Answer 1

Per osservare la differenza, probabilmente dovresti dare un'occhiata a Core. La mia ipotesi che questo si riduce a confronto tra (circa)

let f = map fib [0..] in \x -> f !! x 

a

\x -> let f = map fib [0..] in f !! x 

Quest'ultimo ricalcolare f da zero ad ogni chiamata. Il primo non memorizza efficacemente nella cache lo stesso f per ogni chiamata.

Accade che in questo caso specifico, GHC è stato in grado di ottimizzare il secondo nel primo, una volta abilitata l'ottimizzazione.

Nota tuttavia che GHC non esegue sempre questa trasformazione, poiché questa non è sempre un'ottimizzazione. La cache utilizzata dal primo viene conservata per sempre nella memoria. Ciò potrebbe comportare uno spreco di memoria, a seconda della funzione a portata di mano.

Answer 2

Ho provato a trovarlo ma ho colpito. Penso di averlo sul mio PC a casa. Quello che ho letto è stato che le funzioni che utilizzano il punto fisso erano intrinsecamente più veloci. Ci sono altri motivi per usare il punto fisso. Ne ho incontrato uno nella stesura della funzione iterativa di Fibonacci. Volevo vedere come avrebbe funzionato una versione iterativa, poi mi sono reso conto che non avevo un modo pronto per misurare. Sono un neofita di Haskell. Ma qui c'è una versione iterativa per qualcuno da testare. Non ho potuto ottenere questo da definire a meno che non ho usato il punto dopo la prima ultima funzione. Non ho potuto ridurlo ulteriormente. il parametro [0,1] è fisso e non deve essere fornito come valore di parametro.

Prelude> fib = last . flip take (iterate (\ls -> ls ++ [last ls + last (init ls)]) [0,1]) 
Prelude> fib 25 

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025]