La mia funzione di foldl riscritta è ottimizzata?

Question

Ho appena avviato Haskell 2 giorni fa, quindi non sono ancora sicuro su come ottimizzare il mio codice.

Come esercizio, ho riscritto foldl e foldr (I darà foldl qui ma foldr è la stessa, sostituendo last con head e init con tail).

Il codice è:

module Main where 

    myFoldl :: (a -> (b -> a)) -> a -> ([b] -> a) 

    myFoldl func = (\x -> (\theList 
     -> if (length theList == 0) then 
      x 
     else 
      myFoldl func (func x (last theList)) (init theList) 
     )) 

La mia unica preoccupazione è che ho il sospetto Haskell non può applicare l'ottimizzazione chiamata coda qui perché la chiamata ricorsiva non è fatta al termine della funzione.

Come posso rendere ottimizzata questa coda? L'implementazione integrata di Haskell di foldl è stata implementata in modo diverso per il mio?

Answer 1

L'utilizzo di parentesi nel campione di codice e l'enfasi sulla ricorsione in coda suggeriscono che verrai ad Haskell da Lisp o Scheme. Se vieni da Haskell da un linguaggio volgare come Scheme, tieni presente che le chiamate in coda non sono quasi predittive delle prestazioni in Haskell, poiché sono in un linguaggio entusiasta. Puoi avere funzioni ricorsive in coda che si eseguono nello spazio lineare a causa della pigrizia, e puoi avere funzioni ricorsive non tail che si eseguono nello spazio costante a causa della pigrizia. (Confuso già?)

Il primo errore nella definizione è l'uso di length theList == 0. Questo forza la valutazione dell'intera colonna vertebrale dell'elenco ed è O (n) tempo. E 'meglio usare il pattern matching, come in questo ingenuo foldl definizione in Haskell:

foldl :: (b -> a -> b) -> b -> [a] -> b 
foldl f z [] = z 
foldl f z (x:xs) = foldl f (f z x) xs 

Questo, tuttavia, effettua infamously male in Haskell, perché in realtà non calcoliamo la parte f z x finché il chiamante del foldl esige la risultato; quindi questo foldl accumula i thunks non valutati in memoria per ciascun elemento dell'elenco e non ottiene alcun beneficio dall'essere ricorsivo della coda. Infatti, nonostante sia ricorsivo in coda, questo ingenuo foldl su un lungo elenco può portare a un sovraccarico dello stack! (Lo Data.List module ha una funzione foldl' che non ha questo problema.)

Come converse a questo, molte funzioni ricorsive non-coda di Haskell funzionano molto bene. Per esempio, prendiamo questa definizione di find, in base alla definizione ricorsiva non coda accompagna foldr:

find :: (a -> Boolean) -> [a] -> Maybe a 
find pred xs = foldr find' Nothing xs 
    where find' elem rest = if pred elem then Just elem else rest 

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f z [] = z 
foldr f z (x:xs) = f x (subfold xs) 
    where subfold = foldr f z 

Esegue effettivamente nel tempo e nello spazio lineare costante, grazie alla pigrizia. Perché?

1. Una volta trovato un elemento che soddisfa il predicato, non è necessario per attraversare il resto della lista per calcolare il valore di rest.
2. Una volta esaminato un elemento e deciso che non corrisponde, non è necessario conservare alcun dato su quell'elemento.

La lezione che imparerei in questo momento è: non introdurre in Haskell le tue ipotesi sulle prestazioni di lingue entusiaste. Sei solo due giorni in; concentrati innanzitutto sulla comprensione della sintassi e della semantica del linguaggio e non ti contrapporre ancora alla scrittura di versioni ottimizzate di funzioni. In un primo momento, sarai colpito con lo stack in stile foldl, ma lo domineresti in tempo.

---

EDIT [9/5/2012]: più semplice dimostrazione che pigri find corre nello spazio costante nonostante non sia la coda ricorsiva. definizioni In primo luogo, semplificati:

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f z [] = z 
foldr f z (x:xs) = f x (foldr f z xs) 

find :: (a -> Bool) -> [a] -> Maybe a 
find p xs = let step x rest = if p x then Just x else rest 
      in foldr step Nothing xs 

Ora, usando il ragionamento equazionale (ad esempio, sostituendo pari con eguali, in base alla definizione di cui sopra), e valutare in un ordine pigro (più esterno prima), calcoliamo find (==400) [1..]:

find (==400) [1..] 
    -- Definition of `find`: 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing [1..] 

    -- `[x, y, ...]` is the same as `x:[y, ...]`: 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing (1:[2..]) 

    -- Using the second equation in the definition of `foldr`: 
    => let step x rest = if x == 400 then Just x else rest 
     in step 1 (foldr step Nothing [2..]) 

    -- Applying `step`: 
    => let step x rest = if x == 400 then Just x else rest 
     in if 1 == 400 then Just 1 else foldr step Nothing [2..] 

    -- `1 == 400` is `False` 
    => let step x rest = if x == 400 then Just x else rest 
     in if False then Just 1 else foldr step Nothing [2..] 

    -- `if False then a else b` is the same as `b` 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing [2..] 

    -- Repeat the same reasoning steps as above 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing (2:[3..]) 
    => let step x rest = if x == 400 then Just x else rest 
     in step 2 (foldr step Nothing [3..]) 
    => let step x rest = if x == 400 then Just x else rest 
     in if 2 == 400 then Just 2 else foldr step Nothing [3..] 
    => let step x rest = if x == 400 then Just x else rest 
     in if False then Just 2 else foldr step Nothing [3..] 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing [3..] 
     . 
     . 
     . 

    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing [400..] 
    => let step x rest = if x == 400 then Just x else rest 
     in foldr step Nothing (400:[401..]) 
    => let step x rest = if x == 400 then Just x else rest 
     in step 400 (foldr step Nothing [401..]) 
    => let step x rest = if x == 400 then Just x else rest 
     in if 400 == 400 then Just 400 else foldr step Nothing [401..] 
    => let step x rest = if x == 400 then Just x else rest 
     in if True then Just 400 else foldr step Nothing [401..] 

    -- `if True then a else b` is the same as `a` 
    => let step x rest = if x == 400 then Just x else rest 
     in Just 400 

    -- We can eliminate the `let ... in ...` here: 
    => Just 400 

Si noti che le espressioni nelle fasi di valutazione successive non diventano progressivamente più complesse o più lunghe mentre procediamo attraverso l'elenco; la lunghezza o la profondità dell'espressione al passo n non è proporzionale a n, è fondamentalmente fissa. Questo dimostra infatti come find (==400) [1..] possa essere eseguito pigramente in uno spazio costante.

Answer 2

Idiomatic Haskell ha un aspetto molto diverso da questo, evitando se-poi-altrimenti, nidificazione di lambda, parentesi e funzioni destrutturanti (testa, coda). Invece, devi scrivere qualcosa di simile:

foldl :: (a -> b -> a) -> a -> [b] -> a 
foldl f z0 xs0 = go z0 xs0 
    where 
     go z []  = z 
     go z (x:xs) = go (f z x) xs 

basandosi invece su pattern matching, una clausola WHERE, la ricorsione in coda, custodito dichiarazioni.