[Haskell-beginners] Named (custom) recursions vs clever comonadic
recursions
Federico Brubacher
fbrubacher at gmail.com
Sat Sep 13 17:57:31 EDT 2008
Hey all, Today I had a small exchange with another reddit user about CT and
why is important to Haskell programming...
What I don't get yet (as the subject says) is a real-world example on where
you might apply cathegory theory to a recursion. Here is the small thread :
fbru02:
Sorry for maybe the OT posting but I have a question of my own:
While learning Haskell and being a curious procrastinator I started learning
Category theory but although I get , I don't get it yet.
What I want to ask is practical uses of cathegory theory ? I know that it is
used for high availability systems for theoretical proof that a System has
the correct side effects. Also I know there are in reality recursions that
might need this stuff as they are not as simple as what one would write in a
toy project. What are this recursion schemes ?? What other uses there are
for CT?
nbloomf:
Disclaimer- I am only beginning to understand this stuff myself. I am also a
mathematician, not a computer scientist or a professional programmer.
Two papers that give a good overview of what categories can do are
"Functional Programming with Bananas, Lenses, etc." and "Recursion Schemes
from Comonads".
My understanding of the role of categories in FP (at least partly) is as
follows. Arbitrary recursion is very useful to writers of programs. However,
like arbitrary GOTOs, it can make it hard to see what's "really" happening
in a program. A long time ago people figured out that fold/reduce was a
common recursive pattern, but it was generally only used on lists and
couldn't express all the recursion people wanted to do. More recently it was
discovered that if your language is strongly typed, you can think of the
types as objects in a category. Then some type constructors become
endofunctors, and the traditional fold can be expressed as a particular map,
parameterized by the functor, having a nice universal property. Moreover, as
the "Recursion schemes from comonads" paper discusses, by parameterizing on
the comonad the fold operator can become several different recursion
schemes. This means a much smaller amount of code can express a larger
number of ideas- even ideas that haven't been had yet. Moreover, it makes
optimizations (such as fold fusion) much more powerful.
So the real power of category theory is as a metalanguage- these ideas might
never have become "obvious" without the language of functors, algebras,
initial objects, and such.
fbru02 :
thank you for great response. Have you yourself used this parametraizing of
the comonad? In which context or solving which problem and why couldn't you
solving easily making a normal named recursion :D
Thanks a lot ! :D
Thanks !
--
Federico Brubacher
www.fbrubacher.com
Colonial Duty Free Shop
www.colonial.com.uy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20080913/1d5d2063/attachment.htm
More information about the Beginners
mailing list