Skip to content

Cosa significa "coalgebra" nel contesto della programmazione?

Ciao, abbiamo trovato la soluzione alla tua domanda, scorri verso il basso e la vedrai un po' più in basso.

Soluzione:

Algebre

Penso che il punto di partenza sia la comprensione dell'idea di un algebra. Si tratta di una generalizzazione di strutture algebriche come gruppi, anelli, monoidi e così via. Nella maggior parte dei casi, queste cose vengono introdotte in termini di insiemi, ma dato che siamo tra amici, parlerò invece di tipi Haskell. (Non posso però resistere all'uso di lettere greche: fanno sembrare tutto più figo).

Un'algebra, quindi, è solo un tipo τ con alcune funzioni e identità. Queste funzioni prendono un numero diverso di argomenti di tipo τ e producono un τnon curati, hanno tutti l'aspetto di (τ, τ,…, τ) → τ. Possono anche avere "identità" - elementi di τ che hanno un comportamento speciale con alcune funzioni.

L'esempio più semplice è il monoide. Un monoide è un qualsiasi tipo τ con una funzione mappend ∷ (τ, τ) → τ e un'identità mzero ∷ τ. Altri esempi includono cose come i gruppi (che sono proprio come i monoidi, ma con un extra invert ∷ τ → τ funzione in più), gli anelli, i reticoli e così via.

Tutte le funzioni operano su τ ma possono avere arità diverse. Possiamo scriverle come τⁿ → τ, dove τⁿ corrisponde a una tupla di nτ. In questo modo, ha senso pensare alle identità come τ⁰ → τ dove τ⁰ è solo la tupla vuota (). Ora possiamo semplificare l'idea di algebra: è solo un tipo con un certo numero di funzioni.

Un'algebra è solo uno schema comune in matematica che è stato "sfaccettato", proprio come facciamo con il codice. Le persone hanno notato che tutta una serie di cose interessanti - i già citati monoidi, gruppi, reticoli e così via - seguono tutti uno schema simile, quindi lo hanno astratto. Il vantaggio di questa operazione è lo stesso della programmazione: crea prove riutilizzabili e facilita certi tipi di ragionamento.

Algebre F

Tuttavia, non abbiamo ancora finito con la fattorizzazione. Finora abbiamo un gruppo di funzioni τⁿ → τ. Possiamo in realtà fare un bel trucco per combinarle tutte in un'unica funzione. In particolare, consideriamo i monoidi: abbiamo mappend ∷ (τ, τ) → τ e mempty ∷ () → τ. Possiamo trasformarli in un'unica funzione utilizzando un tipo di somma.Either. L'aspetto sarebbe il seguente:

op ∷ Monoid τ ⇒ Either (τ, τ) () → τ
op (Left (a, b)) = mappend (a, b)
op (Right ())    = mempty

Possiamo usare questa trasformazione ripetutamente per combinare tutti il τⁿ → τ in un'unica funzione, per qualsiasi algebra. (In realtà, possiamo fare questo per qualsiasi numero di funzioni a → τ, b → τ e così via per qualsiasia, b,….)

Questo ci permette di parlare di algebre come un tipo τ con un singolo da una serie di funzioni Eitherad un singolo τ. Per i monoidi, questa confusione è: Either (τ, τ) (); per i gruppi (che hanno un ulteriore τ → τ in più), è: Either (Either (τ, τ) τ) (). È un tipo diverso per ogni diversa struttura. Che cosa hanno in comune tutti questi tipi? La cosa più ovvia è che sono tutti somme di prodotti, tipi di dati algebrici. Per esempio, per i monoidi, si può creare un tipo di argomento monoide che funzioni per qualsiasi monoide τ:

data MonoidArgument τ = Mappend τ τ -- here τ τ is the same as (τ, τ)
                      | Mempty      -- here we can just leave the () out

Possiamo fare la stessa cosa per i gruppi, gli anelli, i reticoli e tutte le altre strutture possibili.

Cos'altro c'è di speciale in tutti questi tipi? Beh, sono tutti Functors! Ad esempio:

instance Functor MonoidArgument where
  fmap f (Mappend τ τ) = Mappend (f τ) (f τ)
  fmap f Mempty        = Mempty

