[Haskell] implementazione di Data.List.intersperse

[banryu79]

Salve,
mi sto cimentando con Haskell, e mentre studio ho preso l'abitudine di provare a reimplementare tutte le funzioni della libreria standard che incontro.

Mi sono lambiccato un po' per capire come implementare intersperse, ho tirato fuori queste due versioni:

-- intersperse with patter matching & recursion
intersperse'' :: a -> [a] -> [a]
intersperse'' _ [] = []
intersperse'' _ [x] = [x]
intersperse'' e (x:xs) = x: (e: (intersperse'' e xs))

-- intersperse with foldr, drop & partial application
rIntersperse :: a -> [a] -> [a]
rIntersperse e = (drop 1) . foldr (\ x acc -> e:x:acc) []


Qualcuno pratico di Haskell può esporre le sue considerazioni? Nel senso: si può fare di meglio (in qualunque senso si voglia attribuire a "meglio")?
In particolare pensavo di poterla implementare con una scan, ma mi sono incartato, convincendomi che non si può fare.

[banryu79]

uppete :O


Uè infami! 11 letture e nessuno che mi dica almeno "ma che cazzo fai?"
Mi aspettavo qualcosa almeno dai più esotici (marco.r, shinya, ecc...)

Completo la domanda: quale delle due versioni è più efficiente a runtime? Quale più idiomatica? Many thanks :D

[marco.r]

uppete :O


Uè infami! 11 letture e nessuno che mi dica almeno "ma che cazzo fai?"
Mi aspettavo qualcosa almeno dai più esotici (marco.r, shinya, ecc...)

Completo la domanda: quale delle due versioni è più efficiente a runtime? Quale più idiomatica? Many thanks :D

Rispondo piu' compiutamente dopo che ora sono di fretta.
comunque dipende da cosa intendi dire piu' efficiente, visto che possiamo parlari di performance, spazio, se hai a che fare con liste finite, infinite...
(a naso non ci dovrebbero essere differenze rilevanti, poi verifico)

[banryu79]

Ok, mi interessava soprattuto l'efficienza a runtime in termini di tempi di esecuzione.

Comunque mi hai messo la pulce nell'orecchio (per quanto riguarda l'uso della memoria). Se hai tempo (e piacere), potresti chiarirmi una cosa? Stavo leggendo del GC di GHC (sto usando GCHi) e leggevo:

...
This greatly simplifies garbage collection (GC). At anytime we can scan the last values created and free those that are not pointed to from the same set (of course, real roots of live values hierarchy are live in the stack). It is how things work: by default, GHC uses generational GC. New data are allocated in 512kb "nursery". Once it's exhausted, "minor GC" occurs - it scans the nursery and frees unused values. Or, to be exact, it copies live values to the main memory area. The fewer values that survive - the less work to do. If you have, for example, a recursive algorithm that quickly filled the nursery with generations of its induction variables - only the last generation of the variables will survive and be copied to main memory, the rest will be not even touched! So it has a counter-intuitive behavior: the larger percent of your values are garbage - the faster it works.

Non riesco a capire la parte in grasseto. La main memory dovrebbe essere la ram, se non erro? E il resto (quello che dice di non toccare) dove è allocato? Sullo stack?

Grazie di ogni eventuale spiegazione, marco.r :)

[banryu79]

Hum, ho appena incontrato foldl' e foldl1' e leggo or ora della questione dei "thunk" nella verisione lazy di queste due funzioni e dei problemi di stack overflow, comincio a capirci qualcosina.

Inoltre ho spulciato l'implementazione di interseperse in Data.List:

