Archivi Categorie: Haskell

Parto con un nuovo linguaggio

Cioè no, c’era stata una falsa partenza ma adesso mi metto su davvero. Promesso.
Ma prima una premessa: quando ero nuovo nel campo c’era chi proponeva un linguaggio buono per tutti e io ero anche andato a una presentazione a Milano, credo da parte di IBM ma non ne sono sicuro (e c’è il rischio che ZAP poi mi cazzia come per APL).

Il linguaggio era PL/1, sì credo proprio che fosse IBM. Questo secondo i suoi proponenti sarebbe andato bene (anzi meglio) per tutto. Le cose poi sono andate molto diversamente. Sono nati millemila linguaggi, ognuno specifico per un campo particolare (+/-, nèh!).

E si continua, anche se mi sembra che il ritmo sia rallentato (e poi sono fuori, non aggiornato). Ultimamente poi va di moda riciclare i vecchi, come quando (sempre da piccolo) si usavano i cappotti rivoltati (a me rifilavano quelli). Dal Basic originale sono nati discendenti targati M$ irriconoscibili, è cambiato anche il Fortran, dal C è nato il C++ che periodicamente viene rimescolato.

Certo ce ne sono anche di (relativamente) nuovi, come Python, Ruby, Haskell e Erlang. Non è che li inseguo tutti, anzi…
Ho amici che usano abitualmente Lua, Ruby, Delphi e simili ma io sono più conservativo.
Dalla mia lista di blog RSSati ecco quelli che seguo (o vorrei seguire).

Go
command center
go with confidence
The Go Programming Language
doxsey.net

Haskell
Bartosz Milewski’s Programming Cafe
FP Complete
Inside ###
Hello | David Siegel
yannesposito.com

Python
I say things
J5’s Blog
Jesse Noller
Kunigami’s Blog
Markon’s blog
Open resource
Palmux | Dall’informatica al rock and roll e ritorno…
Python Conquers The Universe
Python Examples
Robitex’s Blog
SaltyCrane Blog
Satyajit Ranjeev
Sebastian Pölsterl’s blog
SlashCode
tartley.com
The Endeavour
The Mouse Vs. The Python
Stanzinofree
Pythonic Perambulations

Forse ne ho dimenticato qualcuno, forse qualcuno è abusivo. Qualcuno è monomaniaco, altri polymaniaci, insomma è un tentativo.
Poi ci sono altri linguaggi ma questi sono quelli più sexy cool, secondo me, ora. E cambio spesso idea.
Esaminando la lista sembrerebbe che voglio parlare di Python, vero?
Sbagliato! Anche se è appena partito un corso –facile-facile– al quale partecipo, trovate tutto da Bit3Lux, no non è lui, basta Python.

Haskell mi risulta difficile da metabolizzare, ha una sintassi mooolto diversa dal solito, forse avendo un caso cui applicarlo, costretto…
E poi è considerato un rivale del mio linguaggio preferito, non voglio che si pensi che lo sto tradendo (anche se appena lo nomino cala il gelo (per questo non vi dico qual è)).

Go, ecco! questo m’intriga. I padri di Unix erano tutti per il C. Nessuno di loro, per quel che ne so, ha mai endorsato il C++. Neanche Rob. E siccome il C è nato in un’altra era è giunto il momento di fare qualcosa di nuovo, che risponda a nuove necessità intervenute e corregga alcune cose che potevano essere fatte meglio. Per esempio liberarsi dei punti-virgola non necessari. Ecco, provo a raccontare qualcosa di Go. Oltre che sui documenti del sito ufficiale del linguaggio ho una guida semplice e ben fatta: An Introduction to Programming in Go di Caleb Doxsey, si può trovare qui o qui.

Ah, sì, quidi libri ne trovate tantissimi, fateci un salto, se vi va.

Speruma, direbbero a Türin ;-)

Ancora regine

Ed ecco un nuovo post funzionale. Oggi non mi sforzerò più di tanto perché vi propongo la soluzione in Haskell del problema delle regine, di cui avevo già parlato qualche eone fa, ricordate? No, allora ripeto velocemente.

Lo so, non c'entra niente con il post, ma Elisabetta I è la regina par excellence, no?

Avete una scacchiera NxN e dovete piazzare N regine in modo che non si possano catturare a vicenda. Il problema ha zero soluzioni per N minore di 4, una soluzione per N uguale a 4, un numero crescente di soluzioni al crescere di N.

Nello scorso post vi ho chiesto di mettere nei commenti le vostre implementazioni in vari linguaggi di programmazione, e ne sono arriva un po’, da Mathematica a Ruby passando per il Pascal! Grazie al buon Dikiyvolk e a HopfMap! Nessuno però mi ha tolto le soluzioni equivalenti per rotazione e le soluzioni speculari. E allora oggi vi propongo la mia soluzione in Haskell che vi fornisce anche le soluzioni uniche.

Per prima cosa, come rappresento una soluzione? Nel programma C dello scorso post creavo una matrice di caratteri NxN che mi rappresentava la scacchiera. Ma naturalmente non è l’unico modo di rappresentare una soluzione. Un altro modo è di rappresentare la posizione di una regina con le sue coordinate x e y sulla schacchiera; e una soluzione come una lista di N regine. Per cui, ad esempio, nel caso di N = 4, una soluzione è la seguente:

[[(0,2),(1,0),(2,3),(3,1)]]

Le coordinate x e y naturalmente vanno da 0 a N-1. Non è molto accattivante dal punto di vista visivo, ma è una lista, e si tratta molto bene in Haskell!
E allora, bando alle ciance, ecco il programino.

module Main where
import Data.List
import Data.Ord
import Data.Function

dim = 4

main = 
  do putStrLn ("Solutions:     " ++ (show (length queens)) ++ "\n" ++ (show (queens)))
     putStrLn ("No duplicates: " ++ (show (length queensnd)) ++ "\n" ++ (show (queensnd)))

-- true se le due regine non sono in conflitto
noconflict (x1,y1) (x2,y2) = (abs(x1-x2) /= abs(y1-y2)) && (x1 /= x2) && (y1 /= y2)  

-- true se la posizione (x, y) è ammissibile rispetto alla lista di regine
allow l (x,y) = and (map (noconflict (x,y)) l)

-- piazza le regine in tutti i modi possibili nelle righe da 0 a i inclusa
-- restituisce la lista delle soluzioni 
-- (ogni soluzione è una lista di i posizioni)
myqueens :: Int -> [[(Int,Int)]]
myqueens i 
  | i == 0    = all_pos_in_row 0 []
  | otherwise = [ x ++ y | x <- (myqueens (i-1)), y <- (all_pos_in_row i x) ] 
    where all_pos_in_row r list = group(filter (allow list) [ (r,c) | c <- [0..(dim-1)] ])

-- chiama myqueens su dim-1, seleziona (con filter) le soluzioni di lunghezza 
-- dim (quindi quelle in cui ci sono dim regine), 
queens = (filter (\x -> (length x) == dim) (myqueens (dim-1)))

-- e da queste elimina quelle 
-- identiche per rotazioni e riflessioni chiamando la funzione edup definita
-- più sotto 
queensnd = edup queens

-- ruota una soluzione in senso orario di 90 gradi
rotate list = sortBy (compare `on` fst) [(y, dim-1-x) | (x, y) <- list ]
-- produce la soluzione riflessa
spec list = [ (x, dim-1-y) | (x, y) <- list ]
                                        
--- una prova con foldr e scanr                          
edup list = foldr (reflrot) [] (list)
  where reflrot x l = if (rotate x) `elem` l || 
                         (rotate (rotate x)) `elem` l ||
                         (rotate (rotate (rotate x))) `elem` l ||
                         (spec x) `elem` l
                      then l 
                      else l ++ [x]

Allora, al solito per compilare basta scrivere sul terminale:

ghc queens.hs

dove queens.hs è il nome che avrete dato al file. E

./queens

per eseguire.

Il programma ha più commenti che linee di codice. E questa è una delle particolarità di Haskell: il codice viene sempre molto succinto, forse a causa della sintassi particolare, forse a causa del fatto che è un linguaggio funzionale che ti obbliga ad essere succinto!

Brevemente, la funzione che ha bisogno di essere spiegata di più è forse myqueens. Questa si realizza con una serie di funzioni di appoggio:

  • all_pos_in_row: cerca di piazzare in tutti i modi legali possibili delle regine sulla riga r. In output quindi da una lista di soluzioni parziali (con le regine messe fino alla riga r). Quando r è 0, genera dim soluzioni parziali del tipo [(0,0)], [(0,1)], [(0,2)] ecc. Quando r è maggiore di 0, gli vengono passate anche le soluzioni parziali precedenti, e lei seleziona solo quelle ammissibili. Ad esempio per r pari a 1, genera [(0,0),(1,2)], [(0,0),(1,3)], [(0,1), (1,3)], ecc.
  • Per capire quali soluzioni sono legali, si usa la funzione allow, definita più su, che a sua volta usa la funzione noconflict

