[Haskell-cafe] Help me understand general recursion from cata- and anamorphism
muranushi at gmail.com
Sun Jun 23 11:06:39 CEST 2013
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:
> 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.
> 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.
> Takayuki MURANUSHI
> The Hakubi Center for Advanced Research, Kyoto University
The Hakubi Center for Advanced Research, Kyoto University
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe