Haskell 一行中的 Thue-Morse 序列

Question

我将Thue-Morse 序列的定义写为一行 Haskell 中的无限整数列表：

thueMorse = 0:1:f (tail thueMorse) where f = (\(x:xs) -> x:(1 - x):f xs)

这是尝试在一行中定义序列失败的结果，仅根据 lambda 表达式及其本身，没有 let 或 where 表达式（实际上应该在两行中呈现，使上述解决方案在精神上成为两行） ）。我已经阅读了一些有关 lambda 演算的内容，所以我想我应该尝试将其作为练习。我想知道 Haskell 中是否有可能实现这样的事情，如果可能的话该怎么做。

thueMorse = 0:1:(\f xs -> f f xs) (\f (x:xs) -> x:(1 - x):f f xs) ((\(_:xs) -> xs) thueMorse)

上面的表达式有点难以阅读，所以我将其分解：

(\f xs -> f f xs)

接受一个函数和一个参数，并将该函数应用于自身和参数。Haskell 不会计算这个表达式，因为 f 的类型是t = t -> a -> a，这是我问题的关键。

(\f (x:xs) -> x:(1 - x):f f xs)

是传递给前一个表达式的函数，它将自身和列表作为参数。这是递归计算 Thue-Morse 序列的部分。这也有无限型t = t -> [a] -> [a]。

((\(_:xs) -> xs) thueMorse)

这相当于(tail thueMorse)，但用 lambda 表达式编写以满足练习的条件。

Haskell 抱怨这些表达式具有无限类型并拒绝对它们求值，但我认为如果对它们求值，它们将正确生成 Thue-Morse 序列。有什么方法可以扭转解释器或编译器的手臂来评估这些表达式吗？有没有一种方法可以调整语句，以便可以对其进行求值，但仍然只使用 lambda 演算中的运算符，并且在一行中？

Answer 1

这是相同的算法，但没有显式fix：

thueMorse = 0 : 1 : (tail thueMorse >>= \x -> [x, 1 - x])