On 7/10/07, Creighton Hogg
Okay Mr. Piponi, as a math geek I can't let that comment about the web slide without further explanation. Is it just the idea that coalgebras can capture the idea of side affects (a -> F a) or is there something more specific that you're thinking of?
First a quick bit of background on algebras. If F is a functor, an F-algebra is an arrow FX->X. For example if we choose FX = 1+X+X^2 (using + to mean disjoint union) then an F-algebra is a function 1+X+X^2->X. The 1->X part just picks out a constant, the image of 1. The X^2->X defines a binary operator and the X->X part is an endomorphism. A group has a constant element (the identity) an endomorphism (the inverse) and a binary operator (multiplication). So a group is an example of an F-algebra (with some extra equations added in so a group isn't *just* an F-coalgebra). A F-coalgebra is an arrow X->FX. As an example, let's pick FX=(String,[X]). So an F-coalgebra is a function X->(String,[X]). We can view this as two functions, 'appearance' of type X->String and 'links' of type X->[X]. If X is the type of web pages, then interpret 'appearance' as the rendering (as plain text) of the web page and links as the function that gives a list of links in the page. So the web forms a coalgebra. (Though you'll need some extra work to deal with persistent state like cookies.) The theme is that mathematicians often like to study objects with some kind of 'combination' operation like (generalised) addition or multiplication. These form algebras with maps FX->X. Computer scientists often like to study things that generate more stuff (eg. when you press a button or input something). So you end up with something of the form X->FX. This includes many familiar things like web pages, state machines and formal languages. This isn't a sharp divide (of course) but I think it reflects a real difference in emphasis. A great source for this stuff is the book 'Vicious Circles' by Barwise and Moss. It's full of computer sciencey stuff but it seems to be written for an audience that includes mathematicians and computer scientists. (It has quite a few typos and more serious errors however.)