Ok, adesso, per generare tutte le soluzioni, non resta che chiamare myqueens (dim-1), e selezionare solo quelle che contengono almeno dim regine! E con questo abbiamo già finito.

Ma se vogliamo anche eliminare le soluzioni equivalenti per rotazione e riflessione, beh, quello lo fa la funzione queensnd, che prima calcola tutte le soluzioni chiamando queens, e poi elimina quelle equivalenti. Come? Innanzitutto, mi sono definito le funzioni spec e rotate per fare il riflesso e la rotazione di 90 gradi di una soluzione (notare che dopo una rotazione, riordino le posizioni in base alla riga, ovvero al primo elemento della coppia (x,y)). Dopodiché, la funzione edup fa l’eliminazione, facendo un’operazione di reduce (inversa della map!) tramite la foldr che utilizza la funzione reflrot per eliminare man mano le soluzioni equivalenti.

Alcune considerazioni

  • Nel main, queens viene chiamata 2 volte: direttamente la prima volta, indirettamente dalla queensnd la second volta. Ebbene, Haskell fa il calcolo una volta sola, e memorizza il risultato in una cache, così la seconda volta se lo trova già pronto. Può farlo perché queens è una funzione pura: non ha side effects, quindi ogni volta che la chiami produce sempre lo stesso risultato!
  • questa proprietà che le funzioni pure non influenzano lo stato globale, e quindi ritornano sempre gli stessi valori a parità di parametri, è una proprietà importantissima che rende i linguaggi funzionali estremamente interessanti per la programmazione concorrente e parallela, e in particolare per evitare race conditions e strani errori di concorrenza. Ma di questo ne parlerò in un post futuro.

Ok, per stasera ho chiuso! Se avete dubbi sul programma, chiedete e vi sarà risposto!

Eratostene in Haskell

Oggi vediamo come si possa calcolare la sequenza dei primi m numeri primi utilizzando il crivello di Eratostene con Haskell. In realtà, faremo un post molto breve che non è altro che una piccola esercitazione di programmazione in Haskell. Se davvero voleste scrivere un algoritmo super efficiente per calcolare una sequenza di numeri primi, dovete guardarvi questo post e perdere un bel po’ di tempo a studiarvi tutte le varianti proposte.

Ma poiché il tempo a nostra disposizione è quello che è; e oggi è una bella giornata e c’è il sole; i figli richiedono la mia presenza; per tutti questi motivi sarò breve e commenterò solo la prima soluzione semplice per realizzare un crivello di Eratostene.

L’algoritmo è semplicissimo: prendete la lista dei primi m numeri naturali (a partire da 2), e toglieteci tutti i multipli di 2; poi prendete il secondo elemento della lista, cioè il 3, e togliete tutti i multipli di 3; poi prendete il terzo elemento della lista, cioè il 5, e togliete tutti multipli di 5; e così via. Ne ha parlato anche il nostro amico zar in un suo post.

E’ molto semplice scrivere un algoritmo così in Haskell. Supponiamo di saper già fare la sottrazione tra due liste con una funzione che si chiama `minus`. Allora, i primi m primi si calcolano così:

primesTo m = 2 : eratostene [3,5..m] where
  eratostene []     = []
  eratostene (p:xs) = p : eratostene (xs `minus` [p, p+2*p..m])

Vediamo un po’ di capirci qualcosa. Definiamo al solito una funzione per calcolare la lista dei primi fino a m. Tale funzione è pari alla lista contenente il numero 2 in testa, seguita dalla lista prodotta da un’altra funzione locale chiamata eratostene. Alla quale passiamo la lista dei numeri dispari fino a m.

La funzione eratostene è ricorsiva: se gli diamo una lista vuota, ritorna una lista vuota. Se gli diamo una lista con in testa il numero p (che assumiamo essere già primo) e una lista xs, ci da come risultato una lista che contiene in testa il numero p, e in coda la lista ottenuta cancellando da xs la lista contenente tutti i multipli dispari di p fino a m (scritta come [p, p+2*p..m]).

Sintentico ed elegante come al solito! Vi torna? Se avete qualche dubbio scrivetelo nei commenti

Rimane da capire come si realizza la funzione `minus` in maniera elegante e soprattutto efficiente. Fare la sottrazione non è difficile in generale, il difficile è farlo in maniera efficiente. In effetti, la prima semplice soluzione sarebbe di prendere ogni elemento da xs e vedere se si trova nella lista [p, p+2*p..m]. Ma questo significa che per ogni elemento di xs dobbiamo scorrere tutta la lista [p, p+2*p..m]. Quindi, la complessità sarebbe pari al prodotto delle dimensioni delle due liste. Non c’è una maniera migliore di farlo?

La risposta è sì se assumiamo che le due liste siano ordinate in ordine crescente. Ed ecco l’algoritmo:

minus (x:xs) (y:ys) = case (compare x y) of
  LT -> x : minus xs (y:ys)
  EQ -> minus xs ys
  GT -> minus (x:xs) ys

minus xs _ = xs

Immanzitutto, stiamo utilizzando un nuovo costrutto che si chiama case of, ed è piuttosto simile allo switch case del C. Qui l’argomento del case è il risultato della funzione compare, che è una delle tre costanti LT (less than), EQ (equal) o GT (greater than). In particolare, se x è minore di y, allora il risultato di minus è x seguito da xs `minus` ys. Se invece x e y sono uguali, allora bisogna rimuovere x, e quindi il risultato è semplicemente xs `minus` ys. Infine, se x è maggiore di y, allora devo semplicemente scorrere la seconda lista e quindi il risultato è (x:xs) `minus` ys.

L’ultimo pezzo serve nel caso in cui la seconda lista sia vuota. In quel caso, il risultato della “sottrazione” tra liste è semplicemente la prima lista. La complessità di questo algoritmo è pari, nel caso peggiore, al numero totale di elementi nelle due liste.

Ed ecco il codice complessivo:

module Main where
import System.Environment

main :: IO()
main = do args <- getArgs
          putStrLn ( show $ primesTo (read $ args!!0) )

primesTo m = 2 : eratostene [3,5..m] where
  eratostene []     = []
  eratostene (p:xs) = p : eratostene (xs `minus` [p, p+2*p..m])

minus (x:xs) (y:ys) = case (compare x y) of
  LT -> x : minus xs (y:ys)
  EQ ->     minus xs ys
  GT ->     minus (x:xs) ys

minus xs _ = xs

Ed eccoci arrivati in fondo. Con questo post si conclude una prima parte di questo minicorso sui linguaggi funzionali e sul linguaggio Haskell. Per completare ci servono: strutture dati e programmazione sequenziale con Haskell (sì, si può!) e con le monadi. Alla prossima!

Numeri primi in Haskell

Rieccoci con la serie di post sulla programmazione funzionale, finalmente (o purtroppo, dipende dal vostro gradimento). Oggi cercheremo di realizzare un semplice test per i numeri primi in Haskell. Lo scopo è di essere didattici, non di essere efficienti, quindi i matematici e i super esperti portino pazienza, per favore!

Vediamo prima di fare un po di sommario.

Puntate precedenti:

Ripasso di Haskell

Sì, perché l’ultima volta è stata un sacco di tempo fa, e allora facciamo un po’ di ripassino.

I linguaggi funzionali prediligono le funzioni. Tutto è funzione, l’utente definisce funzioni, che possono prendere in ingresso altre funzioni, e ne può fare delle applicazioni parziali per ottenere delle funzioni più semplici. In particolare in Haskell per definire una funzione basta scrivere un’equazione. Ad esempio, ecco la funzione che data una lista ci restituisce un’altra lista contenente solo i numeri pari:

pari :: [Integer] -> [Integer]
pari l = [ x | x <- l, even x ]

Vi ricordo che la prima linea è la type signature, cioè la dichiarazione del tipo di dato che passiamo come argomento in input e del tipo di dato che diamo come output; la seconda linea è invece la definizione vera e propria della funzione. In questo caso abbiamo usato la list comprehension, ricordate? Leggiamolo come se fosse notazione matematica: “tutti gli x tali che x appartiene a l, e x è pari”.

Numeri primi

