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!

Posta un commento o usa questo indirizzo per il trackback.

Commenti

  • zar  Il 15 novembre 2011 alle 17:10

    (Gulp)

    • glipari  Il 16 novembre 2011 alle 09:14

      E non hai visto ancora quello che viene dopo (gasp). Io per esempio i “lazy patterns” ancora non è che li abbia capiti molto bene …

  • Mattux  Il 16 novembre 2011 alle 16:24

    Ottimo post! Veramente, complimenti 😀

Trackback

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: