Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Haskell - Functor, Monoid, Monad
Forum - Haskell - Functor, Monoid, Monad

Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 1:23
Sabato, 21/02/2015
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.


Il mio blog: https://piero.dev
PM Quote
Avatar
marco (Member)
Newbie


Messaggi: 6
Iscritto: 19/02/2015

Segnala al moderatore
Postato alle 10:28
Sabato, 21/02/2015
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):

Codice sorgente - presumibilmente Haskell

  1. class  Functor f  where
  2.     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)

Codice sorgente - presumibilmente Plain Text

  1. map :: (a -> b) -> [a] -> [b]
  2.  
  3. map _ []     = []
  4. 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)

Codice sorgente - presumibilmente Haskell

  1. instance  Functor Maybe  where
  2.     fmap _ Nothing       = Nothing
  3.     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):

Codice sorgente - presumibilmente Haskell

  1. class Monoid a where
  2.         mempty  :: a
  3.         mappend :: a -> a -> a



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

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

Codice sorgente - presumibilmente Plain Text

  1. instance Monoid [a] where
  2.         mempty  = []
  3.         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) http://ncatlab.org/nlab/show/category#with_a_family_of_col ...
(2) http://hackage.haskell.org/package/base-4.7.0.2/docs/src/G ...
(3) https://hackage.haskell.org/package/base-4.7.0.2/docs/src/G ...
(4) http://hackage.haskell.org/package/base-4.7.0.2/docs/src/D ...
(5) https://hackage.haskell.org/package/base-4.7.0.2/docs/src/D ...
(6) https://hackage.haskell.org/package/base-4.7.0.2/docs/src/D ...


Latex:

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

PM Quote
Avatar
ZioCrocifisso (Member)
Pro


Messaggi: 135
Iscritto: 06/03/2013

Segnala al moderatore
Postato alle 15:34
Sabato, 21/02/2015
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.

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 16:40
Sabato, 21/02/2015
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?)


Il mio blog: https://piero.dev
PM Quote
Avatar
ZioCrocifisso (Member)
Pro


Messaggi: 135
Iscritto: 06/03/2013

Segnala al moderatore
Postato alle 16:53
Sabato, 21/02/2015
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.

Ultima modifica effettuata da ZioCrocifisso il 21/02/2015 alle 17:09
PM Quote