Type f should be a Functor if you want to use
simple recursion schemes or Traversable if you want to
use monadic recursion schemes. This style allows you to express
recursive functions in non-recursive manner.
You can imagine that a non-recursive function
holds values of the previous iteration.
An example:
First we define a base functor. The arguments b are recursion points.
Example1 expression
>>> data ListF a b = Nil | Cons a b deriving (Show, Functor)
The list is then a fixed point of ListF
Example1 expression
>>> type List a = Fix (ListF a)
We can write length function. Note that the function we give
to foldFix is not recursive. Instead the results
of recursive calls are in b positions, and we need to deal
only with one layer of the structure.
Example1 expression
>>> :{let length :: List a -> Int length = foldFix $ \x -> case x of Nil -> 0 Cons _ n -> n + 1:}
If you already have recursive type, like '[Int]',
you can first convert it to `Fix (ListF a)` and then foldFix.
Alternatively you can use recursion-schemes combinators
which work directly on recursive types.
>>> let x = unfoldMu (\i -> if i < 3 then Cons i (i + 1) else Nil) (0 :: Int)>>> unwrapMu xCons 0 (unfoldMu unFix (Fix (Cons 1 (Fix (Cons 2 (Fix Nil))))))
>>> let x = unfoldNu (\i -> if i < 3 then Cons i (i + 1) else Nil) (0 :: Int)>>> unwrapNu xCons 0 (unfoldNu unFix (Fix (Cons 1 (Fix (Cons 2 (Fix Nil))))))
Refolding
1 declaration
vvaluerefold :: Functorf => (fb -> b) -> (a -> fa) -> a -> b