Per continuare il ripasso, proviamo timidamente a scrivere una funzione che ci dica se un dato intero è primo o no. Per cominciare, ci serve sapere se un numero divide un altro. Si dice che un numero divide esattamente un altro, se il resto della divisione è zero. Quindi, dato n il numero da dividere e x il divisore, deve essere vero che:

n `mod` x == 0

Dove mod è la funzione che calcola il resto. A onor del vero bisognerebbe scrivere

(mod n x) == 0

perché Haskell usa la notazione prefissa. Però chi ha inventato Haskell sa bene che a volte la notazione infissa (quella degli operatori) è più comoda. Per cui ha dato la possibilità di usare entrambe. Se avete una funzione di due argomenti, potete usare la notazione infissa se mettete la funzione tra “backtick”. Quindi, scrivere mod n x è equivalente a scrivere n `mod` x. Chiaro? (se la risposta è no, non vi preoccupate, ci saranno altri esempi nel seguito).

Per fare le cose un po’ più leggibili, definiamoci una funzione chiamata divides:

divides :: Integer -> Integer -> Bool
x `divides` n = n `mod` x == 0

Ok, adesso vogliamo sapere se un numero è primo. La definizione dice che un numero n è primo se è divisibile solo per se stesso e per l’unità. Quindi, dobbiamo provare a dividere n per tutti i numeri da 2 a n-1, e vedere se viene fuori che qualcuno è divisibile.

La lista di numeri da 2 a n-1 si scrive semplicemente [2..n-1]. La funzione divides ci restituisce dei valori booleani, ovvero True oppure False. Se io applico la funzione divides a tutti i membri della lista [2..n-1] ottengo una lista di True e False. Se tutti i valori della lista risultante sono False, allora il numero è primo, mentre se almeno uno è True, allora il numero è composto. Ci siamo fino a qui? Bene, guardiamo il codice che esprime questo mio ragionamento:

isprime :: Integer -> Bool
isprime n = not $ or [ x `divides` n | x <- [2..n-1] ] 

Spiegazione, cominciando dal fondo: qui vedete una bella list comprehension per costruire la lista di booleani (tutti i risultati della funzione x `divides` n tali che x appartiene alla lista [2..n-1]). La funzione or, come ci si aspetterebbe, prende una lista di booleani e ne fa l’or logico. La funzione not restituisce la negazione logica del suo input e ci da il risultato. Direi che ci siamo… no aspetta, e quel dollaro? Il dollaro serve per evitare di mettere troppe parentesi. Infatti, Haskell legge da sinistra verso destra, e se non mettete le parentesi potrebbe incasinarsi: il dollaro serve a dirgli “aspetta che arrivi il risultato di quello che sta a destra del dollaro prima di valutare la funzione che sta a sinistra del dollaro”. Tecnicamente: cambia l’ordine di precedenza delle funzioni, o meglio associa a destra invece che a sinistra.

Ed ecco il programmino risultante:

module Main where
import System.Environment

main :: IO()
main = do args <- getArgs
          putStrLn ( show $ isprime (read $ args!!0) )

divides :: Integer -> Integer -> Bool
x `divides` n = n `mod` x == 0

isprime :: Integer -> Bool
isprime n = not $ or [ x `divides` n | x <- [2..n-1] ] 

Per provare il codice: salvate il testo qui sopra in un file chiamato ‘primo.hs’ (oppure come meglio credete). Quindi, compilate il file da linea di comando con :

ghc primo.hs

e otterrete il file eseguibile primo, che potete eseguire così:

./primo 1237

e dovrebbe restituirvi True.

(Esercizio: che cosa succede se togliete il dollaro senza mettere alcuna parentesi? provare per capire…)

Let e where

Un matematico storcerà il naso a vedere il mio algoritmo. Inefficiente! Infatti, per provare che un numero è primo, è sufficiente testare i numeri da 2 fino alla radice quadrata di n. E allora facciamolo, che aspettiamo?

Per fare la radice quadrata di n si usa la funzione sqtr che però prende un double e restituisce un double (insomma, quasi). Mentre il nostro n è intero: e quindi se scrivo sqrt n il compilatore protesta: come vi ho già detto, Haskell è fortemente, maledettamente tipato, e se non gli dai i tipi giusti non ti compila. E quindi, bisogna trasformare n in un double, e poi il risultato di sqrt di nuovo in intero. Ecco come si fa:

floor $sqrt $fromIntegral n 

Al solito, i dollari evitano le parentesi.

Potremmo mettere l’espressione con la radice quadrata direttamente in linea al posto di n-1, ma sarebbe orribile a leggersi. Potremmo definire una nuova funzione:

sqn n = floor $sqrt $fromIntegral n
isprime n = not $ or [ x `divides` n | x <- [2..sqn n] ] 

ma definire una nuova funzione sembra eccessivo, specialmente se questa funzione viene usata solo dalla funzione isprime. E allora usiamo il let:

isprime :: Integer -> Bool
isprime n = let sqn = floor $sqrt $fromIntegral n  
            in not $ or [ x `divides` n | x <- [2..sqn] ] 

Let serve a definire delle funzioni “locali” alla funzione isprime. Si usa come nella notazione matematica, e quindi si legge così: “sia (let) sqn la radice quadrata di n, nell’espressione not …”. Quindi, dopo il let si mettono le definizioni locali (anche più di una, su righe diverse), quindi la parola chiave in, e infine si mette l’espressione che usa le definizioni precedenti. Altro esempio:

mytan x = let s = sin x
              c = cos x
          in s / c

definisce la tangente di un angolo. Invece di let si può usare un costrutto alternativo che si chiama where:

mytan x = s / c
          where s = sin x
                c = cos x

che si legge: “la funzione mytan x è definita come s / c, dove (where) s è definito come il seno di x, e c è definito come il coseno di x”. Si legge bene, vero?

C’è una differenza importante fra usare let e where. Let può essere messo dovunque ci sia un’espressione, e quindi anche dentro un’espressione più grande. Per esempio, riscriviamo la nostra sqn

sqn n = floor (let i = fromIntegral n in sqrt i)

Come potete vedere, abbiamo inserito una let/in in un’espressione più grande. La where invece può solo essere legata a una funzione, e quindi la seguente cosa dà un errore di sintassi:

sqn n = floor (sqrt i where i = fromIntegral n)

Se proprio volete usare il where, dovete scrivere:

sqn n = floor s 
        where s = sqrt (fromIntegral n)

Lo so, non è chiarissimo, ma nel seguito spero di inserire qualche altro esempio.

Il secondo programmino:

module Main where
import System.Environment

main :: IO()
main = do args <- getArgs
          putStrLn ( show $ isprime (read $ args!!0) )

x `divides` n = n `mod` x == 0

isprime :: Integer -> Bool
isprime n = let sqn = floor $sqrt $fromIntegral n
            in not $ or [ x `divides` n | x <- [2..sqn] ] 

Al solito, fermatevi e prendetevi 30 secondi di tempo per compilare, eseguire, etc. E magari, provate a usare il where invece del let.

Ricorsione!

Adesso siamo un po’ più efficienti, ma ancora lontani da una buona soluzione. Per esempio, possiamo controllare la divisibilità solo per i primi contenuti tra 2 e la radice quadrata di n. Infatti, non ha senso controllare la divibilità per 4 una volta che il numero non è più divisibile per 2. Ed è inutile controllare la divisibilità per 9 se il numero non è divisibile per 3, ecc.

Ma la lista di primi fino alla radice quadrata di n non ce l’abbiamo! Idea: non potremmo utilizzare la stessa definizione di isprime per calcolarci questa lista?

Allora, adesso proviamo a ragionare top/down. Abbiamo già una funzione isprime decente (anche se non ottimizzata), proviamo ad utilizzarla per calcolare la lista (infinita) di tutti i primi. Come vi ho spiegato qualche tempo fa Haskell permette di definire liste infinite, ovvero liste che potenzialmente contengono un numero infinito di elementi. Haskell è lazy, e quindi non è che effettua un calcolo infinito: semplicemente, calcola gli elementi man mano che servono. Ecco la lista infinita di primi a partire dal 2:

primes :: [Integer]
primes = (filter isprime [2..])

Abbiamo usato la funzione filter che prende come argomenti una funzione (in questo caso isprime), e una lista (in questo caso la lista infinita degli interi maggiori o uguali a 2), e applica la funzione a tutti gli elementi della lista. Il risultato è una lista che contiene tutti e solo gli elementi per i quali isprime ha restituito True, ovvero la lista dei primi.

Ci siamo quasi. Adesso, per testare la primalità, ci basta controllare tutti la divisibilità per tutti i numeri primi fino alla readice quadrata di n. Ecco il codice:

