haskell - 交错功能

Question

我发现这段代码构建了一个与 Thue-Morse sequence 相对应的列表:

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

它很完美并且能创造奇迹，但我无法理解它。一个例子:

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

如果我全局定义 interleave 函数并使用它，我会得到一个异常:

> 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

那么，上面的内容是如何工作的呢？是因为它是一个无限列表所以可以安全地永远交错吗？

Answer 1

是的，它有效，因为输入是一对无限列表。 interleave 的定义仅处理其第一个参数不为空的情况，即使用 : 构造函数。但是列表有第二个构造函数([])，该定义可能会忽略它。更完整的定义可能如下所示，具体取决于您希望它如何处理空输入:

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