Why does haskell's `fix` seem to have trouble with tuples?

Question

I'm trying to bend my head around fixed points and recursive definitions.

This works:

>>> take 10 $ let x = (0:x) in x
[0,0,0,0,0,0,0,0,0,0]

This does the same thing, which makes sense given the definition of fix:

>>> take 10 $ fix (\x -> (0:x))
[0,0,0,0,0,0,0,0,0,0]

Now suppose I start messing around with recursively defined pairs:

>>> take 10 $ fst $ let (u,v) = (0:v,1:u) in (u,v)
[0,1,0,1,0,1,0,1,0,1]

Okay, I should be able to write that with fix too, right?

>>> take 10 $ fst $ fix (\(u,v) -> (0:v,1:u))
*** Exception: <<loop>>

But it doesn't work. Unless I make the following seemingly trivial change:

>>> take 10 $ fst $ fix (\r -> let (u,v)=r in (0:v,1:u))
[0,1,0,1,0,1,0,1,0,1]

What's the critical difference between the last two examples?

Midstream

Answer 1

You want

take 10 $ fst $ fix (\ ~(u,v) -> (0:v,1:u))
                      ^^^

so as to make the pattern matching lazy. In let, the LHS pattern is implicitly lazy/irrefutable.

With the plain \(u,v) -> ... the argument of the lambda will be demanded before any output is produced -- this makes the function too strict for fix. What you need is something like

take 10 $ fst $ fix (\p -> (0:snd p,1:fst p))

so that the argument is not forced by the lambda (there's no constructor there to match). The lazy pattern approach is equivalent to the fst/snd above.

Malvasia

That should be \(~(u,v)) or \ ~(u,v) – Finnie

@Finnie Fixed. (pun intended :-P) – Malvasia