isprime n = let sqn = floor $sqrt $fromIntegral n
            in not $ or [ x `divides` n | x <- takeWhile (<=sqn) primes ]

Spiegazione: la funzione takeWhile prende due paramteri, una funzione e una lista. La prima funzione è una sezione dell’operatore <= e ci restituisce True quando un numero è minore o uguale di sqn. Il secondo argomento è una lista, nel nostro caso la lista infinita primes. La funzione takeWhile applica la funzione a tutti gli elementi della lista finché la funzione restituisce True, poi si ferma. Il risultato è quindi tutta la prima parte della lista fino a che troviamo un numero pari a sqn.

Vi si sta attorcigliando il cervello? No problem, accade sempre con casi di ricorsione doppia incrociata con scappellamento a destra! Qui abbiamo che la funzione isprime ha bisogno della lista primes per essere calcolata, e quest’ultima si calcola a partire dalla funzione isprime. Proviamo a vedere se funziona:

module Main where
import System.Environment

main :: IO()
main = do args <- getArgs
          putStrLn ( show $ isprime (read $ args!!0) )

x `divides` n = n `mod` x == 0

isprime :: Integer -> Bool
isprime n = let sqn = floor $sqrt $fromIntegral n
            in not $ or [ x `divides` n | x <- takeWhile (<sqn) primes ] 

primes :: [Integer]
primes = (filter isprime [2..])

Salvate in un file chiamiato primi2.hs, compilate e eseguite. Ed ecco quello salta fuori:

lipari@lipari$ ./primi 11
primi: <<Loop>>

Ahi ahi. Che è successo? E’ successo che Haskell si è incasinato e non riesce a venire fuori da questa ricorsione doppia con lista infinita. In particolare, quando ha cercato di calcolare il primo elemento della lista primes, è andato in loop. Non avremmo esagerato? Beh, sì un po. Vediamo perché e magari salterà fuori che abbiamo capito qualcosa in più di come funziona il tutto.

  1. Per prima cosa, Haskell cerca di calcolare la fuzione isprime sul numero che gli abbiamo passato sulla linea di comando, che è 11. Per fare questo cerca di risolvere la list comprehension, e in particolare cerca di estrarre il primo elemento della lista primes per darlo in pasto alla takeWhile.
  2. Bisogna quindi calcolare il primo elemento (solo il primo!) della lista primes, che corrisponde al primo elemento della lista risultante dalla funzione filter
  3. Per fare questo, deve prima calcolare isprime 2.
  4. Torniamo su: per calcolare isprime 2 ha bisogno del primo elemento della primes…
  5. Haskell a questo punto si accorge di essere finito in un ciclo infinito, e alza le braccia, stampando l’errore sul terminale e uscendo dal programma.

L’errore qui è che lui non riesce a partire, non ha un punto di inizio. In matematica, si direbbe che abbiamo un’induzione senza una base; in informatica, abbiamo una ricorsione senza una condizione di terminazione. Notate che Haskell non vi pianta il calcolatore fino al fatidico out of memory. Si accorge del loop infinito, e esce subito.

La soluzione è più semplice di quanto possiate immaginare. Se Haskell non riesce a calcolarsi il primo elemento della lista primes, possiamo suggerirlo noi! La definizione di primes diventa:

primes = 2:(filter isprime [3..])

Il primo della lista lo mettiamo noi, gli altri glieli lasciamo calcolare. Adesso abbiamo la base induttiva.

Proviamo a rifare il ragionamento di prima. Dopo il punto 2, il punto 3 ci dice che il primo elemento di primes è 2, che è minore di sqn. Quindi, x prende il valore 2. 11 non è divisibile per 2, quindi il primo elemento della lista da dare in pasto alla funzione or è un bel False. A questo punto dobbiamo calcolare il secondo elemento di primes. Per far questo dobbiamo calcolare isprime 3. La radice di 3 è sqn=1.73…, quindi l’espressione takeWhile (<sqn) primes è una lista vuota. L’or di una lista vuota da come risultato False, e quindi isprime 3 è True. Quindi il secondo elemento di primes è 3, e possiamo tornare a calcolare isprimes di 11. 3 non divide 11, quindi adesso la lista di booleani contiene due False, e ci tocca andare a calcolare il terzo elemento di primes… che penso ci possiamo fermare qui.

A questo punto, dopo tutto questo sforzo mentale, provate a compilare e lanciare il programma!

Ultima piccola modifica. Nel calcolare la lista dei primi, noi sappiamo già che i pari non sono primi, e quindi potremmo applicare una piccola ottimizzazione:

primes = 2:(filter isprime [3,5..])

La lista [3,5,..] è un modo elegante e molto haskelliano di rappresentare i numeri dispari da 3 in su.

Conclusioni

Naturalmente, se proprio vogliamo calcolare la lista dei numeri primi, ci sono metodi parecchio più efficienti, come il crivello di Eratostene, ma questo magari lo vediamo la prossima volta che oggi penso di avervi incriccato la cervice abbastanza. E chissà, magari, forse, prima o poi diamo uno sguardo anche al crivello di Atkin (ah, gli studenti di oggi!)

Note

L’immagine è presa da questo blog.

Liste infinite

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.

Funzioni al cubo

Terza puntata: tipi e funzioni (in Haskell)

Sono in ritardissimo con la terza puntata della serie, lo so. Ma ogni tanto debbo pur lavorare, e poi c’è la famiglia che richiede attenzioni. E poi, … avevo lasciato il gas aperto, il terremoto, le cavallette!

Oggi ci concentriamo su Haskell. Vedremo perché Haskell è uno dei linguaggi funzionali per eccellenza. Parleremo di:

  • tipi di dati e tipi di funzioni;
  • la funzione map;
  • le funzioni lambda;
  • gli operatori.

Ma prima …

Errata corrige

Nella scorsa puntata avevo scritto che in Haskell per concatenare si usano i due punti (:). Beh, non è proprio così. I due punti in Haskell servono per “attaccare” un elemento in testa a una lista. Ad esempio, scrivere 1:[2,3] è equivalente a scrivere [1, 2, 3]. Invece, per concatenare due liste si usa l’operatore ++ come segue:

[1,2,3] ++ [4,5,6]

che ha come risultato la lista [1,2,3,4,5,6]

I due punti (:) possono essere visti come un operatore in notazione infissa che prende due argomenti: quello a sinistra deve essere un elemento, quello a destra una lista di elementi dello stesso tipo del primo argomento. E poiché gli operatori sono come delle funzioni, potremmo dire che (:) è una funzione che prende come primo argomento un tipo arbitrario (chiamiamolo a), come secondo argomento una lista di a (indichiamola con [a]), e restituisce una lista di a. In pseudocodice:

(:)  ::  a -> [a] -> [a] 

Non ci avete capito niente? Allora ripartiamo da capo più lentamente.

Tipi in Haskell

Haskell è un linguaggio tipato. Questo vuol dire che in Haskell i tipi di dato sono molto importanti, e il compilatore vi blocca se il tipo di argomento di una certa funzione non è quello
giusto. Ad esempio, consideriamo la seguente funzione:

inc :: Integer -> Integer
inc x = x+1  

Questa notazione significa che la funzione inc prende un argomento di tipo intero, e restituisce un argomento di tipo intero. Diciamo innanzitutto che Haskell richiede che gli identificatori di tipo inizino con la lettera maiuscola, quindi Integer, mentre tutto il resto (funzioni, argomenti,
variabili, ecc.) inizino con la lettera minuscola.

A proposito: Integer sono gli interi, tutti gli interi, senza alcun limite. Quindi la loro rappresentazione in memoria ha dimensioni variabili. Se volete gli
interi a 32 bit (quelli del C per intenderci), allora utilizzare Int. Naturalmente, i calcoli con Int sono più efficienti, ma rischiate l’overflow.

Dicevamo della funzione inc: come parametro vuole un Integer. Ad esempio, se scrivete:

inc 'a'
inc [1, 2]
inc "pippo" 
inc 7

il compilatore si lamenterà in tutti i primi tre casi, dicendo che si aspettava un intero e voi gli avete passato chissà che. L’ultimo caso invece è corretto.

Passare un argomento a una funzione, e calcolare così il risultato, viene detto applicazione, come nel linguaggio matematico, ed è un’operazione ben precisa come vedremo. Quindi, l’applicazione di 7 a inc si scrive inc 7.

Per indicare una lista di interi, si scrive [Integer]. Per questo motivo, la nostra funzione pari della scorsa puntata aveva questa type signature:

pari :: [Integer] -> [Integer]

cioè prendeva una lista di interi e ne restituiva un’altra che conteneva solo i numeri pari.

Funzioni di ordine superiore

