Haskell - Functor, Monoid, Monad

Più leggo e più mi sta venendo confusione... qualcuno potrebbe spiegarmi in italiano semplice a cosa serve ognuno (magari con un esempio pratico di dove il loro utilizzo è utile)? Forse leggendo una spiegazione alternativa riuscirò a farmi una migliore idea.

Un funtore è una freccia tra due categorie(1). Siano C e D due categorie, allora un funtore F : C -> D è composto da una funzione(lasciamo perdere le questioni di dimensione)

F_0 : obj(C) \to obj(D)

che mappa gli oggetti della prima categoria negli oggetti della seconda categoria, e un'altra funzione

F_1 : mor(C) \to mor(D)

che mappa morfismi di C in morfismi di D, tale che

F_1 id = id
F_1 (f . g) = (F_1 f) . (F_1 g)

dove con . si intende la composizione di morfismi. Spesso, siccome i morfismi sono legati agli oggetti, invece che specificare le due mappe separatamente si fa in un colpo solo, cioè:

F : (A \to B) \mapsto (F(A) \to F(B))

dove A e B sono oggetti della categoria C.

Esempi pratici:

Sia C una qualsiasi categoria(Sets, Ord, Grp, Ab, Vect, Top, ...), allora il funtore

F : C -> C

definito come

F_0 : A \mapsto A
F_1 : f \mapsto f

è un funtore, detto funtore identico. Per dimostrare ciò bisogna verificare le due leggi, cioè che

F_1 id = id

che è vera per definizione, e

F_1 (f . g) = f . g = (F_1 f) . (F_1 g).

I funtori che hanno per dominio e codominio la stessa categoria vengono detti endofuntori.

Altro esempio, considera la categoria degli insiemi, allora hai l'endofuntore

Pow : Sets -> Sets

che mappa ogni insieme nel suo insieme delle parti, cioè nell'insieme dei suoi sottoinsiemi

Pow_0 A = {X . X \subset A}

e che mappa una funzione f : A -> B in una funzione tra insiemi delle parti, che usando la notazione del lambda calcolo può essere scritta come

Pow_1 f = λA -> f(A)

dove con f(A) intendiamo l'immagine dell'insieme A tramite f, cioè l'insieme {f(a) . a \in A}.

È questo un funtore?

Pow_1 id = λA -> id(A) = λA -> A = id
Pow_1 (f . g) = λA -> (f . g) A = λA -> f (g A) = (λA -> f A) . (λA -> g A) = (Pow_1 f) . (Pow_1 g)

quindi Pow è un funtore.

Ultimo esempio, sia C una categoria arricchita su Sets(categoria dei gruppi, spazi topologici etc.), allora il funtore dimenticante(underlying functor)

U : C -> Sets

che "dimentica la struttura" mandando l'oggetto arricchito al suo supporto e i morfismi tra oggetti arricchiti alle rispettive funzioni tra supporti è banalmente un funtore.

Forti di questi esempi, vediamo cosa succede in Haskell.

Se si considera la classe di tutti i tipi T e le funzioni tra i vari tipi si ottiene una categoria, detta Hask.

Guardiamo ora la definizione di Functor(2):

class  Functor f  where
    fmap        :: (a -> b) -> f a -> f b

come puoi notare f mappa a e b della categoria Hask in f a e f b, di una certa categoria, mentre fmap mappa frecce a -> b della categoria Hask in frecce f a -> f b.

Casi concreti:

consideriamo a categoria List delle liste, cioè dei tipi [T], abbiamo(3)

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

map _ []     = []
map f (x:xs) = f x : map f xs

Si tratta di un funtore Hask -> List?

map id [] = []
map id (x : xs) = x : map id xs = induzione = (x : xs)

quindi

map id = id.

map (f . g) [] = []
map (f . g) (x : xs) = (f . g) x : map (f . g) xs = induzione = (map f) (map g) (x : xs)

da cui

map (f . g) = (map f) . (map g).

Secondo esempio:

consideriamo la categoria Maybe, i cui oggetti sono al solito i tipi Maybe T, allora(4)

instance  Functor Maybe  where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

fmap è un funtore. Infatti

fmap id Nothing = Nothing
fmap id (Just a) = Just (id a) = Just a

fmap (f . g) Nothing = Nothing = (fmap f) . (fmap g) Nothing.

A cosa possono servire i funtori? Afaik, ad estendere funzioni su alcuni tipi particolari, come Maybe e List. I funtori sono i morfismi "giusti" delle categorie.

--

Un monoide in linea di massima è una struttura definita su una categoria monoidale (C, ⊗, 1, ...), dove C è una categoria, ⊗ un prodotto tensoriale(un bifuntore C x C -> C) e 1 l'oggetto unitario, e ... sono un po' di isomorfismi naturali.

In particolare un monoide M è formato da un oggetto M di C, una funzione(solitamente detta prodotto) * : M ⊗ M -> M e un'unità e : 1 -> M, e soddisfa la proprietà associativa e dell'unità.

