Mentre Juhan vi ha appena spiegato come cambierà la serie “frattanto…” io continuo con i miei post sulla programmazione funzionale. Anzi, oggi ci collegheremo anche ad un altro post del collega Juhan, dato che il blog sta diventando sempre di più un esperimento collettivo, piuttosto che una semplice somma della parti!
E sempre a proposito dei “colleghi”, volevo dire che lo scorso fine settimana sono andato a Torino per una gita di piacere, e così abbiamo avuto finalmente l’opportunità di incontrarci di persona con Juhan e dikijwolk, e devo dirvi che sono veramente contento, e spero avremo altre occasioni di incontrarci! Perché va bene il virtuale, ma il reale è sempre un’altra cosa. E naturalmente speriamo di incontrarci anche con Piergiu prima o poi!
Ma bando alle ciance, si comincia.
Puntate precedenti:
Soluzioni degli esercizi
Non avrete mica creduto che me ne fossi scordato! Cominciamo dal primo:
- Scrivere la definizione della funzione map in Haskell.
Va beh, questa è banale, dai:
map f [] = []
map f (x:xs) = f x : (map f xs)
Cioè: la map applica la funzione f a tutti i membri della lista. Quindi, se la lista è vuota, restituisce una lista vuota; se invece la lista è formata da una testa x e una coda xs, la lista risultate avrà come testa f x e come coda map f xs.
Si può scrivere anche in un altro modo:
map f [] = []
map f list = f head list : map f tail list
C’è una sottile differenza fra i due modi di scrivere, ma per ora ignoriamola. Passiamo ora al secondo esercizio:
- Scrivere una funzione xmap che, data una lista di funzioni (Integer -> Integer), e una lista di Integer, da in uscita una lista di Integer pari al risultato dell’applicazione delle funzioni della prima lista agli elementi della seconda. In pratica, il risultato di xmap (map (+) [1,2]) [10, 11] sarà [11, 13], mentre il risultato di xmap (map (^) [3, 4]) [2, 3] ) sarà [9, 64]
Ed ecco la soluzione:
module Main where
import System.Environment
xmap [] _ = []
xmap _ [] = []
xmap (f:fs) (x:xs) = (f x) : (xmap fs xs)
main :: IO()
main = do args <- getArgs
putStrLn("Result : " ++ show(xmap (map (^) [3, 4]) [2, 3] ))
E questa è anche compilabile e eseguibile. L’unico simbolo che non ho ancora spiegato è l’underscore _. Significa “variabile senza nome”. Questo perchè non mi interessa cosa si sia al posto di quella variabile (non lo uso a destra dell’uguale). Quindi, le prime due equazioni ci dicono che se la prima o la seconda lista sono vuote, il risultato è la lista vuota. Per quanto riguarda la terza equazione, dopo la spiegazione della map, penso sia superfluo spiegarvi questa, no?
Tuple
Sia in Python che in Haskell ci sono le tuple, che potete pensare come coppie o triplette di dati. Ad esempio, se volete rappresentare un punto in uno spazio cartesiano bidimensionale, vi servono due numeri reali: per esempio, sia in python che in Haskell, il punto di coordinate x = 5 e y= -3 si potrebbe rappresentare con una coppia così
p = (0.5, -3)
A differenza delle liste, le tuple sono strutture dati con un numero fisso di elementi. Ad esempio, tutte le coppie di reali, oppure tutte le triplette di reali ecc. In altre parole, non esistono modi di “appendere” elementi a una tupla, come avviene per le liste. Inoltre, in Haskell le liste devono avere elementi tutti dello stesso tipo (mentre in Python le liste possono avere elementi di tipo diverso), e le tuple invece possono avere elementi di tipo diverso. Per chi viene dal C/C++ o dal Java, le tuple sono l’equivalente delle strutture dati.
Un esempio di tupla con tipi di dato diversi, in Python:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
c = ("Pippo", 25)
print "Nome: " + c[0] + " età: " + `c[1]` + " anni"
La variabile c è una coppia formata da una stringa e da un intero, che nell’intento del programmatore rappresentano nome ed età di una persona. Per accedere all’elemento i-esimo si usa la stessa notazione delle liste.
E in Haskell:
c = ("Pippo", 25)
...
putStrLn( "Nome : " ++ (fst c) ++ " età: " ++ show(snd c) )
c è definita come una coppia. La funzione fts prende il primo elemento della coppia (che è una stringa) mentre snd c ritorna il secondo elemento della coppia (che è un intero). La funzione show trasforma l’intero in una stringa, l’operatore ++ concatena le stringe, e infine la funzione putStrLn fa l’output a video.
A proposito: se volete provare codice Haskell al volo, potete lanciare il comando gchi che è un interprete. L’unica cosa è che non potete scrivere equazioni così come le scrivo io: quindi, per verificare il codice precedente, lanciate gchi, e poi fate le cose seguenti:
lipari@lipari$ ghci
GHCi, version 7.0.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> ("Pippo", 25)
("Pippo",25)
Prelude> putStrLn( "Nome : " ++ (fst it) ++ " età: " ++ show(snd it) )
Nome : Pippo età: 25
Prelude>
La scritta Prelude> è il prompt. Se scrivete un’espressione (come ad esempio (“Pippo”, 25)), il risultato viene memorizzato nella variabile implicita it.
Liste infinite
Oggi parliamo di nuovo di come generare i numeri di Fibonacci. Se andate a riguardare il post di Juhan, vediamo che in Python possiamo usare sia una definizione ricorsiva che una iterativa, e quest’ultima è probabilmente più veloce. In realtà, proveremo ad esprimere un problema solo leggermente diverso: vogliamo la sequenza dei primi n numeri di Fibonacci. Ecco un esempio di codice Python:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys
def fib(n):
list = [1, 1]
for i in range(2, n) :
list.append(list[i-1]+list[i-2])
return list
n = int(sys.argv[1])
print fib(n)
Questo programma legge un intero dalla linea di comando, e stampa la sequenza di Fibonacci fino al numero desiderato. Quindi:
lipari@lipari$ python fib.py 20
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
Inoltre poiché Python è intelligente, usa un tipo di intero illimitato, cioè possiamo arrivare senza paura a chiedere sequenze molto lunghe, tipo i primi 1000 numeri di Fibonacci, anche se il millesimo non è molto simpatico da leggere.
E adesso vediamo come fare la stessa cosa in Haskell. Su questo wiki ci sono alcune possibili implementazioni della sequenza di Fibonacci in Haskell, e giustamente si dice che questo programma è come l'”Hello World” di Haskell! Io mi limiterò a spiegarvi l’implementazione canonica con zipWith.
Cominciamo con il dire che in Haskell si possono definire liste infinite.
COME??? MA STAI SCHERZANDO, VERO???
Sì, si può fare, e no, non sto scherzando. Ecco ad esempio una possibile definizione di una lista composta da soli numeri 1:
ones = 1:ones
Ed ecco la definizione di una lista contenente tutti i numeri naturali:
naturals = [1..]
So che il vostro cervello in questo momento si rifiuta di accettare questa cosa. “Se la memoria di un computer è finita, non c’è nessun modo per calcolare una lista infinita di numeri.” E infatti avete ragione! “Ah, ecco, ma vuoi farci diventare matti?”. No, dai, rileggiamo per bene quello che ho scritto: ho detto che è possibile definire una lista infinita, ma ovviamente non è possibile calcolarla perché ci vorrebbe memoria infinita e tempo infinito!
Ed ecco il punto fondamentale, la pietra angolare che rende Haskell così differente dagli altri linguaggi imperativi come Python.
In un linguaggio come il C o il FORTRAN (e in tutti i loro derivati) l’operatore di assegnamento è indicato dal simbolo =. Quindi se scrivo x = 2 sto operativamente ordinando al processore di scrivere 2 nella zona di memoria che ho chiamata x. E il processore dovrà farlo, prima di poter passare ad eseguire il prossimo ordine. Questa cosa qui è talmente entrata nell’uso della programmazione che ormai quando vediamo un = noi programmatori pensiamo all’assegnamento. Invece, i matematici hanno sempre mal sopportato questo “abuso” di notazione: per un matematico il simbolo di uguale è semplicemente una “dichiarazione” che la parte sinistra e la parte destra sono uguali, quindi un’equazione!
Per cercare di ovviare a questo “qui pro quo”, l’inventore del Pascal, per esempio, decise di usare la notazione “:=” per l’assegnamento, e il semplice uguale per la comparazione. Altri linguaggi utilizzano “<-“, o altri strani simboli.
In Haskell, l’uguale indica semplicemente una definizione, come il def in Python. Quindi, se scrivo naturals = [1..] non sto ordinando al processore di enumerare tutti i numeri naturali, ma sto semplicemente asserendo che il simbolo naturals è definito come [1..], senza implicare nessun calcolo. Haskell è un linguaggio pigro: non calcola niente a meno che non sia costretto a farlo. Quindi, a meno che il programma non usi il simbolo naturals da qualche parte, Haskell non ne calcolerà il valore. E naturalmente posso usare naturals in altre definizioni, senza che ci sia alcun calcolo coinvolto:
squares = map (^2) naturals
Ancora una volta, Haskell evita di svolgere alcun calcolo. Semplicemente, prende nota che per calcolare squares dovrà applicare la funzione map utilizzando come primo argomento l’elevamento al quadrato, e come secondo argomento la lista dei naturali.
Ora vi starete chiedendo: ma allora, quando li fa i calcoli Haskell? Beh, per esempio quando deve stampare a video un risultato. Se voi scrivete sull’interprete il seguente comando:
Prelude> map (^2) [1..]
l’output semplicemente non si fermerebbe più (andrebbe in un ciclo infinito).
Per inciso: scrivere sull’interprete equivale a chiamare la funzione putStrLn e la funzione show. Quindi, quello scritto sull’interprete, in un programma sarebbe:
putStrLn(show(map (^2) [1..]))
Provate a farlo, e vedrete che i risultati vengono stampati a schermo uno per uno! Fate mente locale, e state ben attenti qui: non è che Haskell prima calcola l’intero risultato della map e poi mostra tutto l’insieme, perché in questo caso sullo schermo non vedreste nulla, perché il calcolo della map semplicemente non termina! Invece, la map costruisce i valori uno alla volta, e ogni valore viene convertito in stringa e stampato sullo schermo. Forse avevamo frainteso un po’ il modo che Haskell ha di calcolare sulle liste, eh?
Si dice che Haskell usa la lazy evaluation; cioè calcola i valori man mano che servono e solo se servono. Facciamo adesso un esempio di programma che stampa i quadrati dei primi 10 numeri naturali. Eccolo:
Prelude> take 10 (map (^2) [1..] )
[1,4,9,16,25,36,49,64,81,100]
La funzione take parte da una numero intero n e da una lista, e restituisce la sottolista contenente i primi n elementi. In questo caso, il programma termina dopo aver stampato i 10 numeri. Perché? Perché Haskell è lazy: non ha bisogno di calcolare tutti i valori del secondo argomento della take, gli bastano solo i primi 10.
Fibonacci
Prima di spiegare la sequenza di Fibonacci, ci manca una funzione: zipWith. Ecco la signature.
zipWith :: (a->b->c) -> [a] -> [b] -> [c]
La funzione prende 3 argomenti: una funzione di due argomenti (di tipo a e b, rispettivamente) e che ritorna un risultato di tipo c; una lista di elementi di tipo a; e una lista di elementi di tipo b (a, b e c possono anche essere lo stesso tipo, per esempio Integer). La funzione prende tutti gli elementi dalla prima lista e i corrispondenti elementi dalla seconda, applica la funzione, e ottiene degli elementi che mette nella lista risultato. Si fa molto prima a mostrare un esempio:
Prelude> zipWith (+) [1,3,5] [2, 4, 6]
[3,7,11]
A questo punto siamo pronti per definire la lista di tutti i numeri di Fibonacci. Ed eccola:
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Ecco, lo so che vi gira la testa: liste infinite ricorsive! (ma chi l’ha inventato Haskell? un sadico?)
(Ecco come deve sentirsi il vostro cervello dopo una cosa del genere!)
Piano piano, dai che ce la possiamo fare! Supponiamo di avere già una lista che contiene i numeri di Fibonacci, che qualcuno l’abbia scritta per noi e ce ne abbia fatto gentilmente dono. Proviamo a enumerare i primi 10 numeri di Fibonacci.
1, 1, 2, 3, 5, 8,13,21,34,55
Ok, ora scriviamoci sotto la stessa lista, ma eliminando il primo elemento:
1, 1, 2, 3, 5, 8,13,21,34,55
1, 2, 3, 5, 8,13,21,34,55,..
Se provate a sommare in colonna:
1, 1, 2, 3, 5, 8,13,21,34,55
1, 2, 3, 5, 8,13,21,34,55,..
------------------------------
2, 3, 5, 8,13,21,34,55,89,..
Ovvero, ottenete la stessa lista senza i primi due elementi. Ovvio, no? Ora proviamo a leggere l’uguaglianza Haskell di prima. Si dice che la sequenza di Fibonacci è equivalente a due 1 consecutivi, seguita dalla somma della sequenza di Fibonacci con la sequenza di Fibonacci shiftata di 1 a sinistra. Abbiamo scritto una proprietà della sequenza!
Ok, ma chi darà a Haskell la sequenza di Fibonacci per cominciare e verificare l’uguaglianza? Nessuno, se la ricava da solo a partire dall’uguaglianza, che funziona anche come una definizione, o se volete come un’equazione! Ed ecco il programma completo:
module Main where
import System.Environment
main :: IO()
main = do args <- getArgs
putStrLn("Fibonacci until " ++
(args !! 0) ++
" = " ++
show( take (read (args!!0)::Int) fib ) )
fib :: [Integer]
fib = 1:1: zipWith (+) fib (tail fib)
Nel main, prendo un argomento sulla linea di comando (la variabile args è la lista delle stringhe contenenti gli argomenti sulla linea di comando, come argv[] in C/C++, e args!!0 è il primo elemento della lista), lo converto ad intero (con la read(args!!0)::Int) e lo passo alla take insieme a fib.
Ultima cosuccia: sul mio computer ho provato a paragonare i tempi di esecuzione del programma Python, del programma Haskell, e diun programmino C++ che fa la stessa cosa, al variare di n. Tutti i tempi nella tabella sono in millisecondi, e li ho presi leggendo l’output di time (in particulare, la riga real). Al solito, nessuna pretesa di scientificità (anche se in quanto ricercatore dovrei essere più accurato, lo so…), prendete tutto con il beneficio del dubbio.
| N |
100 |
200 |
400 |
600 |
1000 |
| Python |
50 |
52 |
56 |
60 |
75 |
| Haskell |
9 |
10 |
15 |
18 |
40 |
| C++ |
7 |
9 |
11 |
15 |
32 |
come vedete Haskell non è niente male, direi abbastanza paragonabile al C++. Mentre i tempi di Python probabilmente scontano il ritardo iniziale dovuto all’interprete: infatti, se togliete 40ms da ciascuna della caselle della prima riga, otterrete numeri decenti.
Conclusioni
Beh, oggi è stata dura. Fatemi sapere se non avete capito, o se ho scordato qualcosa. La prossima volta è venuto il momento di fare un intermezzo storico.
. Se vogliamo scrivere un semplice programmino Python che calcola il fattoriale potremmo fare come nel listato seguente:
. Più o meno ci siamo. 