E le funzioni di due argomenti? Per spiegare, prendiamo una funzione semplicissima (ed inutile!):

add :: Integer -> Integer -> Integer
add x y =  x + y  

La funzione add somma i suoi due argomenti. La type signature però è un po’ strana: ci saremmo aspettati qualcosa come:

add :: Integer, Integer -> Integer

Perché invece della virgola c’è una freccia? Calma e sangue freddo.

In Haskell, la freccia è un operatore che associa a destra: se mettiamo le parentesi, l’espressione di cui sopra si può scrivere anche così:

add :: Integer -> (Integer -> Integer)  

Ovvero: la funzione add prende in realtà un argomento, e restituisce una funzione da Integer a Integer!

E’ quindi perfettamente lecito fare una applicazione parziale di una funzione a più variabili per ottenerne un’altra con meno variabili. In matematica, questa operazione si chiama anche proiezione. Ad esempio, possiamo scrivere la funzione inc come:

inc = add 1  

In altre parole, inc è la proiezione di add sul primo argomento. Se volete potete vederla anche così: “tutte le funzioni Haskell prendono un solo argomento; per fare una funzione di più argomenti, faccio in modo che la mia funzione restituisca un’altra funzione”. Contorto, lo so, ma è la programmazione funzionale, baby.

In Haskell, e nella teoria dei linguaggi funzionali, quando prendo una funzione di più argomenti e gliene do in ingresso solo uno sto facendo un’operazione di currying. E sapete perché viene chiamata così? In onore di un certo matematico americano che si chiamava Haskell Curry. A quanto ne so, il buon Haskell è stato l’unico a dare il suo nome a un linguaggio e il suo cognome ad un altro, e a cui è stata intitolata persino un’operazione matematica! Di che esserne fieri, non c’è dubbio!

Ma non divaghiamo troppo: dicevamo che il currying consiste nel passare un solo argomento a una funzione, e ottenerne come risultato un’altra. Dopodiché possiamo prendere questa funzione risultato e farci quello che ci pare. Per esempio, passargli un secondo argomento per ottenere un risultato (se la funzione è di una variabile). Possiamo anche passarla come argomento ad un’altra funzione; oppure restituirla come risultato di una funzione!

Vediamo ora come viene interpretata l’applicazione di una funzione di due variabili come la add. L’applicazione a un argomento è un’operazione associativa a sinistra (al contrario dell’operatore
freccia). Quindi le due scritture:

add 1 2
(add 1) 2  

hanno lo stesso significato. In particolare, guardiamo la seconda. Inizialmente la funzione add si applica a un argomento di tipo Integer, e come risultato otteniamo una funzione da Integer a Integer. Quest’ultima si applica al secondo argomento, e otteniamo come risultato un Integer. Semplice! (O no?)

Le funzioni in Haskell sono oggetti come tutti gli altri. Non c’è alcuna distinzione concettuale tra un dato e una funzione: a entrambi possono essere applicate delle operazioni; entrambi possono essere argomento di funzioni, oppure essere il risultato di funzioni. Si dice che le funzioni di Haskell sono funzioni di ordine superiore, perché possono essere manipolate nelle maniera più varia, esattamente come succede ai dati. Al contrario, ad esempio, delle funzioni del linguaggio C che invece sono solo … funzioni e basta!

La funzione map

Facciamo subito un esempio di funzione che prende come argomento un’altra funzione. Si tratta della map, che prende due variabili: la prima deve essere una funzione f, la seconda deve essere una lista. Il risultato della map è una lista ottenuta applicando la funzione f a tutti gli elementi della lista. Ad esempio:

map inc [1, 2, 3]  

da come risultato la lista [2, 3, 4]. La map naturalmente può prendere una funzione qualsiasi, ad esempio una funzione di più argomenti: in questo caso il risultato sarà una lista
di … funzioni! Ad esempio

map add [1, 2, 3]  

dà come risultato una lista di funzioni, la prima delle quali corrisponde a inc! Altro esempio:

map pari [ [1,2,3], [4, 5, 6], [7, 8, 9] ]

il cui risultato è [ [2], [4, 6], [8] ].

Tipi polimorfici

Se dovessimo scrivere la type signature di map, quale sarebbe? Cominciamo prima con la type signature di una funzione più semplice per capire come funziona. Prendiamo in considerazione la funzione head che prende una lista e restituisce la testa. Ad esempio, head [1,2,3] dà come risultato 1. Però, la head funziona su liste di qualunque tipo, non solo sugli interi. Ad esempio, head ['a', 'b', 'c'] restituisce come risultato ‘a’. E allora qual’è la type signature di head ? Eccola:

head :: [a] -> a

Si legge così: la funzione head prende come primo argomento una lista di un qualsiasi tipo a, e restituisce un risultato di tipo a (cioè dello stesso tipo contenuto nella lista).

Si dice che head è una funzione polimorfica, perché funziona su un insieme di tipi definiti dalla precedente regola. Il simbolo a si chiama type
parameter
perché sta lì ad indicare un tipo qualsiasi, un tipo che ancora non conosciamo al momento della definizione della funzione.

Il compilatore Haskell sta bene attento che tutti i tipi siano consistenti, naturalmente. Quindi se scrivo
inc (head [1, 2, 3]) va tutto bene, mentre se scrivo inc (head ['a', 'b', 'c']) il compilatore mi dà errore dicendo che la inc si aspetta un intero e invece io gli sto dando un
carattere. Quindi il compilatore fa un vero e proprio calcolo sui tipi da usare, e questo calcolo si chiama type inference.

Adesso siamo pronti per scrivere la type signature di map. Eccola:

map :: (a->b) -> [a] -> [b]  

che si legge: la funzione map prende due argomenti; il primo dei quali è una funzione che va da un generico tipo a a un generico tipo b; il secondo è una lista di a; il
risultato è una lista di b.

Abbiamo dovuto mettere le parentesi sul primo argomento perché (ricordate?) l’operatore freccia associa a destra: se avessimo scritto map :: a -> b -> [a] -> [b], la funzione map
sarebbe stata di 3 argomenti!!

Le funzioni lambda

(No, non c’è bisogno di tatuarsi il braccio per imparare a programmare in Haskell, non vi preoccupate)
(ah, il proprietario del tautaggio sembrerebbe essere questo tipo qui…)

Figuriamoci se in Haskell (forse il linguaggio più funzionale in assoluto) potevano mancare le funzioni lambda.

Le funzioni lambda nascono da una semplice osservazione (fatta da Alonzo Church, che ha inventato il lambda calculus): per definire una funzione non serve dargli un nome. Il nome di una funzione, infatti, è un modo per aiutare noi esseri umani a ricordarci di cosa faccia la funzione, e per comunicare con altri esseri umani, cosicché quando diciamo “funzione coseno” sappiamo tutti di cosa stiamo parlando. Ma dal punto di vista strettamente matematico, il nome è un di più, è “zucchero per la mente”, ma non aggiunge né toglie alcunché al significato della funzione. Per esempio, la
funzione coseno potrebbe anche essere chiamata cosine, oppure cos, oppure pippo, ma rimarrebbe sempre la stessa funzione.

Cos’è allora che identifica univocamente la funzione? Innanzitutto la sua type signature; e poi la corrispondenza tra valori del dominio a valori del codominio. In pratica, una funzione è la sua definizione.

Il buon Alonzo pensò che per definire un’algebra delle funzioni non servisse affatto dargli un nome; per cui, tutte le funzioni potrebbero benissimo chiamarsi (ad esempio) lambda.

Vediamo ora di utilizzare la map con una funzione lambda:

map (\x -> x+1) [1, 2, 3]  

Abbiamo cioè definito la funzione inc in linea come funzione lambda, e l’abbiamo passata alla map. Le funzioni lambda devono cominciare con un backslash: quindi segue la lista dei
parametri; quindi l’operatore freccia; quindi la definizione della funzione. Ad esempio, la funzione add si definisce come \x y -> x+y, e il risultato di

map (\x y-> x+y) [1, 2, 3]    

è la lista [\y -> 1+y, \y -> 2+y, \y -> 3+y].

Operatori

Gli operatori non sono altro che funzioni di due argomenti che però usano la notazione infissa: ovvero l’operatore si mette tra i due argomenti, mentre una funzione si mette prima dei suoi argomenti. E finalmente possiamo tornare all’inizio del post: se mi avete seguito fin qui dovreste aver chiarito la type signature dell’operatore :,

(:) :: a -> [a] -> [a] 

Capito? (speriamo).

Altri operatori:

(++) :: [a] -> [a] -> [a]      -- concatenazione di liste
[]     ++ ys  =  ys
(x:xs) ++ ys  = x : (xs ++ ys)

