MonadFix instance for []

Question

The instance is defined as

instance MonadFix [] where
  mfix f = case fix (f . head) of
             []    -> []
             (x:_) -> x : mfix (tail . f)

But I'm failing to grasp the intuitive meaning behind it with respect to the [] monad seen as non-deterministic computations. In mfix f function f must not be strict in its argument, so it can't examine the argument. And according to the definition it also can't use the argument anywhere in its output, otherwise at some point it'll hit fix (f . head) and diverge. So is there any use (or good example) for mfix for lists, other than mfix (const someList)?

Answer 1

It's probably easiest to say it like this. The functions f for which mfix f is totally defined are those for which the spine of f x does not depend on x, so they can be written in the form

f x = [f1 x, ..., fn x]

for some n (possibly infinity) and some f1, ..., fn. Then

mfix f = [fix f1, ..., fix fn]

(of course for this to really be totally defined, each fix fi must also be defined).

---

mfix can be thought of as nondeterministically giving you the fixed point of a nondeterministic function. The rather heavy restriction is that the shape of the nondeterministic computation cannot depend in any way on the input. We seem to need some kind of restriction on the computation in order to get started, but you might hope to at least be able to kill off a branch of the computation conditionally (say if some intermediate calculation is negative). I've always thought that it should be possible to use mfix in this way by using a different nondeterminism monad whose choice operation is not associative, but never worked out the details.

Answer 2

All the fix variants have a problem if you actually use them with a strict function, but that's generally not an issue in the real use case^†: a is basically always a function type, and any lambda is already in NF.

So, as for a concrete use... well, here's at least something that converges:

f :: (Int -> Int) -> [Int -> Int]

f f' = [\x -> if x>0 then f' (x-1) * i else 1 | i<-[0..]]

f basically generates a list of power functions.

GHCi> take 20 $ mfix f <*> [1,2] [0,0,1,1,2,4,3,9,4,16,5,25,6,36,7,49,8,64,9,81]

What this is actually useful for I'm not sure, but it does have quite interesting behaviour.

I've just noticed this is a bad example, as it's actually equivalent to a single fix (f . head). Hm...

---

^†_{You seem to be quite right: it is an issue in the case of a -> [a], because there's no obvious way to make the list structure dependent on the argument without getting strict.}