Interleaving function
I found this code that builds a list matching the Thue-Morse sequence :
thueMorse :: [Int]
thueMorse = 0 : interleave (map (1-) thueMorse) (tail thueMorse)
where interleave (x:xs) ys = x : interleave ys xs
It is perfect and works wonders, but I cannot wrap it around. Example:
> take 8 thueMorse
[0,1,1,0,1,0,0,1]
If I define a function interleave
globally and use it, I get and, rightly, an exception:
> let interleave (x:xs) ys = x : interleave ys xs
> interleave [1,2,3] [4,5,6]
[1,4,2,5,3,6*** Exception: <interactive>:29:5-47: Non-exhaustive patterns in function interleave
So how does it work? Is it because it's an endless list so it can alternate seamlessly?
Yes, it works because the input is a pair of infinite lists. This definition interleave
only handles the case when its first argument is not empty, i.e. Uses the constructor :
. But lists have a second constructor ( []
) that ignores this definition. A more complete definition would probably look like this, depending on how you want it to handle empty input:
interleave (x:xs) ys = x : interleave ys xs
interleave [] ys = ys
The exception already indicates your mistake: your template for is interleave
not comprehensive. What happens if you try to use interleave [] a
? The pattern for the first argument only matches lists with at least one element. Thus, it is interleave
determined only partially , that is, not for all possible lists.