Spieghiamo: la concatenazione di liste è un operatore che prende due argomenti di tipo lista e restituisce una lista con elementi dello stesso tipo; la concatenazione fra una lista vuota e una lista ys corrisponde a ys; la concatenazione fra due liste, di cui la prima è formata da una testa pari a x, e una coda xs, è pari a una lista la cui testa è x e la
cui coda è la concatenazione tra xs e ys.

Vediamo un altro operatore:

(.)  :: (b->c) -> (a->b) -> (a->c)  -- composizione di funzioni
f . g  = \ x -> f (g x)

Questo serve a comporre due funzioni: esso prende in ingresso due funzioni (b->c) e (a->b) e dà in uscita una funzione (a->c); essa viene definita come una funzione lambda che prende in ingresso un argomento x (di tipo a) e da in uscita l’applicazione di f al risultato di g x.

Se applichiamo solo un argomento a un operatore, otteniamo una sezione, che sarebbe come il currying, ma per operatori. Quindi la inc si può scrivere come:

inc = (+1)  

E quindi, la solita espressione con map si può scrivere anche:

map (+1) [1, 2, 3]  

Un’altra espressione di esempio:

map (^2) [1, 2, 3]  

dà come risultato la lista dei quadrati degli elementi della lista, perché ^ è l’operatore di elevazione a potenza.

Sommario

Lo so, a questo punto molti di voi si sono persi completamente. In effetti oggi non ho riportato neanche un programmino di esempio. Però, per capire Haskell bisogna obbligatoriamente prima capire cosa ci sta
sotto, e il perché di una notazione così particolare. E io meglio di così non lo so spiegare!

Il contenuto di questo post è stato liberamente ispirato da “A gentle introduction to Haskell 98” (che però non è così “gentle” come sostiene nel titolo). Se volete approfondire cominciate a dargli un’occhiata! Se no, continuate a seguire questa serie, che prima o poi mostrerò dei programmini utili (insomma, quasi utili).

La spiegazione del “perché esiste il lambda calculus” è stata liberamente ispirata dalla corrispondente pagina su Wikipedia.

Direi che per oggi vi ho stressato abbastanza. Prima di terminare però, provate a svolgere due semplici esercizi per vedere se avete capito:

  1. Scrivere la definizione della funzione map. Naturalmente, sarà una funzione ricorsiva!
  2. 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]
  3. .

Le soluzioni alla prossima!

Funzioni e liste

(Puntata precedente)

(Questo post è stato scritto a quattro mani, dalla premiata ditta glipari & juhan)

Prima di proseguire con la panoramica sulla programmazione funzionale, è bene mettere in chiaro due cose. Primo, la programmazione funzionale può essere considerata un approccio alla programmazione indipendente dal linguaggio utilizzato, anche se alcuni linguaggi permettono di esprimere direttamente e in maniera più efficace i tipici costrutti funzionali.

Secondo, osserviamo che la programmazione funzionale sta diventando di moda perché utile per la risoluzione di molti problemi in maniera pratica ed elegante. Per questo motivo, molti linguaggi di programmazione imperativi forniscono anche delle caratteristiche tipiche della programmazione funzionale. Un esempio è il Python, ed infatti in questo post utilizzeremo primariamente questo linguaggio per i nostri esempi.

Oggi ci soffermiamo sulla lista, un tipo di dato fondamentale per tale tipo di programmazione. Lo faremo inizialmente utilizzando il Python, facendo poi i paragoni con altri linguaggi funzionali.

Non vogliamo mica riscrivere il manuale di Python, naturalmente. Ci limiteremo a enunciare le cose fondamentali, rimandando a siti, libri, corsi per i necessari approfondimenti.

Liste

Chi volesse sapere tutto delle liste in Python, sarà meglio dia un’occhiata qui. Una lista è una sequenza finita di dati non necessariamente dello stesso tipo. Ad esempio, una lista di interi, una lista di caratteri, una lista di stringhe, etc. Le liste si definiscono utilizzando le parentesi quadre, dentro cui si mettono gli elementi separati da virgole. Ecco la lista dei primi 10 numeri primi.

ten_primes = [1, 2, 3, 5, 7, 11, 13, 17, 19, 23]

Le liste sono dinamiche: si possono allungare inserendo elementi in coda o ad una certa posizione, oppure scorciare, cancellando elementi. Si possono poi generare con la funzione range(), oppure utilizzando i due punti. Ecco degli esempi:

ten_primes.extend([29, 31, 37]) # aggiunge altri 3 primi in coda
ten_primes.append(41)           # ne aggiunge un'altro in coda
N_items = len(ten_primes)       # restituisce 14 il numero di elementi della lista
tqq = ten_primes[2:5]           # crea una seconda lista contenente soltanto
                                # 3o, 4o e 5o elemento
print ten_primes[:10]           # stampa i primi 10
print tqq[0]                    # stampa il primo elemento di tqq

Naturalmente, si possono fare un sacco di cose strane, tipo definire liste contenenti altre liste.

In Python, le liste possono contenere un po’ di tutto, anche elementi di tipo diverso. In altri linguaggi che hanno un forte controllo sui tipi (come Haskell), invece, le liste devono contenere elementi tutti dello stesso tipo.

Le liste sono uno degli strumenti di base di ogni programmatore funzionale. Una delle caratteristiche delle liste è che le funzioni ricorsive sulle liste si scrivono benissimo. Infatti, una lista può essere definita ricorsivamente come:

  • La lista vuota []; oppure
  • Il primo elemento (chiamato testa della lista) seguito da una lista contenente il resto degli elementi (chiamato coda)

Ad esempio: la lista [1,2,3] può essere vista come:

  • l’elemento 1 seguito dalla lista [2,3], la quale a sua volta è definita come:
  • l’elemento 2, seguito dalla lista [3], la quale a sua volta è definita come:
  • l’elemento 3, seguita dalla lista [], la quale è definita come lista vuota

Complicato? Beh, inizialmente sì, e molto, ma poi uno si abitua a questi contorcimenti mentali, e scrivere algoritmi ricorsivi diventa il suo pane quotidiano.

Vediamo un po’ di scriverne subito uno. Data una lista, vogliamo ottenere una seconda lista contenente solo i numeri pari presenti nella prima. In Python, la testa di una lista l si ottiene con l[0], mentre la coda si ottiene con l[1:]. Ecco un algoritmo ricorsivo:

#!/usr/bin/python
# -*- coding: utf-8 -*-

def pari(l) :
    if l == [] :           # la lista è vuota
        return []          # fine della ricorsione
    elif (l[0] % 2) == 0 : # se la testa è pari ...
        ll = [ l[0] ]      # ... mettila nella nuova lista ...
        ll.extend(pari(l[1:])) # ... e applica la stessa funzione alla coda
        return ll          
    else :                 # se la testa è dispari
        return pari(l[1:]) # scartala, e applica la stessa funzione alla coda

print pari(range(1,10))

Avete bisogno che spieghi nel dettaglio? Penso sia abbastanza chiara: se la testa della lista è un numero pari, il risultato sarà una lista contenente la stessa testa, e il risultato della funzione pari applicato alla coda. Se è dispari, è semplicemente il risultato della funzione pari applicato alla coda. Il risultato stampato a schermo è la lista [2, 4, 6, 8]. Lo so che si poteva fare più semplicemente con un ciclo for, ma i cicli sono fortemente sconsigliati nella programmazione funzionale, ricordate?

Inoltre, notate che non ci sono vere e proprie variabili locali, a parte la lista ll che ho usato solo per chiarezza, ma che può essere completamente eliminata riscrivendo la funzione come segue:

def pari(l) :
    if l == [] :           
        return []          
    elif (l[0] % 2) == 0 : 
        return [l[0]] + pari(l[1:])
    else :                 
        return pari(l[1:]) 

La riga 5 significa “concatena la testa con la lista ottenuta chiamando la funzione pari sulla coda”.

Per gli esperti e per i curiosi: questa versione è un po’ meno efficiente della versione precedente, sappiatelo!

In realtà, ci sono modi più eleganti di scrivere la stessa cosa. Per esempio, in Python si può usare una funzione chiamata filter, che serve appunto per ottenere una lista sottoinsieme, i cui elementi sono selezionati in base a una funzione booleana. Ecco l’esempio:

def isEven(i) : return i % 2 == 0

l = range(1,10)
print filter(isEven, l)

La funzione isEven ritorna True se un numero è pari. La funzione filter applica la funzione isEven a tutti gli elementi della lista l, e tutti quegli elementi per cui isEven è True vengono inseriti nella lista risultato. Quindi, l’output del programmino di cui sopra è ancora [2, 4, 6, 8]. Ma si può fare ancora di meglio! Si può eliminare del tutto la funzione isEven, trasformandola in una lambda function, così:

