La pigrizia di Haskell è un'alternativa elegante ai generatori di Python?

Question

In un esercizio di programmazione, è stato prima chiesto di programmare la funzione fattoriale e quindi calcolare la somma: 1! + 2! + 3! +... n! in moltiplicazioni O(n) (quindi non è possibile utilizzare direttamente il fattoriale). Non sto cercando la soluzione a questo specifico (banale) problema, sto cercando di esplorare le abilità di Haskell e questo problema è un giocattolo con cui vorrei giocare.

Pensavo che i generatori di Python potessero essere una buona soluzione a questo problema. Per esempio:

from itertools import islice 
def ifact(): 
    i , f = 1, 1 
    yield 1 
    while True: 
     f *= i 
     i += 1 
     yield f 

def sum_fact(n): 
    return sum(islice(ifact(),5)) 

Poi ho cercato di capire se c'era qualcosa in Haskell avere un comportamento simile di questo generatore e ho pensato che la pigrizia fare tutto il personale, senza alcun concetto aggiuntivo.

Per esempio, si potrebbe sostituire il mio Python ifact con

fact = scan1 (*) [1..] 

E poi risolvere l'esercizio con il seguente:

sum n = foldl1 (+) (take n fact) 

mi chiedo se questa soluzione è davvero "equivalente" al proprio Python per quanto riguarda la complessità del tempo e l'utilizzo della memoria. Direi che la soluzione di Haskell non memorizza mai tutta la lista perché i loro elementi sono usati una sola volta.

Ho ragione o totalmente sbagliato?

---

EDIT: avrei dovuto controllare più precisamente:

Prelude> foldl1 (+) (take 4 fact) 
33 
Prelude> :sprint fact 
fact = 1 : 2 : 6 : 24 : _ 

So (il mio attuazione) Haskell memorizzare il risultato, anche se non è più utilizzato.

Answer 1

I tuoi esempi sono non equivalenti nell'utilizzo della memoria. È facile vedere se si sostituisce * con un + (in modo che i numeri non diventino troppo veloci) e quindi esegui entrambi gli esempi su un grande n come 10^7. La tua versione di Haskell consumerà molta memoria e python lo manterrà basso.

Il generatore Python non genererà un elenco di valori, quindi riassumerà. Invece, la funzione sum otterrà i valori uno a uno dal generatore e li accumulerà. Pertanto, l'utilizzo della memoria rimarrà costante.

Haskell valuterà le funzioni pigramente, ma per calcolare dire foldl1 (+) (take n fact) dovrà valutare l'espressione completa. Per large n questo si aprirà in un'espressione enorme allo stesso modo di (foldl (+) 0 [0..n]). Per maggiori dettagli su valutazione e riduzione dai un'occhiata qui: https://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27.

È possibile correggere il sum n utilizzando foldl1' anziché foldl1 come descritto nel collegamento sopra. Come @ user2407038 ha spiegato nel suo commento, avresti anche bisogno di mantenere fact locale. Le seguenti opere in GHC con l'utilizzo della memoria costante:

let notfact = scanl1 (+) [1..] 
let n = 20000000 
let res = foldl' (+) 0 (take n notfact) 

Si noti che nel caso del fattoriale reale al posto di notfact considerazioni di memoria sono meno di una preoccupazione. I numeri diventeranno grandi rapidamente, l'aritmetica di precisione arbitraria rallenterà le cose in modo da non essere in grado di ottenere grandi valori di n per poter effettivamente vedere la differenza.

Answer 2

Fondamentalmente, sì: le lazy-list di Haskell sono molto simili ai generatori di Python, se quei generatori fossero facilmente clonabili, memorizzabili nella cache e componibili. Invece di aumentare StopIteration si restituisce [] dalla funzione ricorsiva, che può inserire lo stato nel generatore.

Fanno cose più interessanti a causa dell'auto-ricorsione. Ad esempio, il generatore fattoriale è più idiomaticamente generato come:

