Pigrizia e ricorsione della coda in Haskell, perché questo si sta schiantando?

Question

Ho questa funzione abbastanza semplice per calcolare la media degli elementi di una grande lista, usando due accumulatori per contenere la somma finora e il conteggio finora:

mean = go 0 0
    where
      go s l []     = s / fromIntegral l
      go s l (x:xs) = go (s+x) (l+1) xs

main = do
  putStrLn (show (mean [0..10000000]))

Ora, in un linguaggio rigoroso, questo sarebbe ricorsivo alla coda e non ci sarebbero problemi. Tuttavia, dato che Haskell è pigro, il mio googling mi ha portato a capire che (s + x) e (l + 1) saranno passati alla ricorsione come thunk. Quindi l'intera faccenda si schianta e brucia:

Stack space overflow: current size 8388608 bytes.

Dopo aver cercato su Google, ho trovato seq e $! . Il che sembra non capisco perché tutti i miei tentativi di usarli in questo contesto si sono rivelati inutili, con messaggi di errore che dicevano qualcosa su tipi infiniti.

Finalmente ho trovato -XBangPatterns , che risolve tutto cambiando la chiamata ricorsiva:

go !s !l (x:xs) = go (s+x) (l+1) xs

Ma non sono contento di questo, dato che -XBangPatterns è attualmente un'estensione. Vorrei sapere come rendere severa la valutazione senza l'uso di -XBangPatterns . (E forse impari anche qualcosa!)

Solo per capire la mia mancanza di comprensione, ecco cosa ho provato (l'unico tentativo compilato, cioè):

go s l (x:xs) = go (seq s (s+x)) (seq l (l+1)) xs

Da quello che ho potuto capire, seq dovrebbe qui forzare la valutazione dell'argomento s ed l, evitando così il problema causato dai thunk. Ma ho ancora un overflow dello stack.

Answer 1

Ho scritto molto su questo:

• Real World Haskell, cap 24: controllo della valutazione
• Sulla ricorsione e rigore in Haskell

In primo luogo, sì, se si desidera richiedere una valutazione rigorosa degli accumulatori, utilizzare seq e rimanere in Haskell 98:

mean = go 0 0
  where
    go s l []     = s / fromIntegral l
    go s l (x:xs) = s `seq` l `seq`
                      go (s+x) (l+1) xs

main = print $ mean [0..10000000]

*Main> main
5000000.0

In secondo luogo: se si danno alcune annotazioni di tipo, si avvia l'analisi di rigidezza e si compila con -O2:

mean :: [Double] -> Double
mean = go 0 0
 where
  go :: Double -> Int -> [Double] -> Double
  go s l []     = s / fromIntegral l
  go s l (x:xs) = go (s+x) (l+1) xs

main = print $ mean [0..10000000]

$ ghc -O2 --make A.hs
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...

$ time ./A
5000000.0
./A  0.46s user 0.01s system 99% cpu 0.470 total

Poiché 'Double' è un wrapper sul tipo atomico rigoroso Double #, con ottimizzazioni attivate e un tipo preciso, GHC esegue un'analisi di rigore e afferma che la versione rigorosa andrà bene.

import Data.Array.Vector

main = print (mean (enumFromToFracU 1 10000000))

data Pair = Pair !Int !Double

mean :: UArr Double -> Double   
mean xs = s / fromIntegral n
  where
    Pair n s       = foldlU k (Pair 0 0) xs
    k (Pair n s) x = Pair (n+1) (s+x)

$ ghc -O2 --make A.hs -funbox-strict-fields
[1 of 1] Compiling Main             ( A.hs, A.o )
Linking A ...

$ time ./A
5000000.5
./A  0.03s user 0.00s system 96% cpu 0.038 total

Come descritto nel capitolo RWH sopra.

Answer 2

La funzione seq forza la valutazione del primo parametro una volta chiamata la funzione. Quando passi seq s (s + x) come parametro la funzione seq viene non chiamata immediatamente, perché non è necessario valutare valore di quel parametro. Volete che la chiamata a seq sia valutata prima della chiamata ricorsiva, in modo che a sua volta possa forzare la valutazione del suo parametro.

Di solito questo è fatto link this:

 go s l (x:xs) = s `seq` l `seq` go (s+x) (l+1) xs

Questa è una variazione sintattica di seq s (seq l (go (s + x) (l + 1) xs)) . Qui le chiamate a seq sono le chiamate di funzione più esterne nell'espressione. A causa della pigrizia di Haskell, questo fa sì che vengano valutati per primi: seq viene chiamato con i parametri ancora non valutati s e seq l (go (s + x) (l +1) xs) , la valutazione dei parametri viene rinviata al punto in cui qualcuno cerca effettivamente di accedere ai propri valori.

Ora seq può forzare la valutazione del suo primo parametro prima di restituire il resto dell'espressione. Quindi il prossimo passo nella valutazione sarebbe il secondo seq . Se le chiamate a seq sono sepolte da qualche parte in alcuni parametri, potrebbero non essere eseguite a lungo, vanificando il loro scopo.

Con le posizioni modificate del seq il programma si esegue bene, senza usare eccessive quantità di memoria.

Un'altra soluzione al problema sarebbe semplicemente abilitare le ottimizzazioni in GHC quando viene compilato il programma ( -O o -O2 ). L'ottimizzatore riconosce la pigrizia superflua e produce codice che non alloca memoria inutile.

Answer 3

Hai ragione nel capire che seq s (s + x) forza la valutazione di s . Ma non forza s + x , quindi stai ancora accumulando thunk.

Usando $! puoi forzare la valutazione dell'aggiunta (due volte, per entrambi gli argomenti). Ciò ottiene lo stesso effetto dell'uso dei modelli di botto:

mean = go 0 0
 where
    go s l []     = s / fromIntegral l
    go s l (x:xs) = ((go $! s+x) $! l+1) xs

---

L'uso della funzione $! tradurrà go $! (s + x) all'equivalente di:

let y = s+x 
in seq y (go y)

Quindi y viene prima forzato nella forma normale testa debole , il che significa che viene applicata la funzione più esterna. Nel caso di y , la funzione più esterna è + , quindi y viene valutato completamente in un numero prima di essere passato a go .

---

Oh, e probabilmente hai ricevuto il messaggio di errore di tipo infinito perché non avevi la parentesi nel posto giusto. Ho avuto lo stesso errore quando ho scritto per la prima volta il tuo programma :-)

Perché l'operatore $! è associativo giusto, senza parentesi vai $! (s + x) $! (l + 1) significa lo stesso di: go $! ((s + x) $! (l + 1)) , che è ovviamente sbagliato.