print filter(lambda i : i%2== 0, range(1,10))

Ma che cos’è una lambda function? Juhan ne aveva già parlato qui. Praticamente è una funzione inlined nel codice. Si elimina il nome (inutile, perché la funzione non verrà utilizzata da nessun’altra parte), e si sostituisce con il generico lambda; si elimina il return e resta solo la lista dei parametri (qui il solo i) e l’espressione. Va bene usarla per robetta semplice, come appunto una funzione con il solo return. In pratica, l’espressione lambda x : expr, è equivalente a scrivere una funzione

def fun x : return expr

e a passarla alla filter.

(Uff, lungo questo post!)
Ma aspettate! Dobbiamo ancora fare un passettino: la list comprehension. Lo stesso esempio si può scrivere così:

print [x for x in range(1,10) if x%2==0]

Che si legge: “stampa l’insieme degli x tali che x appartiene a range(1,10), e solo se x è pari”. Assomiglia un po’ alla notazione matematica per definire un insieme con certe caratteristiche, che nel nostro esempio sarebbe:

\{x | x \in [1, 10) \wedge x \; \mbox{mod} \; 2 = 0 \}

In effetti l’idea è proprio quella: avvicinarsi il più possibile alla notazione matematica.
Sulle liste ci torneremo presto con altre interessanti operazioni, map e reduce su tutte. E poi per fare qualche esempio un tantinello più complicato.

Le liste in NewLISP

E se questo è quello che trovate in Python, provate a immaginare cosa potreste trovare in un linguaggio funzionale! Cominciamo dal NewLISP.

Una lista in NewLISP è una sequenza di elementi tra parentesi tonde. In LISP (e NewLISP di conseguenza) si usano quasi soltanto parentesi tonde, tanto è vero che uno dei classici jokes dice che LISP starebbe per Lista di Inutili Stupide Parentesi! Ma voi non credetegli, non sono poi così stupide!

xckd sul lisp

NewLISP è leggermente diverso dal LISP classico, di cui tra l’altro ne esistono tantissimi altri dialetti. La testa di una lista in newLISP si ottiene con la funzione first (ma dimmi te!), mentre nel LISP serio con car. Il resto della lista si ottiene in newLISP con rest, mentre nel LISP serio con cdr. Adesso vediamo l’esempio precedente in newLISP utilizzando la funzione predefinita filter:

;; definisco even?, torna true per pari, nil per dispari 
(define (even? n) 
    (= (% n 2) 0)
)

