haskell - Interleave function -

i found code builds list corresponding thue-morse sequence:

thuemorse :: [int] thuemorse = 0 : interleave (map (1-) thuemorse) (tail thuemorse)     interleave (x:xs) ys = x : interleave ys xs 

it's perfect , works wonders, cannot wrap head around it. example:

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

if define interleave function globally , use get, , rightly so, 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 above work? because it's infinite list it's safe interleave forever?

yes, works because input pair of infinite lists. definition of interleave handles case first argument not empty, ie uses : constructor. lists have second constructor ([]) definition ignores possible. more complete definition this, depending on how want handle empty input:

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