Struttura algebrica e programmazione

Question

Qualcuno potrebbe darmi un esempio su come possiamo migliorare la riusabilità del codice utilizzando strutture algebriche come gruppi, monoidi e anelli? (o come posso usare questo tipo di strutture in programmazione, sapendo almeno che non ho imparato tutta quella teoria in High School per niente).

Ho sentito dire che è possibile, ma non riesco a capire come applicarli nella programmazione e applicare genericamente matematica hardcore nella programmazione.

Answer 1

Non è proprio la cosa matematica che aiuta come il pensiero matematico. L'astrazione è la chiave nella programmazione. Trasformare i veri concetti dal vivo in numeri e relazioni è ciò che facciamo ogni giorno. L'algebra è la madre di tutto, l'algebra è l'insieme di regole che definisce la correttezza, è il livello più alto di astrazione, quindi, comprendere l'algebra significa che puoi pensare in modo più chiaro, più veloce, più efficiente. Partendo dalla teoria degli insiemi alla teoria delle categorie, alla teoria dei domini ecc. Tutto deriva da sfide pratiche, astrazione e requisiti di generalizzazione. Nella pratica comune non avrete bisogno di conoscerli realmente, anche se state pensando di sviluppare cose come agenti di IA, linguaggi di programmazione, concetti e strumenti fondamentali, allora sono un must.

Answer 2

Come ho avuto alcuna idea di questa roba esisteva nel mondo informatico, si prega di ignorare questa risposta;)

---

non credo che i due campi (no pun intended) hanno alcuna sovrapposizione. Gli anelli/campi/gruppi si occupano degli oggetti matematici. Si consideri una parte della definizione di un campo:

Per ogni a in F, esiste un elemento -a in F, tale che a + (-a) = 0. Analogamente, per ogni a in F altra di 0, esiste un elemento a^-1 in F, tale che a · a^-1 = 1. (Gli elementi a + (-b) e a · b^-1 sono anche denotati a - b e a/b, rispettivamente.) In altre parole, esistono operazioni di sottrazione e divisione.

Che diamine vuol dire in termini di programmazione? Non posso sicuramente avere un inverso additivo di un oggetto list in Python (beh, potrei semplicemente distruggere l'oggetto, ma è come l'inverso moltiplicativo . Immagino che potresti ottenere da qualche parte il tentativo di definire un anello Python, ma alla fine non funzionerà). Non fanno così anche pensare di dividere lists ...

Per quanto riguarda la leggibilità del codice, non ho assolutamente idea di come questo può anche essere applicato, in modo da questa applicazione è irrilevante.

Questa è la mia interpretazione, ma essere un esperto di matematica probabilmente mi rende cieco rispetto ad altre terminologie da diversi campi (sai di quale sto parlando).

Answer 3

Nella programmazione funzionale, esp. Haskell, è comune strutturare programmi che trasformano gli stati come monadi. Ciò significa che è possibile riutilizzare algoritmi generici su monadi in programmi molto diversi.

La libreria di modelli standard C++ presenta il concetto di monoid. L'idea è ancora una volta che gli algoritmi generici possono richiedere un'operazione per soddisfare gli assiomi dei monoidi per la loro correttezza.

Es., Se siamo in grado di dimostrare il tipo T su cui stiamo operando (numeri, stringa, qualsiasi cosa) è chiuso sotto l'operazione, sappiamo che non dovremo controllare determinati errori; otteniamo sempre T valido indietro. Se possiamo dimostrare che l'operazione è associativa (x * (y * z) = (x * y) * z), possiamo riutilizzare l'architettura fork-join; un modo semplice ma di programmazione parallela implementato in varie librerie.

Answer 4

In questi giorni l'informatica sembra avere un sacco di soldi da category theory. Ottieni monadi, monoidi, funtori - un intero bestiario di entità matematiche che vengono utilizzate per migliorare la riusabilità del codice, sfruttando l'astrazione della matematica astratta.

Answer 5

Le liste sono monoidi liberi con un generatore, gli alberi binari sono gruppi. Hai la variante finita o infinita.

Punti di partenza:

• http://en.wikipedia.org/wiki/Algebraic_data_type
• http://en.wikipedia.org/wiki/Initial_algebra
• http://en.wikipedia.org/wiki/F-algebra

Si consiglia di imparare teoria di categoria, e la teoria categoria Way si propone strutture algebriche: è esattamente il modo in cui i linguaggi di programmazione funzionale si avvicinano alle strutture dati, per lo meno shapewise.

Esempio: il tipo dell'albero A è

Tree A =() | Tree A | Tree A * Tree A 

quale stabilisce l'esistenza di un isomorfismo (*) (ho impostato G = Tree A)

1 + G + G x G -> G 

che è la stessa come una struttura di gruppo

Infatti, gli alberi binari possono rappresentare espressioni e formano una struttura algebrica Ure. Un elemento di G legge sia l'identità, l'inverso di un elemento o il prodotto di due elementi. Un albero binario è una foglia, un singolo albero o un paio di alberi. Si noti la somiglianza nella forma.

(*) così come una proprietà universale, ma sono due di loro (alberi finiti o alberi pigri infiniti) quindi non voglio dwelve in dettaglio.

Answer 6

I monoidi sono onnipresenti nella programmazione. In alcuni linguaggi di programmazione, ad es. Haskell, possiamo rendere espliciti i monoidi http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html