Category Archives: Funzionali

Un esercizio in Python

A me piace molto il C++, ci lavoro e lo insegno. Ma riconosco che sia un linguaggio “un po’ complicato” (eufemismo). Per tante cose di tutti giorni, serve qualcosa di più semplice. Come sapete, recentemente mi sto appassionando al Python: e siccome la maniera migliore per fissare quello che uno impara è di metterlo per iscritto e provare a spiegarlo agli altri, oggi si parla di Python. Vi presento un piccolo esercizio in Python in cui svilupperemo le nostre abilità con la programmazione funzionale.

Supponiamo di avere un file pieno di numeri interi separati da virgole. Il file è però un pochino disordinato: su una linea ci possono essere un numero variabile di numeri, e tra un numero e l’altro e tra le virgole ci possono essere un numero variabile di spazi. Obiettivo: leggere tutti i numeri e metterli in una lista. Facile facile.

Esempio di file in input:

12 , 25, 
34, -15,    17  , 
100, 24

, 37, 99

Comciamo con il leggere tutto il file:

file = open('dati.txt', 'r')
lines = file.readlines()
all = ""
for x in lines :
    all = all + x

lines è una lista di stringhe, una per ogni linea, e con il ciclo le mettiamo tutte insieme.
Poi le splittiamo e infine le trasformiamo in interi:

nums = all.split(',')
intnum = []
for x in nums : 
    intnum.append(int(x))
print intnum

Insomma, facile. Ma tutti quei cicli for… non si può fare in maniera più compatta? Ovviamente si!
Ecco come. Innanzitutto, eliminiamo il primo ciclo for utilizzando la funzione read() che legge tutto in una stringa.

file = open('dati.txt', 'r')
all = file.read()

La stringa all adesso contiene tutto il file in una sola stringa. Adesso proviamo a fare lo split e a transformare tutto in numeri in un colpo solo:

intnum = map(int, all.split(','))
print intnum

La funzione map() applica la funzione passata come primo argomento, ovvero int(), a tutti gli elementi della lista passata come secondo argomento, ovvero al risultato di all.split(‘,’), e produce dunque una lista di interi.

A questo punto potremmo anche far tutto in una sola linea:

print map(int, open('dati.txt','r').read().split(','))

Alternativamente, invece della map() potete usare la list comprehension:

print [int(x) for x in open('dati.txt','r').read().split(',')]

Voilà, tutto in una linea!

Esercizio per casa: supponete di avere un file di configurazione con delle “proprietà”, ogni proprietà può avere assegnato un valore numerico. Ad esempio:

pippo = 15,
pluto = 25, paperino = 104, 
paperone = 75, qui, quo, qua

Nel file qui quo e qua non hanno alcun valore assegnato, quindi supponiamo che il vaolre di default per loro sia 0.
L’esercizio consiste nel leggere il file e produrre un dizionario {key,value}. L’output del programma sul file precedente dovrebbe essere:

{'pippo': 15, 'paperino': 104, 'pluto': 25, 'qua': 0, 'paperone': 75, 'qui': 0, 'quo': 0}

Cercate di farlo con il codice più breve e compatto possibile!

Buon divertimento! (poi posterò la mia soluzione, e non è affatto detto che la mia sarà la più “compatta”)

PS: nella prima versione di questo post, leggevo il file con readlines() solo per fare una join() successiva. In realtà basta fare read() per leggere l’intero file, e quindi ho editato la seconda parte del post.

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!

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 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 in Python

Avevo detto che mi sarei buttato sullo storico, ma mi sta prenendo più tempo del previsto, e allora ecco un post breve su Python (con la collaborazione di Juhan)

Puntate precedenti:

La domanda di oggi è: si possono fare le liste infinite in Python come in Haskell? La risposta è ni. Il Python non ha alcun meccanismo sintattico per definire una lista infinita, ed inoltre è tutt’altro che “pigro”: non appena definite qualcosa, Python cerca di calcolarla. Quindi, la risposta diretta sarebbe NO. Però. Però esiste un meccanismo in Python che è quello dei generatori, e come vedremo ci permette di calcolcare delle liste “potenzialmente infinite”.

Il meccanismo ha direttamente a che vedere con il ciclo for. Per esempio, se volete fare un ciclo in cui la variabile i assume tutti i valori tra 1 e 10 at ogni iterazione, dovete scrivere qualcosa come:

for i in range(1,10) :
    print i,

In pratica, questo stampa a video tutti i numeri tra 1 e 9.

C’è una cosa che i non pythonisti madrelingua non impareranno tanto facilmente e alcuni mai: il ciclo for i in range (1,10): sarà eseguito per i valori 1, 2, 3, 4, 5, 6, 7, 8, e 9. Cioè fino al limite superiore ESCLUSO.

