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

[Takayuki Muranushi]

Dear all,

https://github.com/nushio3/practice/blob/master/recursion-schemes/FibTest.hs

After learning fix-point operators, I found an answer by myself.

```

fibBase :: (Integer -> Integer) -> Integer -> Integer
fibBase fib n
  | n <= 1    = 1
  | otherwise = fib (n-1) + fib (n-2)

fibWithFix :: Integer -> Integer
fibWithFix = fix fibBase
```

I can say `fibBase` is free of recursion, despite the facts that apparently
it uses a name `fib` on RHS which it binds on the LHS, and that the entire
structure seems very similar to the recursive version of `fib` .



2013/6/16 Takayuki Muranushi <muranushi at gmail.com>

> 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
>



-- 
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/20130623/0c640a53/attachment.htm>