;; la lista
(set 'L (sequence 1 9))

;; e filtro
(set 'P (filter even? L))

(println P)
(exit)

Spieghiamo. In NewLISP, le funzioni si definiscono con define (il nome della funzione può contenere il punto interrogativo che non è un carattere speciale). Il nome della funzione è seguito dal nome del parametro n.

Per inciso: notate la notazione prefissa per gli operatori: prima l’operatore, poi gli argomenti. Questo perché gli operatori non sono altro che funzioni che prendono due argomenti! Ad esempio, se dobbiamo fare due più due, in NewLISP scriveremo: + 2 2 (cioè applica la funzione somma agli argomenti 2 2).

Nei linguaggi funzionali è abbastanza comune evitare di usare le parentesi per “calcolare” il valore di una funzione. Ad esempio, se vogliamo calcolare il valore di fun nel punto 5, in un linguaggio imperativo scriveremo fun(5), mentre in un linguaggio funzionale scriveremo semplicemente fun 5. Quindi, si scrive + 2 2, piuttosto che +(2,2).

Tornando al nostro esempio, alla riga 3 l’operatore di confronto = prende due argomenti, il primo dei quali è il risultato dell’applicazione dell’operatore % ai parametri n e 2. Le parentesi servono a raggruppare gli argomenti, in modo che l’interprete NewLISP non si confonda. Torna? E’ tutta questione di abitudine, vedrete.

Poi definisco la lista L. L’operatore set assegna al suo primo argomento L il risultato dell’applicazione della funzione sequence ai parametri 1 e 9. Spero sia chiaro anche questo! Naturalmente, anche NewLISP, che ha a che fare con un sacco di liste, ha la funzione filter, che prende ancora una funzione e una lista. Alla fine, stampiamo a video il contenuto della lista P.

Aspettate, ma non ci saranno mica le funzioni lambda anche in NewLISP? Ma ceeeeerrrrrrrto che si! Ecco una versione con la lambda e con la definizione della lista in linea:

(set 'P (filter (lambda (n) (= (% n 2) 0)) (sequence 1 9)))

(println P)
(exit)

La definizione di lambda è molto simile a quella del Python: lambda seguito da una lista di argomenti, seguito dall’espressione booleana ottenuta applicando l’operatore = etc.
Provate ad eseguire il programma per rendervi conto di come funziona!

Se mi avete seguito fino a qui, siete pronti al salto finale: la stessa cosa in Haskell!
(Argh!!!)

Liste in Haskell

Le liste in Haskell hanno una notazione molto simile a quella di Python. C’è una restrizione: le liste devo contenere elementi tutti dello stesso tipo (o ereditate dallo stesso tipo, come si vedrà più avanti parlando delle gerarchie di tipi). Vediamo alcuni esempi:

[1, 2, 3, 5, 7, 11]  -- alcuni numeri primi
[1..9]               -- tutti i numeri interi da 1 a 9, compresi
l1 : l2              -- l3 è la concatenazione di l1 e l2
head l1              -- la testa di l1
tail l2              -- la coda di l2
(x:xs)               -- x è la testa di una lista, xs è la coda 

I commenti in Haskell cominciano con il doppio meno, –: l’equivalente di range sono i due puntini all’interno della lista (riga 2); per concatenare si usano i due punti (riga 3); le funzioni head e tail restituiscono rispettivamente la testa e la coda di una lista; le quali si possono ottenere anche con la notazione alla riga 5. Quest’ultima notazione sarà subito utilizzata nel programma per ottenere i pari, prima versione, quella ricorsiva:

module Main where
import System.Environment

main :: IO()
main = do args <- getArgs
          putStrLn(show( pari( [1..9])) )

pari :: [Integer] -> [Integer]
pari [] = []
pari (x:xs) = if even x then x : pari xs else pari xs

La prima parte è “difficile” e non siamo ancora pronti a comprenderla a fondo: l’unica cosa da dire è che stampiamo sul terminale con la putStrLn una stringa ottenuta chiamando la funzione show che appunto trasforma il suo argomento in una stringa, e il suo argomento è il risultato della chiamata alla funzione pari sulla lista degli interi da 1 a 9 inclusi.

La funzione pari è dichiarata come una funzione che prende una lista di interi e restituisce un’altra lista di interi. La funzione pari sulla lista vuota ritorna la lista vuota. La funzione pari su una lista con una testa (denominata x) e una coda (denominata xs) ha due casi: se x è pari (chiamamiano la funzione even passandogli x, e questa ci restituisce True se x è pari) allora il risultato è la concatenazione di x con il risultato della funzione pari applicata alla coda: se no è semplicemente il risultato della funzione pari sulla coda.

Finito? Aspetta, si può scrivere anche così:

                                    
pari :: [Integer] -> [Integer]
pari l = [ x | x <- l, even x ]

Stavolta abbiamo usato la list comprehension, che naturalmente è ben presente anche in Haskell! Sembra proprio la notazione matematica: il risultato di pari è una lista di elementi x tali che x appartiene a l, e x è pari.

In Haskell le varie definizioni di funzione vengono chiamate equazioni: nel primo caso abbiamo scritto due equazioni per definire la funzione pari; nel secondo caso ci è stata sufficiente una sola equazione. Sul perché si chiamino equazioni, spero di darvi una risposta più esauriente nei prossimi post! Per ora notate che chi ha inventato il linguaggio ha fatto di tutto per farle sembrare delle equazioni.

Conclusioni

Tiriamo le conclusioni per questo post. Le liste sono un importantissimo strumento per i linguaggi funzionali, perché permettono di scrivere le funzioni ricorsive in maniera semplice e diretta. Tutti i linguaggi funzionali (e non) permettono di manipolare le liste nei modi più vari. Oggi abbiamo visto la funzione filter e le lambda functions in Python e NewLISP; e le list comprehension in Python e Haskell (naturalmente ci sono le lambda function anche in Haskell, anche se non le abbiamo ancora viste). Cosa ci aspetta prossimamente?

  • map e reduce;
  • le liste infinite in Haskell;
  • funzioni pure e costo della ricorsione e del parallelismo nei linguaggi funzionali;
  • qualche programmino leggermente più complicato.

(Continua…)

PS: il plug-in di wordpress per mostrare il codice supporta Python, ma non supporta NewLISP né Haskell. Quindi niente code highlighting per gli ultimi due, ci dispiace!

Linguaggi imperativi e linguaggi funzionali

Questo post nasce dall’esigenza di spiegare, a chi non è un esperto del mestiere, che cosa sia un linguaggio di programmazione funzionale, e perché risulti così ostico alla maggior parte dei programmatori. In questo blog si è già cominciato da tempo a vedere qualche linguaggio funzionale: prima Lisp, adesso OClam, grazie al grandissimo socio! Però questi linguaggi funzionali rimangono un po’ misteriosi, e quindi diamoci una sguardo generale.

In particolare, mi rivolgo ad alcuni matematici e fisici che ci seguono di tanto in tanto: secondo me potrebbero apprezzare molto un linguaggio di programmazione funzionale, una volta capita l’idea che ci sta dietro. In effetti si dice spesso che i linguaggi di programmazione funzionale siano i più graditi ai matematici: vediamo se riesco a spiegare perché.

Categorie

Se seguite questo blog dall’inizio, avrete capito che esistono più linguaggi di programmazione di quanti ne possiate immaginare. Alcuni sono delle meteore, prodotti della ricerca e poco più. Altri hanno avuto un modesto successo in alcune nicchie applicative. Alcuni sono diventati diffusissimi e usatissimi, nonostante i loro difetti. Altri sono rimasti dominio di pochi nerd, nonostante i loro pregi. E naturalmente nessuno sa perché, ad esempio, un linguaggio come Java abbia avuto tutto quell’enorme successo.

Come orientarsi tra questa selva di linguaggi di programmazione? Naturalmente, si fanno le tassonomie, ovvero si cercano di classificare i linguaggi di programmazione rispetto alle loro caratteristiche. Una delle prime categorizzazioni è la distinzione tra linguaggi imperativi e linguaggi funzionali

Linguaggi imperativi (o procedurali)

I primi sono di gran lunga i più diffusi, contando fra i loro membri la maggior parte dei linguaggi cosidetti Object Oriented. Stiamo parlando di stelle del firmamento come C++, Java, Python, Objective C, etc. Ma anche i vecchi linguaggi come C, Fortran, Cobol, Pascal.

In un linguaggio procedurale l’enfasi è sui dati (variabili, strutture dati, oggetti) e sui modi per processarli (tramite procedure, funzioni, metodi). In pratica, in un linguaggio procedurale si parte da un insieme di dati, e si applicano una serie di “operazioni” da eseguire in sequenza che li elaborano per produrre il risultato finale. Le operazioni da eseguire vengono descritte come una serie di istruzioni, comandi, ordini che il processore deve eseguire in sequenza per ottenere il risultato.

Oggi il modo di pensare del 90% dei programmatori è fortemente orientato alla programmazione procedurale. Uno pensa un algoritmo come una sequenza di passi più o meno elementari, ognuno dei quali modifica i dati finché non si arriva al risultato finale.

Linguaggi funzionali

I linguaggi funzionali, invece, pongono tutta l’enfasi sulle funzioni. Non che non ci siano i dati: però le funzioni sono in qualche modo più importanti. Per esempio, in un linguaggio funzionale una funzione può essere argomento di un’altra funzione, oppure il suo valore di ritorno; data una funzione di due variabili, è possibile fare una proiezione su una delle due variabili (assegnandogli una valore) ottenendo una funzione di una variabile.

Inoltre, di solito nei linguaggi funzionali le funzioni sono pure. Ovvero, non hanno effetti nascosti. Il risultato di una funzione per certi valori degli argomenti sarà sempre lo stesso, indipendentemente da quando la funzione viene valutata (cioè in quale ordine nella sequenza di operazioni da effettuare).

Prima di continuare è bene fare degli esempietti molto semplici per capire di cosa stiamo parlando. Scriveremo gli esempi in Python (come esempio di linguaggio imperativo); e in Haskell (come esempio di linguaggio funzionale). Avvertenza per gli esperti: ovviamente Python ha delle caratteristiche “funzionali”, e “Haskell” qualche aspetto “imperativo”. Ma per fare gli esempi useremo Python sempre in modalità “imperativa”, e “Haskell” per lo più in modalità “funzionale”.

Esempio 1: Fattoriale

La funzione fattoriale in matematica è una funzione definita sui numeri naturali (interi positivi) ed è semplicemente data dal prodotto di tutti i numeri naturali fino all’argomento n. In altre parole: fatt(n) = 1 \cdot 2 \cdot \ldots (n-1) \cdot n. Se vogliamo scrivere un semplice programmino Python che calcola il fattoriale potremmo fare come nel listato seguente:

def fatt(n) :
    prod = 1
    if n > 1 :
        for i in range(2,n+1) :
            prod = prod * i
    return prod

def main :
    risultato = fatt(5)
    print risultato

Nella funzione fatt, se l’argomento è minore o uguale a 1, il risultato viene 1. Se invece l’argomento è maggiore di 1, allora facciamo un ciclo for (linee 4-5) in cui moltiplichiamo ripetutamente il risultato per il valore della variabile i che viene incementata da 2 a n.

In pratica, diciamo operativamente come calcolare il fattoriale, dando una serie di comandi (adesso metti prod a 1; quindi moltiplica prod per 2, poi per 3, … e infine per n; quindi ritorna il risultato in prod).

Nei linguaggi funzionali, invece, non esistono i cicli. Se proprio dovete ripetere delle operazioni, potete usare la ricorsione. Per esempio, la funzione fattoriale in Haskell è la seguente.

module Main where
import System.Environment

main :: IO()
main = do args <- getArgs
          putStrLn("Factorial of " ++ 
                   (args !! 0) ++ 
                   " = " ++ 
                   show( fatt(read(args !! 0))) )

fatt :: Integer -> Integer
fatt 1 = 1
fatt n = n * fatt(n-1)

Saltate per il momento tutta la prima parte, e concentratevi sulla funzione fatt che comincia alla linea 11. Innanzitutto, definiamo fatt come una funzione che va dal dominio degli interi al codominio degli interi. In notazione matematica si scriverebbe: fatt : \mathcal{Z} \rightarrow \mathcal{Z}. Più o meno ci siamo.

Poi diciamo che fatt(1) fa 1. Il simbolo di uguaglianza qui significa “definito come”: si definisce che la funzione fatt, quando ha come ingresso il valore 1, ci da come risultato il valore 1. Nei linguaggi imperativi in cui la sintassi derivi dal linguaggio C, il simbolo di uguale significa “assegnamento”, ovvero un’operazione che assegna il valore dell’espressione a destra dell’uguale alla variabile a sinistra. Ma nei linguaggi funzionali non c’è alcun assegnamento: il simbolo di uguale recupera il suo significato matematico originale.

Infine, alla linea 13 diamo la definizione della funzione fatt nel caso generale: e diciamo che la funzione fatt per un qualunque intero n è definita come il prodotto di n per il valore della funzione fatt in (n-1).

L’ordine delle definizioni è importante in Haskell: la prima definizione alla linea 12 ha precedenza sulla definizione alla linea 13: quindi, per n=1 si preferisce la definzione alla linea 12, mentre nel caso generale si usa la definizione alle linea 13.

Per compilare il programma, salvatelo sul file fatt.hs. Poi usate il compilatore ghc così: ghc fatt.hs. Questo produrrà un file eseguibile fatt, che lancerete così:

$ ./fatt 5

che calcolerà il fattoriale di 5. Il significato delle linee di codice 1-10 è un bel po’ complicato, e magari lo vedremo un’altra volta. Fidatevi che fa quello che uno si aspetta.

Conclusioni parziali

Naturalmente, anche in Python si può usare la ricorsione, come con tutti i linguaggi imperativi. In effetti, l’esempio che vi ho portato oggi è molto ma molto semplice. Però, spero che abbiate cominciato a capire una piccolissima differenza: mentre con Python potete fare la ricorsione, oppure programmare in maniera imperativa, oppure mischiare entrambe le cose, Haskell vi forza a programmare con la ricorsione, e vi impedisce di fatto di utilizzare comandi imperativi. Non potete definire variabili locali temporanee nelle funzioni; non potete modificare variabili globali (che in realtà non esistono). Semplicemente dovete sforzarvi di ridurre tutti a delle funzioni. E non è affatto semplice!

(Continua…)

Iscriviti

Ricevi al tuo indirizzo email tutti i nuovi post del sito.

Unisciti agli altri 63 follower