Questo nella visione di Guido aveva un senso: se il range fosse normale (cioè partisse da zero) il limite superiore rappresenterebbe il numero di componenti. Questa è la spiegazione ufficiale. Quella meno ufficiale è che il BDFL continuasse a sbagliare indici negli arrays in C. Ma è un’accusa falsa e tendenziosa — anche se Python è unico per questo comportamento.

Ma vediamo più in dettaglio come funziona:

  • Prima la funzione range(1,10) genera una lista contenente tutti i numeri da 1 a 9
  • Una lista in Python è un caso particolare di un contenitore, e un contenitore può essere visitato usando un iteratore (per chi non sapesse che cosa è un iteratore, è come un puntatore, un indice, un segnaposto, che inizialmente viene posizionato alla testa della lista, e che si può di volta in volta spostare avanti di un passo)
  • Alla prima iterazione viene inizializzato un iteratore che punta alla testa della lista,
  • il valore puntato dall’iteratore viene messo nella variabile i
  • si esegue il codice nel corpo del for
  • alla fine dell’iterazione, l’iteratore viene incrementato per puntare all’elemento successivo della lista; se non ci sono più elementi, il ciclo termina; altrimenti si assegna a i il valore puntato e si torna al passo precedente.

Uh, quante cose! Complicato? Mica tanto, alla fine sembra complicato perché abbiamo spiegato le cose per filo e per segno, ma il comportamento finale è molto intuitivo, vero?

Comunque, la cosa fondamentale da notare qui è che prima viene creata tutta la lista con range(), e dopo si scorre con l’iteratore. Si potrebbe anche fare in un altro modo, in effetti: si potrebbero generare gli elementi della lista man mano che servono e solo se servono. Ed è in parte quello che fa Haskell con la sua pigrizia: calcola gli elementi man mano che servono e solo se servono. E quindi, in Python hanno pensato che questa cosa qui fosse effettivamente utile, e hanno pensato di fornirla con il concetto di generatore.

Cominciamo a vedere in pratica come si fa: nell’esempietto precedente, invece di chiamare range bisogna chiamare xrange così:

#ciclo normale
for i in range(1,10) :
    print i

#ciclo con generatore
for i in xrange(1,10) :
    print i

Nel secondo caso, xrange non costruisce la lista, ma un semplice generatore, ovvero un oggetto che fornisce un iteratore, e ogni volta che avanzate l’iteratore, esso calcola al momento il nuovo valore da restituire. Dal punto di vista della performance non è cambiato molto in questo semplice caso.

Ma supponiamo adesso di voler costruire la sequenza dei primi 10.000 numeri Fibonacci. La lista risultante prenderà un po’ di spazio in memoria, e magari non ci servirà tutta, oppure ci servivà solo per fare il ciclo e da nessun’altra parte nel programma. In tal caso, usare un generatore invece di una lista permette di risparmiare memoria, e magari anche tempo.

Naturalmente adesso ci serve capire come costruire un generatore per i numeri di Fibonacci. Eccolo:

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

import sys

def fibGen() :
    a,b = 1,1
    while True :
        yield a
        a,b = b, a+b

n = int(sys.argv[1])
for k in fibGen() :
    print k,
    n -= 1
    if n == 0 :
        break

La funzione fibGen() è in realtà un generatore: da cosa si capisce? dal fatto che invece di ritornare il risultato con la keyword return, usa yield. Ecco come funziona:

  • Per prima cosa si inizializzano le variabili a e b a 1 e 1, rispettivamente.
  • Poi si effettua un ciclo infinito (che infinito non è in realtà!) con la while(True)
  • Viene chiamata yield, che ritorna il valore della variabile a (cioè 1). Però, a differenza di return, la yield si “segna” il punto in cui ci eravamo fermati, e il valore di tutte le variabili locali, così che, la prossima volta che si invocherà, si riparte dal punto in cui ci eravamo fermati.
  • La prossima volta che si invoca, si riparte dallo stato precedente, e a e b vengono aggiornati
  • quindi si ritorna il valore di a, e così via

Come si invoca fibGen()? esattamente come la range, solo che stavolta, se voglio fermarmi ad un certo punto, devo inserire una condizione di uscita dal ciclo con la break. Carino, no? La funzione fibGen() genera una lista potenzialmente infinita, ma un numero alla volta!

Non sarà tutto automatico come in Haskell, ma alla fine abbiamo messo dentro le liste infinite anche qui. Ecco l’output:

Ultima cosa: ricordatevi che il tipo int è limitato a 2.147.483.647, ma c’è il long che sopperisce e permette interi illimitati: vedi la documentazione Python, o anche:

Alla prossima!

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 71 follower