Possiamo quindi generalizzare ancora di più la nostra idea di algebra. È solo un tipo τ con una funzione f τ → τ per qualche funtore f. In effetti, potremmo scriverlo come una classe di tipi:

class Functor f ⇒ Algebra f τ where
  op ∷ f τ → τ

Questa viene spesso chiamata "algebra F" perché è determinata dal funtore F. Se potessimo applicare parzialmente le classi di tipi, potremmo definire qualcosa come class Monoid = Algebra MonoidArgument.

Algebre di carbone

Ora, si spera che abbiate una buona conoscenza di cosa sia un'algebra e di come sia solo una generalizzazione delle normali strutture algebriche. Che cos'è dunque una F-coalgebra? Il termine "co" implica che si tratta del "duale" di un'algebra, cioè che prendiamo un'algebra e invertiamo alcune frecce. Nella definizione precedente vedo solo una freccia, quindi la invertirò:

class Functor f ⇒ CoAlgebra f τ where
  coop ∷ τ → f τ

Ed è tutto qui! Ora, questa conclusione può sembrare un po' stravagante (heh). Vi dice cosa una coalgebra, ma non dà alcuna idea di come sia utile o perché ci interessi. Ci arriverò tra un po', una volta trovato o trovato un buon esempio o due :P.

Classi e oggetti

Dopo aver letto un po' in giro, credo di avere una buona idea di come usare le coalgebre per rappresentare classi e oggetti. Abbiamo un tipo C che contiene tutti i possibili stati interni degli oggetti della classe; la classe stessa è una coalgebra su C che specifica i metodi e le proprietà degli oggetti.

Come mostrato nell'esempio dell'algebra, se abbiamo un gruppo di funzioni come a → τ e b → τ per qualsiasi a, b,…possiamo combinarli tutti in un'unica funzione usando Either, un tipo di somma. La "nozione" duale sarebbe la combinazione di un insieme di funzioni di tipo τ → a, τ → b e così via. Possiamo farlo utilizzando il duale di un tipo somma: un tipo prodotto. Quindi, date le due funzioni di cui sopra (chiamate f e g), possiamo crearne una singola come questa:

both ∷ τ → (a, b)
both x = (f x, g x)

Il tipo (a, a) è un funtore in senso stretto, quindi si adatta certamente alla nostra nozione di F-coalgebra. Questo particolare trucco ci permette di impacchettare un insieme di funzioni diverse - o, per l'OOP, di metodi - in un'unica funzione di tipo τ → f τ.

Gli elementi del nostro tipo C rappresentano le funzioni interno dell'oggetto. Se l'oggetto ha delle proprietà leggibili, queste devono poter dipendere dallo stato. Il modo più ovvio per farlo è renderle una funzione di C. Quindi, se vogliamo che una proprietà di lunghezza (ad es. object.length), avremo una funzione C → Int.

Vogliamo metodi che accettino un argomento e modifichino lo stato. Per farlo, dobbiamo prendere tutti gli argomenti e produrre un nuovo metodo C. Immaginiamo un metodo setPosition che prende un parametro x e un y coordinate: object.setPosition(1, 2). L'aspetto sarebbe il seguente: C → ((Int, Int) → C).

Lo schema importante è che i "metodi" e le "proprietà" dell'oggetto prendono l'oggetto stesso come primo argomento. Questo è proprio come il metodo self in Python e come il parametro implicito this di molti altri linguaggi. Una coalgebra essenzialmente incapsula il comportamento del prendere un parametro self è ciò che il primo parametro C in C → F C è.

Quindi mettiamo tutto insieme. Immaginiamo una classe con un elemento position una proprietà, una name e setPosition funzione:

class C
  private
    x, y  : Int
    _name : String
  public
    name        : String
    position    : (Int, Int)
    setPosition : (Int, Int) → C

Abbiamo bisogno di due parti per rappresentare questa classe. In primo luogo, dobbiamo rappresentare lo stato interno dell'oggetto; in questo caso contiene solo due Inte un String. (Questo è il nostro tipo C.) Poi dobbiamo trovare la coalgebra che rappresenta la classe.

data C = Obj { x, y  ∷ Int
             , _name ∷ String }

Abbiamo due proprietà da scrivere. Sono piuttosto banali:

position ∷ C → (Int, Int)
position self = (x self, y self)

name ∷ C → String
name self = _name self

Ora dobbiamo solo essere in grado di aggiornare la posizione:

setPosition ∷ C → (Int, Int) → C
setPosition self (newX, newY) = self { x = newX, y = newY }

Questo è proprio come una classe Python con le sue proprietà esplicite self variabili. Ora che abbiamo un gruppo di variabili self → dobbiamo combinarle in un'unica funzione per la coalgebra. Possiamo farlo con una semplice tupla:

coop ∷ C → ((Int, Int), String, (Int, Int) → C)
coop self = (position self, name self, setPosition self)

Il tipo ((Int, Int), String, (Int, Int) → c)-per qualsiasic-è un funtore, quindi coop ha la forma che vogliamo: Functor f ⇒ C → f C.

Dato questo, C insieme a coop formano una coalgebra che specifica la classe che ho dato sopra. Si può vedere come si possa usare questa stessa tecnica per specificare un numero qualsiasi di metodi e proprietà che i nostri oggetti devono avere.

Questo ci permette di usare il ragionamento coalgebrico per trattare le classi. Per esempio, possiamo introdurre la nozione di "omomorfismo F-coalgebrico" per rappresentare le trasformazioni tra classi. Si tratta di un termine dal suono spaventoso che indica semplicemente una trasformazione tra coalgebre che preserva la struttura. In questo modo è molto più semplice pensare alla mappatura di classi su altre classi.

In breve, una coalgebra F rappresenta una classe con un insieme di proprietà e metodi che dipendono tutti da una classe di tipo self contenente lo stato interno di ciascun oggetto.

Altre categorie

Finora abbiamo parlato di algebre e coalgebre come tipi Haskell. Un'algebra è solo un tipo τ con una funzione f τ → τ e una coalgebra è solo un tipo τ con una funzione τ → f τ.

Tuttavia, nulla lega realmente queste idee ad Haskell di per sé. Infatti, di solito vengono introdotte in termini di insiemi e funzioni matematiche piuttosto che di tipi e funzioni Haskell. In effetti, possiamo generalizzare questi concetti a qualsiasi categorie!

Possiamo definire un'algebra F per una categoria C. Per prima cosa, abbiamo bisogno di un funtore F : C → C-cioè un endofuntore. (Tutti gli Haskell Functorsono in realtà endofuntori di Hask → Hask.) Quindi, un'algebra è solo un oggetto A da C con un morfismo F A → A. Una coalgebra è la stessa cosa, ma con A → F A.

Che cosa otteniamo considerando altre categorie? Possiamo usare le stesse idee in contesti diversi. Come le monadi. In Haskell, una monade è un tipo M ∷ ★ → ★ con tre operazioni:

map      ∷ (α → β) → (M α → M β)
return   ∷ α → M α
join     ∷ M (M α) → M α

Il map è solo una prova del fatto che M è un Functor. Quindi possiamo dire che una monade è solo un funtore con due operazioni: return e join.

I funtori formano una categoria a sé stante, e i morfismi tra di essi sono le cosiddette "trasformazioni naturali". Una trasformazione naturale è solo un modo per trasformare un funtore in un altro preservandone la struttura. Ecco un bell'articolo che spiega l'idea. Parla di concatche è semplicemente join per le liste.

Con i funtori Haskell, la composizione di due funtori è essa stessa un funtore. In pseudocodice, potremmo scrivere questo:

instance (Functor f, Functor g) ⇒ Functor (f ∘ g) where
  fmap fun x = fmap (fmap fun) x

Questo ci aiuta a pensare a join come una mappatura da f ∘ f → f. Il tipo di join è ∀α. f (f α) → f α. Intuitivamente, possiamo vedere come una funzione valida per tutti tipi α può essere pensato come una trasformazione di f.

return è una trasformazione simile. Il suo tipo è ∀α. α → f α. L'aspetto è diverso: il primo α non è "in" un funtore! Fortunatamente, possiamo risolvere il problema aggiungendo un funtore di identità: ∀α. Identity α → f α. Quindi return è una trasformazione Identity → f.

Ora possiamo pensare a una monade come a un'algebra basata su un funtore f con operazioni f ∘ f → f e Identity → f. Non vi sembra familiare? È molto simile a un monoide, che era semplicemente un tipo τ con operazioni τ × τ → τ e () → τ.

