Interleave function

Question

I found this code that builds a list corresponding to the Thue-Morse sequence:

thueMorse :: [Int]
thueMorse = 0 : interleave (map (1-) thueMorse) (tail thueMorse)
    where interleave (x:xs) ys = x : interleave ys xs

It's perfect and works wonders, but I cannot wrap my head around it. An example:

> take 8 thueMorse 
[0,1,1,0,1,0,0,1]

If I define the interleave function globally and use it I get, and rightly so, 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 the above work? Is it because it's an infinite list so it's safe to interleave forever?

Carl · Accepted Answer · 2014-09-10 18:21:18Z

7

Yes, it works because the input is a pair of infinite lists. That definition of interleave only handles the case where its first argument is not empty, ie uses the : constructor. But lists have a second constructor ([]) which that definition ignores is possible. A more complete definition would probably look like this, depending on how you want it to handle an empty input:

interleave (x:xs) ys = x : interleave ys xs
interleave [] ys = ys

answered Sep 10, 2014 at 18:21

Carl

27.2k4 gold badges67 silver badges88 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Zeta · Accepted Answer · 2014-09-10 18:20:32Z

3

The exception already tells your error: your pattern for interleave isn't exhaustive. What happens if you try to use interleave [] a? The pattern for the first argument only matches lists with at least one element. That way, interleave is only defined partially, that is, not for all possible lists.

answered Sep 10, 2014 at 18:20

Zeta

107k13 gold badges207 silver badges250 bronze badges

Collectives™ on Stack Overflow

Interleave function

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related