[Haskell-cafe] Help me understand general recursion from cata- and anamorphism

Takayuki Muranushi muranushi at gmail.com
Sun Jun 16 10:09:22 CEST 2013


In an attempt to understand why cata- and anamorphisms are considered so
important, I found multiple implications that you can write any recursive
functions in terms of nonrecursive functions and ana, cata (am I right
here?) so I'm trying to practice the rewrite by a few functions. I'm
following a recipe found here:

http://lambda-the-ultimate.org/node/4290

~~~
Given a function that recurses on itself, do a partial CPS transform so
that it only ever recurses on itself with tail calls. Then, convert the
recursive calls to codata returns, so that the function either returns
TheAnswer or StillWorking with enough parameters to describe the recursive
call / continuation state. This codata can be built with an unfold and can
be collapsed back down to the final answer with a fold.
~~~


https://github.com/nushio3/practice/blob/master/lens/banana/CollatzTest.hs
https://github.com/nushio3/practice/blob/master/lens/banana/FibTest.hs

I find it difficult to understand the terminology, and the above attempts
are only halfway done. I guess ( TheAnswer or StillWorking ) structure is
the one found in iteratee/enumeratee. But I don't know how to "build a
codata with unfold."

I'd appreciate any advice.

Best,

-- 
Takayuki MURANUSHI
The Hakubi Center for Advanced Research, Kyoto University
http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130616/3ed65b38/attachment.htm>


More information about the Haskell-Cafe mailing list