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?
source to share
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
source to share
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.
source to share