[OT-Haskell]The power of laziness

[Scara95]

Perchè l'essere pigri può semplificarci le cose (lo sto dicendo solo per giustificare il mio stile di vita )
In ogni caso: vi volevo portare qualche piccolo esempio in cui l'essere pigri permette permette di implementare alcune cose in modo semplice e compatto!
Se volete poi metto la spiegazione del codice, nel caso non risulti intuitivo

P.s. io ho utilizzato haskell ma cose simili sono possibili anche in altri linguaggi, ad esempio Clojure è pure molto adatto!

--fibonacci
fibonacci = (fibonacci'!!)
  where
    fibonacci' = 1 : 1 : zipWith (+) fibonacci' (tail fibonacci')

--crivello di Erastotene
primes = (primes'!!)
  where
    primes' = 2 : dropMuls [3,5..]
    dropMuls (x:xs) = x : dropMuls [a | a <- xs, (a `mod` x) /= 0]
    --in alternativa se non si vuole usare la list comprehension
    --dropMuls (x:xs) = x : dropMuls (filter ((/=0) . (`mod`x)) xs)
		
--piramide di tartaglia
tartaglia = (tartaglia'!!)
  where
    tartaglia' = [1] : map tartaglia'' tartaglia'
    tartaglia'' xs = 1 : zipWith (+) xs (tail xs) ++ [1]

[MItaly]

Uhm, forse conviene che metti la spiegazione... alcune cose mi sono familiari (ad esempio le list comprehensions dal Python), ma tante altre mi sfuggono...

[Scara95]

Dimenticavo: se volete provarle basta aggiungere un

main = print $ nomefunzione numero_elemento

Passiamo alla spiegazione (che non volevo fare causa la mia pigrizia ).
Tutte e tre le implementazioni giocano sul fatto che haskell tratta tutte le cose con pigrizia (cioè le calcola solo se necessario) quindi implementano la coda della lista definendola con la lista stessa.
La prima riga di ogni funzione (es. fibonacci = (fibonacci'!!) ) non fa altro che applicare parzialmente l'operatore !! che data una lista e un numero restituisce l'ennesimo elemento. Perciò (lista!!) ritorna una funzione che prende un numero. Le liste fibonacci', primes' e tartagia' sono definite localmente (ho scritto tartaglia1 al posto di tartaglia' scusatemi).
Passiamo alla definizione di fibonacci'.
I primi due numeri della sucessione di fibonacci saranno sicuramente 1 e 1 quindi li inseriamo in testa alla lista. La coda della lista è formata dalla somma dei due numeri precedenti. zipWith è una funzione che data una funzione e due liste restituisce una lista i cui elementi sono l'applicazione membro a membro della funzione sulle due liste

zipWith (+) [1,2,3] [7,8,9] -> [1+7,2+8,3+9]

. La nostra coda sarà allora la somma membro a membro di tutta la sucessione a partire dal primo numero (cioè la fibonacci') e della sucessione senza il primo numero (cioè la coda di fibonacci' (tail fibonacci')).
Tartaglia si basa su un principio simile:
tartaglia'' è una funzione che prende una lista di questo tipo [1,3,3,1] e restituisce la riga sucessiva: [1,4,6,4,1]. Per calcolare la riga usa esattamente lo stesso meccanismo di fibonacci': il primo e l'ultimo elemento saranno certamente 1 e quindi li fissiamo a 1, quelli centrali saranno la somma membro a membro della riga precedente per la sua coda (cioè tutti gli elementi affiancati).
tartaglia' è una lista, il suo primo elemento (cioè la prima riga della piramide di tartaglia) sarà una lista con un solo 1, la coda invece è definita come un map della funzione tartaglia'' sulla lista stessa. Per comprende come funziona bisogna pensare che, mentre si calcolerà il primo elemento di map, cioè il secondo della lista, il primo elemento della lista sarà noto; ora calcolando il secondo elemento di map, cioè il terzo della lista, l'elemento precedente sarà noto; e così via...
primes' è la definizione più complessa.
L'inizio è esattamente lo stesso: il primo numero primo è 2 la coda è definita come l'applicazione della funzione dropMuls sulla lista infinita dei numeri dispari [3,5...]
Passiamo alla complessa definizione di dropMuls.
(x:xs) non fa altro che scomporre la lista in testa (x) e coda (xs). La testa sarà sicuramente un numero primo perciò lo inseriamo nella lista, alla coda invece applichiamo dropMuls dopo averla privata di tutti i multipli della testa. Per privarla di tutti i multipli, come avrete visto, ho proposto due metodi uno semplice che usa la list comprehension:

[a | a <- xs, (a `mod` x) /= 0]

la lista conterrà tutti quegli elementi a tali che questi appartengano a xs e il resto della loro divisione per x (che era la testa della lista) sia diverso (/=) da 0.
La seconda implementazione sfrutta le capacita di composizione di Haskell e l'applicazione parziale: . è una funzione che prende due funzioni e le compone (sempre che il type system non si lamenti, in quanto, anche se non sembra, haskell è fortemente tipizzato).
(/=0) è l'applicazione parziale di diverso (/=) è restituisce una funzione de dato un numero controlla se è diverso da zero.
(`mod`x) si basa su un'altra proprietà di Haskell: ogni funzione può essere resa infissa se il suo nome viene preceduto e succeduto da un backtick (`) quindi è l'applicazione parziale nel suo secondo argomento della funzione mod.
La funzione passata a filter sarà quindi la composizione di queste due funzioni parzialmente applicate nell'ordine:
(`mod`x) prenderà un numero e calcolerà il suo resto per x
questo sarà l'argomento di (/=0) che controllerà che questo sia diverso da 0
a questo punto la funzione filter non farà altro che scartare quegli elementi dove ((/=0) . (`mod`x)) sia falsa.

Se dovessi non essere risultato chiaro in alcuni punti chiedete pure (d'altra parte ho scritto di getto)!