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.La pigrizia di Haskell è un'alternativa elegante ai generatori di Python?
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.
Ci sono alcune somiglianze, ma anche alcune differenze: i generatori Python non ti danno accesso agli elementi visitati in precedenza, a meno che tu non li memorizzi esplicitamente in qualche altro oggetto. – pyon
I più vicini generatori analogici a Python (C#: 'IEnumerator', Rust:' Iterator', ecc.) Mi viene in mente la nozione di 'Producer's, nell'eccellente [pipe] di Gabriel Gonzalez (http://hackage.haskell.org/package/pipes) libreria. – pyon
Direi che sono un po 'più di una generalizzazione di loro in qualche modo, ma i generatori di Python possono anche fungere da coroutine, che sono piuttosto carini in circostanze molto specifiche. – bheklilr