Quindi una monade è proprio come un monoide, solo che invece di avere un tipo abbiamo un funtore. È lo stesso tipo di algebra, solo in una categoria diversa. (Per quanto ne so, è da qui che deriva la frase "Una monade è solo un monoide nella categoria degli endofuntori").

Ora, abbiamo queste due operazioni: f ∘ f → f e Identity → f. Per ottenere la coalgebra corrispondente, basta invertire le frecce. Si ottengono così due nuove operazioni: f → f ∘ f e f → Identity. Possiamo trasformarle in tipi Haskell aggiungendo variabili di tipo come sopra, ottenendo così ∀α. f α → f (f α) e ∀α. f α → α. Questo assomiglia alla definizione di una comonade:

class Functor f ⇒ Comonad f where
  coreturn ∷ f α → α
  cojoin   ∷ f α → f (f α)

Una comonade è quindi una coalgebra in una categoria di endofuntori.

Le F-algebre e le F-coalgebre sono strutture matematiche strumentali al ragionamento su tipi induttivi (o tipi ricorsivi).

Algebre F

Cominceremo prima con gli algebri F. Cercherò di essere il più semplice possibile.

Immagino che sappiate cosa sia un tipo ricorsivo. Per esempio, questo è un tipo per una lista di numeri interi:

data IntList = Nil | Cons (Int, IntList)

È ovvio che è ricorsivo, infatti la sua definizione si riferisce a se stesso. La sua definizione consiste in due costruttori di dati, che hanno i seguenti tipi:

Nil  :: () -> IntList
Cons :: (Int, IntList) -> IntList

Si noti che ho scritto tipo di Nil come () -> IntListe non semplicemente IntList. Si tratta infatti di tipi equivalenti dal punto di vista teorico, perché () ha un solo abitante.

Se scriviamo le firme di queste funzioni in modo più teorico, otterremo

Nil  :: 1 -> IntList
Cons :: Int × IntList -> IntList