-- | The 'intersperse' function takes an element and a list and
-- \`intersperses\' that element between the elements of the list.
-- For example,
--
-- > intersperse ',' "abcde" == "a,b,c,d,e"

intersperse :: a -> [a] -> [a]
intersperse _ [] = []
intersperse sep (x:xs) = x : prependToAll sep xs


-- Not exported:
-- We want to make every element in the 'intersperse'd list available
-- as soon as possible to avoid space leaks. Experiments suggested that
-- a separate top-level helper is more efficient than a local worker.
prependToAll :: a -> [a] -> [a]
prependToAll _ [] = []
prependToAll sep (x:xs) = sep : x : prependToAll sep xs

La parte in grasseto implica quindi che quella versione è più efficiente, che so, della mia implementazione con foldr (che a questo punto sostituirei con foldr') oppure no? Mi sfugge il significato di "local worker", cosa intendono esattamente? Un let ... in ... piuttosto che una where?

[marco.r]

Ok, mi interessava soprattuto l'efficienza a runtime in termini di tempi di esecuzione.

Comunque mi hai messo la pulce nell'orecchio (per quanto riguarda l'uso della memoria). Se hai tempo (e piacere), potresti chiarirmi una cosa? Stavo leggendo del GC di GHC (sto usando GCHi) e leggevo:

Non riesco a capire la parte in grasseto. La main memory dovrebbe essere la ram, se non erro? E il resto (quello che dice di non toccare) dove è allocato? Sullo stack?

Grazie di ogni eventuale spiegazione, marco.r :)
Allora, quanto e' scritto la' e' vero ma un po' una minchiata (se mi passi il francesismo) :D.
Comunque il tuo dubbio e' dovuto principalmente alla terminologia usata. Tenendo presente che quello di GHC e' un GC generazionale, fa conto che la "nursery" sia la generation 0, mentre la "main memory" le generazioni da 1 in su (non so se in pratica sia una sola generazione o piu').
La questione del non toccare il resto e' legata all'affermazione

The trick is that immutable data NEVER points to younger values

In particolare i dati della generazione N+1 sono sempre piu' vecchi di quelli della generazione N per cui nessun oggetto nella generazione N+1 puntera' a qualsivoglia oggetto nella generazione N.
Questo vuol dire che per decidere se i dati della generazione N sono garbage o meno, posso considerare solo le generazioni <= N, e ovviamente la root (ovvero lo stack, variabili globali, registri del processore...).
In particolare la vita degli oggetti della generazione 0 (la nursery) e' totatlmente indipendente dalle altre generazioni, per cui l'idea e' che io la tengo di dimensione piccola, e la pulisco frequentemente. Questa e' una operazione molto rapida perche' devo controllare solo poche centinaia di kb invece che magari due GB di memoria dell'intero processo.
Questo vuol dire che per GHC decidere di allocare le variabili locali della funzione nello heap invece che nello stack non e' molto piu' costoso.
Il discorso fatto in quel link e' corretto, visto che se io produco 10 byte di garbage ogni 1 devo fare meta' lavoro piuttosto che generarne 5 ogni 1, ma ovviamente il garbage collector verra' chiamato in causa piu' spesso, per questo dicevo che e' una cavolata.

[marco.r]

Salve,
mi sto cimentando con Haskell, e mentre studio ho preso l'abitudine di provare a reimplementare tutte le funzioni della libreria standard che incontro.

Mi sono lambiccato un po' per capire come implementare intersperse, ho tirato fuori queste due versioni:

-- intersperse with patter matching & recursion
intersperse'' :: a -> [a] -> [a]
intersperse'' _ [] = []
intersperse'' _ [x] = [x]
intersperse'' e (x:xs) = x: (e: (intersperse'' e xs))

-- intersperse with foldr, drop & partial application
rIntersperse :: a -> [a] -> [a]
rIntersperse e = (drop 1) . foldr (\ x acc -> e:x:acc) []


Qualcuno pratico di Haskell può esporre le sue considerazioni? Nel senso: si può fare di meglio (in qualunque senso si voglia attribuire a "meglio")?
In particolare pensavo di poterla implementare con una scan, ma mi sono incartato, convincendomi che non si può fare.

Dal punto di vista prestazionale non ti so dire, non penso ci dovrebbero essere enormi differenze (ma qui lo dico e qui lo nego :D).
Francamente trovo la prima versione piu' leggibile e preferibile (foldl e compagnia le trovo comode quando l'operazione e' a sua volta un parametro, per cui si riesce a programmare a piu' alto livello, altrimenti preferisco la versione esplicita).
Anche l'impatto sulla memoria dovrebbe essere relativamente analogo (bisogna un po' capire come funziona la fold e l'impatto sullo stack, per maggiori dettagli puoi spulciarti http://www.haskell.org/haskellwiki/Fold e soprattutto http://www.haskell.org/haskellwiki/Stack_overflow).
Non puoi usare una scan, e piu' che convincersi si puo' dimostrarlo. scanl (e parenti) ritorna una lista della stessa lunghezza di quella originale, mentre tu ne vuoi una che abbia lunghezza 2N-1. Direi che non sono compatibili le due cose.

b.t.w. se vuoi una soluzione ancora piu' sintetica (e abbastanza leggibile, anche se probabilmente meno efficiente), il seguente e' un bel one-liner :D

intersperse c xs = tail $ concat [ [c,x] | x <- xs ]

[marco.r]

La parte in grasseto implica quindi che quella versione è più efficiente, che so, della mia implementazione con foldr (che a questo punto sostituirei con foldr') oppure no?

Questa e' una domanda difficile, non vale :D
Cerco di spiegarmi, ma non garantisco buoni risultati :p
Parto intanto dalla definizione di foldr

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

E poi riscriviamo un attimo per leggibilita' la tua funzione in una versione strutturalmente identica

rIntersperse e xs = drop 1 (foldr f [] xs)
where f x acc = e:x:acc

Se vado a fare l'espansione di una chiamata

rIntersperse 10 [1,2,3]
drop 1 (foldr f [] [1,2,3])
drop 1 (f 1 (foldr f [] [2,3]))
drop 1 (10 : 1 : (foldr f [] [2,3]))
1 : (foldr f [] [2,3]) -- Qua ho gia' il primo elemento della lista
1 : (f 2 (foldr f [] [3]))
1 : (10 : 2 : (foldr f [] [3])) -- qui ho il secondo e il terzo
1 : (10 : 2 : (f 3 (foldr f [] [])))
1 : 10 : 2 : 10 : 3 : [] -- qua anche il resto

Quindi no, a naso la versione con foldr non crea space leak. Infatti foldr e' di solito la funzione adatta per quando l'output della fold e' una lista che vuoi costruire man mano i valori di una lista potenzialmente infinta
In altri termini il seguente codice funziona

take 10 $ rIntersperse 0 [1..]

Anche se vado a fare la fold su una lista infinita.
Per il discorso foldl foldr... occhio che sono due cose distinte, a meno che l'operazione che vai a fare non sia commutativa.
Per capirlo e' molto comodo pensare al fatto che, figurativamente, ottieni il risultato della fold{r,l} semlicemente sostituendo la funzione argomento alle virgole, e associando rispettivamente a destra e sinistra:

[1,2,3,4,5] -- lista iniziale

(1 `f` (2 `f` (3 `f` (4 `f` 5)))) -- foldr
(((((1 `f` 2) `f` 3) `f` 4) `f` 5) -- foldl

Ora se 'f' e' una (+) sono uguali come risultato (ma non come spazio utilizzato), perche' diventano

(1 + (2 + (3 + (4 + 5))))
((((1 + 2) + 3) + 4) + 5)

Visto che la + commuta il risultato e' lo stesso. Pero' prova con una meno e vedi che cambia tutto
Nel tuo caso la intersperse fatta con la foldr e' piu' o meno la seguente cosa

intersperse 10 [1,2,3,4,5]
(1 : 10 : (2 : 10 : (3 : 10 : ( 4 : 10 : 5))))

Non puoi ottenere una cosa analoga con la foldl, a meno che tu non voglia ottenere la lista a rovescio, oppure una lista di liste.
La foldl' e' simile alla foldl solo che "forza" la computazione dei risultati parziali durante l'esecuzione.
Ad esempio quando faccio foldl (+) della solita lista

((((1 + 2) + 3) + 4) + 5)

Io mi tengo tutta quell'espressione non valutata fino a che non necessito di sapere quel valore (ad esempio per stamparlo a video). Questo vuol dire che al posto di un singolo intero mi tengo da qualche parte l'albero di computazione piu' tutta la lista originale. Ora capisci da dove viene lo space leak.
foldl' invece forza il calcolo (1+2) = 3 prima di incrociare l'elemento successivo, per cui ti porti dietro il risultato parziale.

A questo punto (spero :D) dovresti aver capito quando usare foldr e quando foldl.
Vuoi produrre una lista o comunque una struttura dati che puoi cominciare ad usare quando la computazione (potenzialmente infinita) non e' ancora terminata ? Usa foldr:

(1 : 10 : (2 : 10 : (3 : 10 : ( 4 : 10 : 5))))

Vuoi una computazione di cui ti interessa il solo risultato finale e lo vuoi fare senza portarti dietro tutti i calcoli intermedi ? Usa foldl' (e lascia stare foldl)

((((1+2)+3)+4)+5)



Mi sfugge il significato di "local worker", cosa intendono esattamente? Un let ... in ... piuttosto che una where?
Esatto, intendono semplicemente una funzione definita localmente.
Per capirsi l'alternativa e'


intersperse :: a -> [a] -> [a]
intersperse _ [] = []
intersperse sep (x:xs) = x : prependToAll sep xs
where prependToAll sep (x:xs) = sep : x : prependToAll sep xs

Sul perche' sia piu' veloce una versione piuttosto che l'altra non ne ho idea, ma a quanto pare neanche loro :D (ghc effettua inaspettate ottimizzazioni a volte).

[banryu79]

...
In particolare i dati della generazione N+1 sono sempre piu' vecchi di quelli della generazione N per cui nessun oggetto nella generazione N+1 puntera' a qualsivoglia oggetto nella generazione N.
Questo vuol dire che per decidere se i dati della generazione N sono garbage o meno, posso considerare solo le generazioni <= N, e ovviamente la root (ovvero lo stack, variabili globali, registri del processore...).
In particolare la vita degli oggetti della generazione 0 (la nursery) e' totatlmente indipendente dalle altre generazioni, per cui l'idea e' che io la tengo di dimensione piccola, e la pulisco frequentemente. Questa e' una operazione molto rapida perche' devo controllare solo poche centinaia di kb invece che magari due GB di memoria dell'intero processo.
...

Grazie, ora ho capito!
Una considerazione forse scontata: quindi, per via dell'imutabilità dei valori in un linguaggio di programmazione puramente funzionale, non ha senso immaginarne uno che non preveda una piattaforma con GC e invece deleghi al programmatore la gestione della memoria, sarebbe assurdo, giusto?



Non puoi usare una scan, e piu' che convincersi si puo' dimostrarlo. scanl (e parenti) ritorna una lista della stessa lunghezza di quella originale, mentre tu ne vuoi una che abbia lunghezza 2N-1. Direi che non sono compatibili le due cose.

Grazie, purtroppo non sono abituato a ragionare in termini rigorosi, e questo a volte è un limite molto forte con cui mi trovo a fare i conti.



b.t.w. se vuoi una soluzione ancora piu' sintetica (e abbastanza leggibile, anche se probabilmente meno efficiente), il seguente e' un bel one-liner

intersperse c xs = tail $ concat [ [c,x] | x <- xs ]


Ach, bello, non mi era venuto in mente di provare con una list comprehension. D'altro canto ho appena cominciato, devo ancora finire il tutorial che sto usando, e mi stavo proprio esercitando con le varie fold e scan quindi magari per un po' tenderò a infilarle a muzzo un po' ovunque, finchè non le digerisco bene.
La cosa che mi colpisce di più, nella tua versione qui sopra analoga alla mia, è che per sbarazzarti del primo "separator" in testa alla lista tu dici "è la coda" e io invece dico "molla il primo elemento della lista": prospettiva funzionale (la tua) contro prospettiva imperativa (la mia), il nuovo paradigma sarà la cosa che mi richiederà più tempo in assoluto da adottare...



Questa e' una domanda difficile, non vale :D
Cerco di spiegarmi, ma non garantisco buoni risultati :p
Parto intanto dalla definizione di foldr
...

Many, many, many thanks!
So che dare risposte così articolate richiede tempo, ti ringrazio tantissimo per le spiegazioni, mi sono state utilissime!
Appena ho tempo (a casa) mi sviscero ben bene questo post, che per ora mi ha chiarito comunque alcuni dubbi e domandine che mi erano sorte circa l'opportunità o meno di usare le fold{l,r} le differenze tra loro e quando usare le versioni lazy piuttosto che le strict.
Sto anche consultando le pagine su haskell.org che mi hai indicato, c'è parecchia carne al fuoco a quanto pare, però sto capendo un poco di più (fold' o foldr, la facenda della strictness del secondo argomento della funzione passata alla fold ecc...)

Comuqnue anche a me piace (trovo più leggibile) la versione con il pattern matching e la ricorsione.

Marco, mi sei stato di grandissimo aiuto, grazie! :mano:

[marco.r]

Grazie, ora ho capito!
Una considerazione forse scontata: quindi, per via dell'imutabilità dei valori in un linguaggio di programmazione puramente funzionale, non ha senso immaginarne uno che non preveda una piattaforma con GC e invece deleghi al programmatore la gestione della memoria, sarebbe assurdo, giusto?

Si' e' improponibile, e la questione non e' solo relativa alla quantita' di memoria allocata e deallocata, ma anche, e soprattutto al fatto che l'immutabilita' dei valori porta ad un pesante riuso dei valori tra strutture dati diverse (tanto non cambiando mai non c'e' alcun rischio) che rende impossibile seguire "a mano" la vita degli oggetti.
L'esempio classico e' quello dell'albero di ricerca funzionale
Fa conto di avere definito un albero in questo modo

data Tree = Leaf | Node Int Tree Tree

E che definiamo un inserimento in modo da tenerlo ordinato (per semplicita ignoriamo il discorso del bilanciamento)

insert :: Tree -> Int -> Tree
insert Leaf x = Node x Leaf Leaf
insert (Node k l r) = if x <= k then Node k (insert l x) r
else Node k l (insert r x)

Quando io vado ad inserire un nuovo elemento nell'albero, non vado a modificare la vecchia versione, che tengo buona (volendo) per altri usi.
Ma il nuovo albero che ottengo, non e' totalmente differente da quello vecchio, anzi gran parte dei dati sono condivisi. Le uniche differenze sono nel cammino tra la radice e l'elemento nuovo inserito. Ad esempio nel seguente albero

10
/ \
5 100
/ / \
1 50 200

Inserendo 7 ottengo

10
/ \
5 100
/ \ / \
1 7 50 200

dove gli unici nodi nuovi sono quelli contenenti 10, 5 e 7 stesso.
Come puoi immaginare tenere traccia di tutto questo manualmente diventa impossibile.

[banryu79]

...
Nel tuo caso la intersperse fatta con la foldr e' piu' o meno la seguente cosa

intersperse 10 [1,2,3,4,5]
(1 : 10 : (2 : 10 : (3 : 10 : ( 4 : 10 : 5))))

Non puoi ottenere una cosa analoga con la foldl, a meno che tu non voglia ottenere la lista a rovescio, oppure una lista di liste.

Beh, io penso che anche con la foldl si possa fare (parlo relativamente al fatto di implementare intersperse) solo che il mio tutorial mi dice che è "bad" dover usare (++) quando puoi fare lo stesso usando (: )

-- Intersperse with foldr (lazy, can work on infinite list)
-- example:
-- intersperse 10 [1,2,3,4,5]
-- with foldr expanded:
-- 1 f (2 f (3 f (4 f 5)))
-- 10:1:(10:2:(10:3:(10:4:(10:5([])))))
rIntersperse :: a -> [a] -> [a]
rIntersperse e = tail . foldr (\ x acc -> e:x:acc) []

-- Intersperse with foldl' (strict, bad cause uses ++)
--
-- intersperse 10 [1,2,3,4,5]
-- with foldl expanded:
-- ((((1 f 2) f 3) f 4) f 5)
-- ((((([] ++ [1,10]) ++ [2,10]) ++ [3,10]) ++ [4,10]) ++ [5,10])
lIntersperse :: a -> [a] -> [a]
lIntersperse e = init . foldl' (\ acc x -> acc ++ [x,e]) []

Immagino quella con la foldr è migliore perchè mi permette di lavorare con liste infinite, l'altra no.

@EDIT: beh, guardando l'espansione della versione con foldl', si vede che è uno schifo :D

[marco.r]

Immagino quella con la foldr è migliore perchè mi permette di lavorare con liste infinite, l'altra no.

@EDIT: beh, guardando l'espansione della versione con foldl', si vede che è uno schifo :D

Si' esatto, soprattutto crei un sacco di liste inutili. Prima crei una lista di due elementi, poi la butti via per crearne una di quattro, che butti via per creare una da sei...
non si puo' vedere :D

[banryu79]

Si' esatto, soprattutto crei un sacco di liste inutili. Prima crei una lista di due elementi, poi la butti via per crearne una di quattro, che butti via per creare una da sei...
non si puo' vedere :D
Tra l'altro ho provato a immaginare l'espansione nella versione ricorsiva (quella che ci piace di più, non a caso) ed è identica (ma non è una sorpresa) a quella con la foldr... Solo che la cosa è "tipograficamente" esplicita nell'implementazione della funzione stessa.

Scusa le considerazioni forse banali, ma sai com'è quando uno è nuovo...
A proposito di essere newbie: il tuo esempio dell'albero qua sopra l'ho capito, ma non ho ancora visto la definizione di tipi utente (mi riferisco a 'sta roba: data Tree = Leaf | Node Int Tree Tree; data type e compagnia bella per me ancora sono magia nera).

Grazie di nuovo, marco.r :)

[shinya]

(mi riferisco a 'sta roba: data Tree = Leaf | Node Int Tree Tree; data type e compagnia bella per me ancora sono magia nera).
Vuol dire semplicemente che un Tree o è un Leaf o è un Node Int Tree Tree.
Sono due costruttori: uno senza argomenti (Leaf) e uno che prende un intero e due Tree come parametri (Node). Un Tree lo puoi costruire in un modo o nell'altro. Mi spiego?

[banryu79]

Vuol dire semplicemente che un Tree o è un Leaf o è un Node Int Tree Tree.
Sono due costruttori: uno senza argomenti (Leaf) e uno che prende un intero e due Tree come parametri (Node). Un Tree lo puoi costruire in un modo o nell'altro. Mi spiego?
Sì, quello a spanne lo avevo capito, e ho visto che poi fa una sorta di patter matching sui tipi (in insert), avevo visto per la prima volta un concetto simile in Scala.

Scusa, per chiudere il discorso sulle fold{l,r}, mi sembra che foldl e foldr siano concettualmente analoghe alle head e tail recursion, rispettivamente, ha senso o questa analogia la vedo solo io perchè non ho le idee chiare? (sto pensando a implementazioni di funzioni ricorsive in linguaggi imperativi, tipo in C) Grazie :)

[banryu79]

Ancora però non mi è chiara una cosa; avendo queste due implementazioni di length:

-- length implemented with sum and list comprehension
length'' :: (Num b) => [a] -> b
length'' xs = sum [1 | _ <- xs]

-- length implemented with recursion and pattern matching
recLength :: (Num b) => [a] -> b
recLength [] = 0
recLength (_:xs) = 1 + recLength xs

e mandandole in esecuzione in WinGHCi, ottengo questi risultati:

"ghci>" length'' [1..200000]
200000
(0.39 secs, 40215052 bytes)
"ghci>" recLength [1..200000]
200000
(0.58 secs, 46652288 bytes)
"ghci>" length'' [1..1000000]
1000000
(2.73 secs, 185027204 bytes)
"ghci>" recLength [1..1000000]
1000000
(6.44 secs, 209939884 bytes)

Bisogna tenere conto che i valori stampati da GHCi sono:

Display some stats after evaluating each expression, including the elapsed time and number of bytes allocated. NOTE: the allocation figure is only accurate to the size of the storage manager's allocation area, because it is calculated at every GC. Hence, you might see values of zero if no GC has occurred.

Perchè la versione ricorsiva è più lenta di quella che fa uso di sum applicata a una list comprehension?


@EDIT: includo l'implementazione di sum, o usa una foldl oppure la ricorsione, quindi non capisco cosa causa la netta differenza che ho rilevato.

...
-- | The 'sum' function computes the sum of a finite list of numbers.
sum :: (Num a) => [a] -> a
-- | The 'product' function computes the product of a finite list of numbers.
product :: (Num a) => [a] -> a
#ifdef USE_REPORT_PRELUDE
sum = foldl (+) 0
product = foldl (*) 1
#else
sum l = sum' l 0
where
sum' [] a = a
sum' (x:xs) a = sum' xs (a+x)
product l = prod l 1
where
prod [] a = a
prod (x:xs) a = prod xs (a*x)
#endif
...



@EDIT2: Hum, pare abbia a che fare col fatto che recLength è una funzione "almost tail recursive", infatti se ne implmento la versione veramente "tail recurvise" i risultati sono molto vicini a quelli di length''

-- length: real tail recursion (must use an accumulator)
tailLength :: (Num b) => [a] -> b -> b
tailLength [] acc = acc
tailLength (x:xs) acc = tailLength xs (1 + acc)

risultati:

"ghci>" length'' [1..1000000]
1000000
(2.69 secs, 185237624 bytes)
"ghci>" recLength [1..1000000]
1000000
(6.48 secs, 209938376 bytes)
"ghci>" tailLength [1..1000000] 0
1000000
(2.98 secs, 180103352 bytes)

Che palle però :D
Meglio che continuo con il tutorial guidato, mi sa che sono uscito troppo dal seminato, e questi sono aspetti più avanzati del linguaggio e forse riguardano anche come è implementata la piattaforma... torno a studiare.

[marco.r]

@EDIT2: Hum, pare abbia a che fare col fatto che recLength è una funzione "almost tail recursive", infatti se ne implmento la versione veramente "tail recurvise" i risultati sono molto vicini a quelli di length''

-- length: real tail recursion (must use an accumulator)
tailLength :: (Num b) => [a] -> b -> b
tailLength [] acc = acc
tailLength (x:xs) acc = tailLength xs (1 + acc)

risultati:

Che palle però :D
Meglio che continuo con il tutorial guidato, mi sa che sono uscito troppo dal seminato, e questi sono aspetti più avanzati del linguaggio e forse riguardano anche come è implementata la piattaforma... torno a studiare.
direi di si'.
Comunque l'analisi delle prestazioni e della memoria in un programma lazy e' argomento tutt'altro che banale eh (pero' ci si guadagna in una maggiore facilita' nel analizzarne la correttezza).
Anche in questo caso, e visto che sommiamo valori (i.e. non dobbiamo generare liste parziali) puo' valere la pena forzare un po' di strictness.
Ad esempio possiamo prendere la versione con accumulatore e forzare il calcolo della somma ad ogni passaggio:

length3 x = f 0 x
where f acc [] = acc
f acc (x:xs) = acc `seq` f (1+acc) xs

(qui con "seq" diciamo al programma che prima ci calcolare la parte a destra deve effettuare il calcolo della parte a sinistra, ovvero di acc).
Per fare un esempio sulla mia macchina ottengo i seguenti valori

*Main Data.List> length'' [1..10000000]
10000000
(35.49 secs, 3178182056 bytes)

*Main Data.List> length3 [1..10000000]
10000000
(4.91 secs, 2984878736 bytes)

Ma soprattutto quel "sum = foldl (+) 0" chiama un po' vendetta... occhio se al posto uso foldl' :

length4 xs = foldl1 (+) 0 [ 1 | _ <- xs ]

*Main Data.List> length4 [1..10000000]
10000000
(2.94 secs, 1691837800 bytes)

[banryu79]

Ma soprattutto quel "sum = foldl (+) 0" chiama un po' vendetta... occhio se al posto uso foldl' :

length4 xs = foldl1 (+) 0 [ 1 | _ <- xs ]

*Main Data.List> length4 [1..10000000]
10000000
(2.94 secs, 1691837800 bytes)

Ammazza che fetecchia! (intendo l'implementazione di sum in GHC) :D
Guarda qua, sulla mia macchina, con sum e queste due funzioni:

import Data.Foldable (foldl')

-- sum with lazy left fold
lazySum :: (Num a) => [a] -> a
lazySum = foldl (+) 0

-- sum with strict left fold
strictSum :: (Num a) => [a] -> a
strictSum = foldl' (+) 0

ottengo questi risultati:

"ghci>" sum [1..1000000]
500000500000
(2.06 secs, 148476192 bytes)
"ghci>" lazySum [1..1000000]
500000500000
(2.11 secs, 148677428 bytes)
"ghci>" strictSum [1..1000000]
500000500000
(0.25 secs, 131180208 bytes)

La morale dunque è quella che mi avevi già fatto tu: se devi usare foldl forse vale la pena foldl', per foldr invece è meglio la versione lazy, se si vuole lasciare aperta la porta che ne permette l'uso su liste infinite. Inoltre dove ci sta una foldr forse ci sta meglio una chiamata ricorsiva, specie se è una vera e propria tail call. Devo abituarmi al mondo funzionale.

Se non hanno scelto di usare foldl' ci sarà anche un perchè, e mi chiedo quale...