In particolare se si considera la categoria Sets, si prende come prodotto tensoriale il prodotto cartesiano e come oggetto unitario l'insieme {{}} si ottiene una categoria monoidale.

Un monoide in quella categoria diventa allora un insieme M dotato di un'operazione binaria interna associativa M x M -> M e un elemento e di M che funge da unità.

In haskell i monoidi non sono niente di diverso(5):

class Monoid a where
        mempty  :: a
        mappend :: a -> a -> a

mempty è l'unità e mappend è l'operazione binaria.

Un esempio classico di monoide è quello delle liste(6):

instance Monoid [a] where
        mempty  = []
        mappend = (++)

l'elemento neutro è la lista vuota, e l'operazione binaria interna associativa è la concatenazione. Le liste su un alfabeto A sono il monoide libero generato da A, quindi sono in un certo qual modo speciali.

Per concludere, data una categoria C, la categoria degli endofuntori di C, End(C), è una categoria monoidale rispetto alla composizione di endofuntori e considerando come unità l'endofuntore identico.

Una monade su C è semplicemente un monoide in End(C).


Credo di non saperti spiegare perché sono utili, meglio che lo faccia qualcuno più esperto.


(1) ncatlab.org/nlab/show/…
(2) hackage.haskell.org/package/base-4.7.0.2/docs/src/…
(3) hackage.haskell.org/package/base-4.7.0.2/docs/src/…
(4) hackage.haskell.org/package/base-4.7.0.2/docs/src/…
(5) hackage.haskell.org/package/base-4.7.0.2/docs/src/…
(6) hackage.haskell.org/package/base-4.7.0.2/docs/src/…


Latex:

\to corrisponde alla freccia ->
\mapsto corrisponde alla freccia |->, cioè specifica qual'è l'immagine di un certo elemento.

marco ti ha spiegato cosa sono dal punto di vista della teoria delle categorie, ma il fatto che questa sia necessaria per usare Haskell è un luogo comune errato. Ha soltanto ispirato alcuni dei suoi concetti. Riguardo alla tua domanda, tutte e tre le classi sono molto astratte, pertanto non è possibile dare una spiegazione che comprenda tutti i casi. IO, le liste e le funzioni sono tutti funtori, ma è difficile trovare punti in comune, se non le operazioni e le leggi dei funtori che rispettano. Un esempio di utilizzo dei funtori è nella creazione di funzioni che agiscono su qualunque tipo di collezione (usando il polimorfismo con Functor come constraint). Tuttavia, non tutti i funtori sono collezioni, e non tutte le collezioni sono funtori. Inoltre, i funtori rappresentano soltanto un aspetto delle collezioni, quello della modifica di tutti gli elementi con una funzione che agisce su di uno (map). Altre operazioni/aspetti sono rappresentati da classi come Foldable e Traversable, ma anche Monoid, che rappresenta l'aspetto "concatenativo". Ma anche i monoidi (che dal punto di vista di Haskell, ma non della CT, non c'entrano nulla con le monadi) hanno altri esempi di istanze che non sono collezioni, come i numeri*. Quindi, come per i funtori, non si può dare una spiegazione che comprenda tutti i casi, se non quella riguardante le sue operazioni (l'operatore associativo e l'elemento di identità e le leggi. Rispetto alle altre typeclass, le monadi hanno qualcosa di speciale. Infatti, Haskell ha una sintassi apposita, la do-notation, che funziona con tutte le monadi (con un'estensione è possibile estendere alle monadi anche le list comprehension). Si tratta soltanto di zucchero sintattico, perché ogni blocco do può essere sostituito con le operazioni della typeclass Monad (>>= e return), tuttavia è molto utile e fa intuire che tipicamente sono monadi i tipi che rappresentano computazioni in sequenza (IO, ST, State, ecc.).

* Poiché si possono formare più istanze di Monoid per i Num, questi non hanno un'istanza diretta, ma vengono usati i wrapper Sum e Product. Ciò non è vero però per i funtori, che, come è stato dimostrato, possono avere un'unica istanza.

Grazie entrambi per le risposte! Wow.

Quindi in sostanza:
- I functor (funtori) sono per poter eseguire fmap.
- I monoid (monoidi) catturano certe proprietà matematiche (function composition all'interno di un set) per poi poter applicare funzioni generali che rispettano queste proprietà.
- Le monad (monadi) catturano altre proprietà matematiche (computazioni definite da una serie di passi o sequenze), sempre per poter applicare funzioni generali che rispettano queste proprietà.

E' più o meno questo il sunto (a parte una dozzina di eccezioni?)

Con le definizioni che hai dato (non del tutto corrette) non ci sono eccezioni. Ci sono se definisci i funtori come collezioni, i monoidi come numeri, le monadi come computazioni, ecc.
Lo scopo comunque è quello, sfruttare il polimorfismo. Ti consiglio in ogni caso di non porti troppi problemi riguardo a queste typeclasses per ora, ti basta sapere cosa definiscono. Imparerai a riconoscerle e a usarle con l'esperienza.