search

prathyvsh / morphisms-of-computational-structures

A visual catalogue + story of morphisms displayed across computational structures.
https://patternatlas.com/
119 stars 5 forks source link

Find out how the categorical duality between expressions and continuations can be grounded using initial and final algebras and co-algebras #3

Open prathyvsh opened 3 years ago

prathyvsh commented 3 years ago

Lectures on Semantics: The initial algebra and final coalgebra perspectives Peter Aczel (1997)

A Tutorial on (Co)Algebras and (Co)Induction: https://fldit-www.cs.tu-dortmund.de/~peter/JR.pdf Bart Jacobs, Jan Rutten (1997)

prathyvsh commented 3 years ago

Screen Shot 2020-09-15 at 10 41 45 PM Screen Shot 2020-09-15 at 10 41 55 PM

Function Programming with apomorphisms (Co-Recursion): http://cs.ioc.ee/~tarmo/papers/nwpt97-peas.pdf

prathyvsh commented 3 years ago

Alexandra Silva seems to be doing some great work vis à vis Coalgebra: https://alexandrasilva.org/#/talks.html

prathyvsh commented 3 years ago

An idiosyncratic definition of Coalgebras by Paul Blain Levy: https://www.cs.bham.ac.uk/~pbl/coalglect.pdf

prathyvsh commented 3 years ago

Interleaving data and effects: https://bentnib.org/interleaving.html

prathyvsh commented 3 years ago

This looks like an accessible work to understand structural corecursion and codata which uses examples in Agda and Scheme: https://arxiv.org/pdf/2103.06913v1.pdf

prathyvsh commented 3 years ago

Understanding the difference between data vs. codata

https://github.com/idris-lang/Idris-dev/wiki/Copatterns https://web.archive.org/web/20201209020710/http://www.tac-tics.net/blog/data-vs-codata http://www.jucs.org/jucs_10_7/total_functional_programming/jucs_10_07_0751_0768_turner.pdf http://blog.sigfpe.com/2007/07/data-and-codata.html https://www.cs.uoregon.edu/Reports/MS-201806-Sullivan.pdf

prathyvsh commented 2 years ago

An interesting thing to be noted here is how the algebraic structures (monoid, semigroups) etc. have free/forgetful variants. And how different laws on them such as associativity / commutativity etc. gives them certain guarantees. For example, the free monoid means that in the presence of just unit elements and associativity, there is a canonical representation for them. For example, on lists, the ++ is the operator for free monoid with the unit []. But Last is also a monoid, but since it doesn’t preserve the structure, it is not considered as the free version, so with + and * on natural numbers, there too, the concatenation operation is I think considered as the monoid. TODO: Is there a theorem that there will be one and only one free monoid?

Now an interesting thing to observe is that with associativity, both foldLeft and foldRight on monoids will collapse into a single structure. This is one interesting place where associativity’s nature of providing for multiple decomposition of a problem to one confluent representation shines through.