Useful instantiations of “fix” on non-function types?

Question

Every time I’ve used fix :: (a -> a) -> a, it’s been at the type

((a -> b) -> a -> b) -> a -> b

for some a and b. Is there actually some application of fix where its type parameter is not instantiated to a function type, other than a trivial thing like fix (const 0)? What is the purpose of leaving the signature at its most general?

Wines

"What is the purpose of leaving the signature at its most general?" You lose nothing by doing so. – Exploratory

Answer 1

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

Cleary

The factorial numbers are simply fix ((1:) . zipWith (*) [1..]). – Caerleon

Answer 2

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

Strati

Answer 3

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

Caerleon

I really like these examples, although I feel that the second one is cheating somewhat because State is essentially a synonym for s -> (a, s) and so the input fed to fix has type ((b -> c) -> b -> c) where b = (Int, Int) and c = ((Int,Int), [Int]). – Cleary

@Chris Taylor, that's fair. However one of the questions is "What is the purpose of leaving the signature at its most general?", and this example is the illustration. – Caerleon

@ChrisTaylor: right. Then again, any type can be read as "essentially a synonym for" such a function type, namely its untyped-lambda-calculus representation. – Polariscope