[Haskell-cafe] Clearly, Haskell is ill-founded

[Dan Piponi]

On 7/10/07, Creighton Hogg <wchogg at gmail.com> wrote:
> 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.)