[Haskell-cafe] Master's thesis topic sought

[Edward Kmett]

I'm to blame for that page. I made the various 'greco'-morphisms from
constructive algorithmics into independently combinable features in
category-extras, and page spun out of a joke on the #haskell channel from
people making fun of the ever more complicated recursion schemes I was
supporting. It is a fairly useless technical term for a recursion scheme
that no one in their right mind would use, but 'zygo-' 'histomorphic' and
'prepromorphism' all have real meanings.

Each of these features can be composed. They are also fairly painfully
abstract.

A catamorphism is just a generalization of 'unfoldr' to arbitrary algebraic
data types.

A generalized catamorphism is a catamorphism that uses a distributive law
for some comonad.

A zygomorphism introduces mutual recursion with a helper function. It is
just a generalized catamorphism using the reader/product comonad. However,
in category-extras I defined 'comonad transformers', including a
reader/product comonad transformer, so you can modify more complicated
recursion schemes by adding 'zygo'.

A histomorphism gives access to 'results obtained so far', and a
prepromorphism is a modified catamorphism that also applies a natural
transformation each time it recurses. This can be done by utilizing the fact
that there is a "cofree comonad" for any functor f, which has a natural
distributive law over f. So a histomorphism is just another generalized
catamorphism.

A prepromorphism is a slightly different animal, it applies a natural
transformation each time it recurses. This lets you build up recursive
operations like 'iterate' in a more formal manner. I generalized
prepromorphisms, the way that you can generalize catamorphisms, allowing
them to be parameterized on an arbitrary comonad. This means that all of the
machinery you can use to parameterize your catamorphisms, can now be
exploited to parameterize prepromorphism.

Since you can apply the comonad transformer for reader to the cofree comonad
of your base functor you can make a zygohistomorphic prepromorphism.

The nice thing is that you can readily dualize each of these notions and
start talking about the equivalent way to build UP a structure.

One might argue that for consistency the name should be a
zygohistoprepromorphism, but that starts to become unwieldy.

The downside is that few people have read all of the papers to know what
each of those terms mean in isolation, let alone when rolled into the same
recursion scheme, so I wouldn't recommend using one in production
maintainable code. =)

-Edward Kmett

On Thu, Nov 5, 2009 at 5:31 PM, Deniz Dogan <deniz.a.m.dogan at gmail.com>wrote:

> 2009/11/5 Andrew Coppin <andrewcoppin at btinternet.com>:
> > Matus Tejiscak wrote:
> >>
> >> zygohistomorphic prepromorphisms
> >
> > Please tell me this isn't a real technical term. o_O
>
> http://www.haskell.org/haskellwiki/Zygohistomorphic_prepromorphisms
>
> Still can't tell if it's a joke or not...
>
> --
> Deniz Dogan
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091106/634f6dbc/attachment.html