dove 1 è un insieme unitario (insieme con un elemento) e A × B è un prodotto incrociato di due insiemi A e B (cioè l'insieme di coppie (a, b) dove a passa attraverso tutti gli elementi di A e b attraversa tutti gli elementi di B).

Unione disgiunta di due insiemi A e B è un insieme A | B che è l'unione degli insiemi {(a, 1) : a in A} e {(b, 2) : b in B}. Essenzialmente è un insieme di tutti gli elementi di entrambi gli insiemi A e B, ma con ciascuno di questi elementi "marcato" come appartenente a uno dei due gruppi A o B, quindi quando scegliamo un qualsiasi elemento da A | B sapremo immediatamente se questo elemento proviene da A o da B.

Possiamo 'unire' Nil e Cons in modo che formino un'unica funzione che lavora su un set 1 | (Int × IntList):

Nil|Cons :: 1 | (Int × IntList) -> IntList

Infatti, se Nil|Cons viene applicata a () (che, ovviamente, appartiene a 1 | (Int × IntList) si comporta come se fosse un valore di Nil; se Nil|Cons è applicato a qualsiasi valore di tipo (Int, IntList) (tali valori sono anche nell'insieme 1 | (Int × IntList)si comporta come Cons.

Consideriamo ora un altro tipo di dato:

data IntTree = Leaf Int | Branch (IntTree, IntTree)

Ha i seguenti costruttori:

Leaf   :: Int -> IntTree
Branch :: (IntTree, IntTree) -> IntTree

che possono essere uniti in un'unica funzione:

Leaf|Branch :: Int | (IntTree × IntTree) -> IntTree

Si può notare che entrambi i costruttori joined hanno un tipo simile: sono entrambe simili a

f :: F T -> T

dove F è un tipo di trasformazione che prende il nostro tipo e dà un tipo più complesso, che consiste in x e | operazioni, usi di T ed eventualmente di altri tipi. Ad esempio, per IntList e IntTreeF si presenta come segue:

F1 T = 1 | (Int × T)
F2 T = Int | (T × T)

Notiamo subito che qualsiasi tipo algebrico può essere scritto in questo modo. Infatti, è per questo che si chiamano "algebrici": sono costituiti da un certo numero di "somme" (unioni) e "prodotti" (prodotti incrociati) di altri tipi.

Ora possiamo definire l'algebra F. Algebra F è solo una coppia (T, f), dove T è un tipo e f è una funzione di tipo f :: F T -> T. Nei nostri esempi le algebre F sono (IntList, Nil|Cons) e (IntTree, Leaf|Branch). Si noti, tuttavia, che nonostante il tipo di f la funzione è la stessa per ogni F, T e f possono essere arbitrari. Ad esempio, (String, g :: 1 | (Int x String) -> String) o (Double, h :: Int | (Double, Double) -> Double) per alcuni g e h sono anche algebre F per F corrispondente.

In seguito possiamo introdurre gli omomorfismi delle algebre F e quindi algebre F iniziali che hanno proprietà molto utili. Infatti, (IntList, Nil|Cons) è un'algebra F1 iniziale e (IntTree, Leaf|Branch) è un'algebra F2 iniziale. Non presenterò le definizioni esatte di questi termini e proprietà perché sono più complesse e astratte del necessario.

Tuttavia, il fatto che, ad esempio, (IntList, Nil|Cons) sia un'algebra F ci permette di definire fold-su questo tipo di funzione. Come è noto, la piegatura è un tipo di operazione che trasforma alcuni tipi di dati ricorsivi in un unico valore finito. Ad esempio, possiamo piegare un elenco di numeri interi in un unico valore che è la somma di tutti gli elementi dell'elenco:

foldr (+) 0 [1, 2, 3, 4] -> 1 + 2 + 3 + 4 = 10

È possibile generalizzare tale operazione su qualsiasi tipo di dato ricorsivo.

La seguente è una firma di foldr funzione:

foldr :: ((a -> b -> b), b) -> [a] -> b

Si noti che ho usato le parentesi graffe per separare i primi due argomenti dall'ultimo. Questo non è un vero e proprio foldr ma è isomorfa ad essa (cioè, si può facilmente ottenere una dall'altra e viceversa). Applicazione parziale foldr avrà la seguente firma:

foldr ((+), 0) :: [Int] -> Int

Possiamo notare che si tratta di una funzione che prende un elenco di numeri interi e restituisce un singolo numero intero. Definiamo questa funzione in termini di IntList tipo.

sumFold :: IntList -> Int
sumFold Nil         = 0
sumFold (Cons x xs) = x + sumFold xs

Vediamo che questa funzione è composta da due parti: la prima definisce il comportamento di questa funzione su Nil parte di IntListe la seconda parte definisce il comportamento della funzione su Cons parte.

Supponiamo ora di non programmare in Haskell, ma in un linguaggio che permetta l'uso di tipi algebrici direttamente nelle firme dei tipi (tecnicamente Haskell permette l'uso di tipi algebrici tramite tuple e Either a b ma questo porta a un'inutile verbosità). Consideriamo una funzione:

reductor :: () | (Int × Int) -> Int
reductor ()     = 0
reductor (x, s) = x + s

Si può notare che reductor è una funzione di tipo F1 Int -> Intproprio come nella definizione di algebra F! Infatti, la coppia (Int, reductor) è un'algebra F1.

Perché IntList è un'algebra F1 iniziale, per ogni tipo di T e per ogni funzione r :: F1 T -> T esiste una funzione, chiamata catamorfismo per rche converte IntList a Te tale funzione è unica. In effetti, nel nostro esempio, un catamorfismo per reductor è sumFold. Si noti come reductor e sumFold sono simili: hanno quasi la stessa struttura! In reductor definizione s l'uso dei parametri (il cui tipo corrisponde a T) corrisponde all'utilizzo del risultato del calcolo di sumFold xs in sumFold definizione.

Per rendere il tutto più chiaro e per aiutarvi a vedere lo schema, ecco un altro esempio, sempre partendo dalla funzione di piegatura risultante. Consideriamo append che aggiunge il primo argomento al secondo:

(append [4, 5, 6]) [1, 2, 3] = (foldr (:) [4, 5, 6]) [1, 2, 3] -> [1, 2, 3, 4, 5, 6]

Ecco come appare sul nostro IntList:

appendFold :: IntList -> IntList -> IntList
appendFold ys ()          = ys
appendFold ys (Cons x xs) = x : appendFold ys xs

Di nuovo, proviamo a scrivere il riduttore:

appendReductor :: IntList -> () | (Int × IntList) -> IntList
appendReductor ys ()      = ys
appendReductor ys (x, rs) = x : rs

appendFold è un catamorfismo per appendReductor che trasforma IntList in IntList.

Quindi, essenzialmente, le algebre F ci permettono di definire "pieghe" sulle strutture di dati ricorsive, cioè operazioni che riducono le nostre strutture a qualche valore.

F-coalgebre

Le F-coalgebre sono il cosiddetto termine "duale" delle F-algebre. Ci permettono di definire unfolds per i tipi di dati ricorsivi, cioè un modo per costruire strutture ricorsive a partire da un valore.

Supponiamo di avere il seguente tipo:

data IntStream = Cons (Int, IntStream)

Si tratta di un flusso infinito di numeri interi. Il suo unico costruttore ha il seguente tipo:

Cons :: (Int, IntStream) -> IntStream

Oppure, in termini di insiemi

Cons :: Int × IntStream -> IntStream

Haskell consente di effettuare pattern match sui costruttori di dati, quindi è possibile definire le seguenti funzioni che lavorano su IntStreams:

head :: IntStream -> Int
head (Cons (x, xs)) = x

tail :: IntStream -> IntStream
tail (Cons (x, xs)) = xs

Si possono naturalmente 'unire' queste funzioni in una singola funzione di tipo IntStream -> Int × IntStream:

head&tail :: IntStream -> Int × IntStream
head&tail (Cons (x, xs)) = (x, xs)

Si noti come il risultato della funzione coincida con la rappresentazione algebrica della nostra funzione IntStream del nostro tipo IntStream . Una cosa simile può essere fatta anche per altri tipi di dati ricorsivi. Forse avete già notato lo schema. Mi riferisco a una famiglia di funzioni di tipo

g :: T -> F T

dove T è un tipo. D'ora in poi definiremo

F1 T = Int × T

Ora, F-coalgebra è una coppia (T, g), dove T è un tipo e g è una funzione di tipo g :: T -> F T. Ad esempio, (IntStream, head&tail) è una coalgebra F1. Anche in questo caso, come per le algebre F, g e T possono essere arbitrari, ad esempio (String, h :: String -> Int x String) è anche una coalgebra F1 per qualche h.

Tra tutte le coalgebre F ci sono le cosiddette le cosiddette coalgebre F terminali, che sono duali alle algebre F iniziali. Ad esempio, IntStreamè una F-coalgebra terminale. Ciò significa che per ogni tipo T e per ogni funzione p :: T -> F1 T esiste una funzione, chiamata anamorfismo che converte T a IntStreame tale funzione è unica.

Consideriamo la seguente funzione, che genera un flusso di numeri interi successivi a partire da quello dato:

nats :: Int -> IntStream
nats n = Cons (n, nats (n+1))

Esaminiamo ora una funzione natsBuilder :: Int -> F1 Int, cioè, natsBuilder :: Int -> Int × Int:

natsBuilder :: Int -> Int × Int
natsBuilder n = (n, n+1)

Anche in questo caso, possiamo notare una certa somiglianza tra nats e natsBuilder. È molto simile alla connessione che abbiamo osservato in precedenza con i riduttori e le pieghe. nats è un anamorfismo per natsBuilder.

Un altro esempio, una funzione che accetta un valore e una funzione e restituisce un flusso di applicazioni successive della funzione al valore:

iterate :: (Int -> Int) -> Int -> IntStream
iterate f n = Cons (n, iterate f (f n))

La sua funzione costruttrice è la seguente:

iterateBuilder :: (Int -> Int) -> Int -> Int × Int
iterateBuilder f n = (n, f n)

Allora iterate è un anamorfismo per iterateBuilder.

Conclusione

Quindi, in breve, le F-algebre permettono di definire pieghe, cioè operazioni che riducono la struttura ricorsiva in un unico valore, e le F-coalgebre permettono di fare il contrario: costruire un [potentially] struttura infinita a partire da un singolo valore.

In effetti in Haskell le F-algebre e le F-coalgebre coincidono. Questa è una proprietà molto bella che è una conseguenza della presenza di un valore "inferiore" in ogni tipo. Quindi in Haskell è possibile creare sia pieghe che pieghe per ogni tipo ricorsivo. Tuttavia, il modello teorico che sta dietro a questo è più complesso di quello che ho presentato sopra, quindi l'ho deliberatamente evitato.

Spero che questo sia d'aiuto.

Leggendo il documento del tutorial Un tutorial sulle (co)algebre e la (co)induzione dovrebbe darvi qualche idea sulla co-algebra in informatica.

Di seguito una citazione per convincervi,

In termini generali, un programma in un linguaggio di programmazione manipola dati. Durante lo
sviluppo dell'informatica negli ultimi decenni è diventato chiaro che una descrizione astratta di questi dati è auspicabile, ad esempio per garantire che una
descrizione astratta di questi dati è auspicabile, ad esempio per garantire che il programma non dipenda dalla particolare rappresentazione dei dati su cui opera. Inoltre, tale astrattezza facilita le prove di correttezza.
Questo desiderio ha portato all'uso di metodi algebrici in informatica, in una branca chiamata specificazione algebrica o teoria dei tipi di dati astratti. L'oggetto di studio sono i tipi di dati in sé, utilizzando nozioni e tecniche familiari all'algebra. I tipi di dati utilizzati dagli informatici sono spesso generati da una data collezione di operazioni (costruttori), ed è per questo motivo che l'"inizialità" delle algebre gioca un ruolo così importante.
Le tecniche algebriche standard si sono rivelate utili per catturare vari aspetti essenziali delle strutture dati utilizzate in informatica. Ma si è rivelato difficile descrivere algebricamente alcune delle strutture intrinsecamente dinamiche che si verificano nell'informatica. Tali strutture di solito implicano una nozione di stato, che può essere trasformata in vari modi. Gli approcci formali a tali sistemi dinamici basati sugli stati fanno generalmente uso di automi o sistemi di transizione, come primi riferimenti classici.
Nel corso dell'ultimo decennio è cresciuta l'idea che tali sistemi basati sugli stati non debbano essere descritti come algebre, ma come le cosiddette co-algebre. Queste sono il duale formale delle algebre, in un modo che verrà precisato in questo tutorial. La proprietà duale dell'"inizialità" delle algebre, ossia la finalità, si è rivelata cruciale per tali co-algebre. E il principio di ragionamento logico necessario per queste co-algebre finali non è l'induzione, ma la co-induzione.


Preludio, sulla teoria delle categorie.
La teoria delle categorie dovrebbe essere rinominata teoria dei funtori.
Poiché le categorie sono ciò che si deve definire per definire i funtori.
(Inoltre, i funtori sono ciò che si deve definire per definire le trasformazioni naturali).

Cos'è un funtore?
È una trasformazione da un insieme a un altro che ne conserva la struttura.
(Per maggiori dettagli ci sono molte buone descrizioni in rete).

Che cos'è un'algebra F?
È l'algebra dei funtori.
È solo lo studio della proprietà universale dei funtori.

Come può essere collegata all'informatica?
Il programma può essere visto come un insieme strutturato di informazioni.
L'esecuzione di un programma corrisponde alla modifica di questo insieme strutturato di informazioni.
È bene che l'esecuzione conservi la struttura del programma.
Allora l'esecuzione può essere vista come l'applicazione di un funtore su questo insieme di informazioni.
(Quello che definisce il programma).

Perché la F-co-algebra?
I programmi sono duali per essenza in quanto sono descritti da informazioni e agiscono su di esse.
Quindi le informazioni che compongono il programma e lo modificano possono essere viste in due modi.

  • I dati, che possono essere definiti come le informazioni elaborate dal programma.
  • Stato, che può essere definito come l'informazione condivisa dal programma.

A questo punto, vorrei dire che,

  • La F-algebra è lo studio delle trasformazioni funzionali che agiscono sull'universo dei dati (come è stato definito qui).
  • F-co-algebre è lo studio delle trasformazioni funzionali che agiscono sull'Universo di Stato (come è stato definito qui).

Durante la vita di un programma, dati e stato coesistono e si completano a vicenda.
Sono duali.



Utilizzate il nostro motore di ricerca

Ricerca
Generic filters

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.