Useful instantiations of “fix” on non-function types?
Fibonacci sequence, for example:
fibs = fix ((1:) . (1:) . (zipWith (+) <*> tail))
Or the forever
function:
forever x = fix (x >>)
Or another variant of fibonacci sequence:
fibs :: State (Int, Int) [Int]
fibs = fix $ \loop -> do
(x, y) <- get
put (y, y + x)
(x :) <$> loop
main = print $ take 15 $ fst $ runState fibs (1, 1)
prints [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]
.
I don't know if you would regard this example as trivial, but you can use fix
directly (without going through a function) to build up data:
repeat :: a -> [a]
repeat x = fix (x:)
There are many examples of building corecursive data with fix
. I don't know enough to elaborate on the general theory, but it seems as though any data type that is like a stream, in that you can always output one more value given the stream so far, can be computed with fix
without feeding it a function type.
Examples
The simplest example (given in Cactus's answer) is a repeating stream of values, for example
x = [1, 1, 1, 1, 1, 1, 1, 1, ...]
This satisfies the equation
(1:) x = x
and can be produced by
>> fix (1:)
[1,1,1,1,1,1,1,1,1,1,...]
A slightly more complicated example is the natural numbers
n = [0, 1, 2, 3, 4, 5, 6, ...]
which satisfy the equation
0 : map (+1) n = n
and can be produced by
>> fix ((0:) . map (+1))
[0,1,2,3,4,5,6,7,8,9,...]
The factorial numbers can be generated most easily if we look at the pair (n,f)
where f
is the n
th factorial number -
x = [(0,1), (1,1), (2,2), (3,6), (4,24), (5,120), ...]
which are fixed if we take the pair (n,f)
to (n+1, f*(n+1))
and then cons (0,1)
to the start of the list. So they can be generated by
>> fix $ \xs -> (0,1) : map (\(n,f) -> (n+1,f*(n+1))) xs
[(0,1),(1,1),(2,2),(3,6),(4,24),(5,120),(6,720),(7,5040),...]
The fibonacci numbers can be generated similarly, as in user3237465's answer.
Generalizing the examples
All three examples here are essentially recursive functions transformed into corecursive streams, i.e. they have some initial state s
and the values emitted by the stream are s
, f s
, f (f s)
etc for some function f
. The general method for doing this is the function iterate
iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)
which can be defined in terms of fix
-
iterate f x = x : map f (iterate f x)
= (x:) . (map f) $ iterate f x
= fix ((x:) . map f)
So any stream which repeatedly applies a function to some state can be written in terms of fix
(though, of course, you could simply use iterate
instead of fix
-- a particular case of the rule that fix
is not necessary in a language which allows recursive let expressions).
Non-stream examples
For an example that isn't a stream, consider binary trees with values at the branches -
data Tree a = Tip | Bin a (Tree a) (Tree a) deriving (Show)
If we want a binary tree whose nodes are labelled in breadth first order, note that we could fix such a tree by taking two copies of itself, and incrementing all of the values in the left- and right-branches by the appropriate amount, as defined by the following function -
fun :: (Num a) => Tree a -> Tree a
fun t = Bin 1 (incr 1 t) (incr 2 t)
where
incr n (Bin a l r) = Bin (a+n) (incr m l) (incr m r)
where
m = 2 * n
Using a simple function takeLevels
to display just the initial portion of the tree, we then compute the fixed point as
>> takeLevels 3 $ fix fun
Bin 1 (Bin 2 (Bin 4 Tip Tip) (Bin 5 Tip Tip)) (Bin 3 (Bin 6 Tip Tip) (Bin 7 Tip Tip))
which is what we wanted.