16 Jun 10:09 2013

## Help me understand general recursion from cata- and anamorphism

Takayuki Muranushi <muranushi <at> gmail.com>

2013-06-16 08:09:22 GMT

2013-06-16 08:09:22 GMT

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

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

Takayuki MURANUSHI

The Hakubi Center for Advanced Research, Kyoto University

http://www.hakubi.kyoto-u.ac.jp/02_mem/h22/muranushi.html

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at> haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe