Fixed points of a functor.
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.
>>> data ListF a b = Nil | Cons a b deriving (Show, Functor)
The list is then a fixed point of
ListF
>>> 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.
>>> :{
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.