facts = 1 : zipWith (*) facts [1..] 

oi Fibonaccis come:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs) 

In generale qualsiasi ciclo iterativo può essere convertito in un algoritmo ricorsivo attraverso la promozione del ciclo-stato a argomenti di una funzione e quindi chiamarla in modo ricorsivo per ottenere il ciclo successivo. I generatori sono proprio così, ma anteponiamo ad alcuni elementi ogni iterazione della funzione ricorsiva, `go ____ = (cose): vai ____.

L'equivalente perfetta è dunque:

ifact :: [Integer] 
ifact = go 1 1 
    where go f i = f : go (f * i) (i + 1) 

sum_fact n = sum (take n ifact) 

In termini di ciò che è più veloce, il più veloce in assoluto in Haskell sarà probabilmente il "ciclo for":

sum_fact n = go 1 1 1 
    where go acc fact i 
      | i <= n = go (acc + fact) (fact * i) (i + 1) 
      | otherwise = acc 

Il fatto che questo è " coda-ricorsiva "(una chiamata di go non convoglia alcuna chiamata secondaria a go a un'altra funzione come (+) o (*)) significa che il compilatore può impacchettarlo in un ciclo molto stretto, ed è per questo che lo sto confrontando con" for loops "anche se non è un'idea nativa per Haskell.

Quanto sopra sum_fact n = sum (take n ifact) è un po 'più lento di questo, ma più veloce di sum (take n facts) dove facts viene definito con zipWith. Le differenze di velocità non sono molto grandi e penso che per lo più si limitino a allocazioni di memoria che non vengono più utilizzate.

Answer 3

In effetti, le liste pigre possono essere utilizzate in questo modo. Ci sono alcune sottili differenze:

• Le liste sono strutture di dati. Quindi puoi mantenerli dopo averli valutati, il che può essere sia buono sia cattivo (puoi evitare il ricalcolo dei valori e trucchi ricorsivi come descritto da @ChrisDrost, al costo di mantenere la memoria non rilasciata).
• Le liste sono pure. Nei generatori è possibile avere calcoli con effetti collaterali, non è possibile farlo con le liste (che è spesso auspicabile).
• Dal momento che Haskell è un linguaggio pigro, la pigrizia è ovunque e se si converte semplicemente un programma da un linguaggio imperativo a Haskell, i requisiti di memoria possono cambiare considerevolmente (come descrive @RomanL nella sua risposta).

Ma Haskell offre strumenti più avanzati per realizzare il modello generatore/consumatore. Attualmente ci sono tre librerie che si concentrano su questo problema: pipes, conduit and iteratees. Il mio preferito è conduit, è facile da usare e la complessità dei suoi tipi è mantenuta bassa.

Hanno diversi vantaggi, in particolare che è possibile creare pipeline complesse e basarle su una monade scelta, che consente di dire quali effetti collaterali sono consentiti in una pipeline.

Utilizzando condotto, il tuo esempio potrebbe essere espresso come segue:

import Data.Functor.Identity 
import Data.Conduit 
import qualified Data.Conduit.List as C 

ifactC :: (Num a, Monad m) => Producer m a 
ifactC = loop 1 1 
    where 
    loop r n = let r' = r * n 
       in yield r' >> loop r' (n + 1) 

sumC :: (Num a, Monad m) => Consumer a m a 
sumC = C.fold (+) 0 

main :: IO() 
main = (print . runIdentity) (ifactC $= C.isolate 5 $$ sumC) 
-- alternatively running the pipeline in IO monad directly: 
-- main = (ifactC $= C.isolate 5 $$ sumC) >>= print 

Qui creiamo un Producer (un condotto che consuma nessun input) che produce fattoriali a tempo indeterminato. Quindi lo componiamo con isolate, che garantisce che non venga propagato più di un dato numero di valori attraverso di esso, e quindi lo componiamo con uno Consumer che somma solo i valori e restituisce il risultato.