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 


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

2 answers

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.



All Articles