通过重复输入/迭代来定义列表

Question

我想定义 Thue-Morse Sequence (或 fair-sharing sequence )根据初始元素 0 和根据整个列表定义列表的下一部分的规则，直到此时。即

fair 0 = [0]
--fair 1 = [0,1]
--fair 2 = [0,1,1,0]
--fair 3 = [0,1,1,0,1,0,0,1]
fair n = fair (n - 1) ++ map (1-) (fair (n - 1))

这可以很好地生成任何预定义长度的列表，但如果我需要预定义的数量，则不能立即定义整个列表并使用 take 似乎无效。

我第一次尝试定义整个列表是 fair = 0 : map (1-) fair 但当然，这会随着列表的进行而填充列表，所以它永远(不需要) 重新输入列表(并返回 [0,1,0,1,0,1...])。我想要的是一些定义列表的方法，以便当它到达列表中尚未定义的元素时，它通过重新进入列表来定义下一个“ block ”仅直到那一点，(而不是在生成新值时进行计算)，因此计算列表的步骤类似于以下过程:

• 从初始列表开始，[0]
• 将 (1-) 映射到现有列表上，生成 [1]
• 将其附加到现有列表，生成 [0,1]
• 将 (1-) 映射到现有列表上，生成 [1,0]
• 将其附加到现有列表，生成 [0,1,1,0]
• 将 (1-) 映射到现有列表上，生成 [1,0,0,1]
• 将其附加到现有列表，生成 [0,1,1,0,1,0,0,1]

Wikipedia article我上面链接有一个helpful gif来说明这个过程。

我想您可以看到，随着需要新元素，这种情况会无限期地持续下去。但是，我终其一生都找不到一种方法来在递归函数中成功地对其进行编码。

我试过了

reenter f xs = reenter f (xs ++ map f xs)
fair = reenter (1-) [0]

但是虽然逻辑看起来是正确的，但它挂起而没有产生任何结果，这可能是由于立即递归调用(尽管我认为 haskell 的惰性评估可能会解决这个问题，尽管这是一个相当复杂的情况)。

Answer 1

正如您所指出的，您不能立即进行递归调用 - 您首先需要返回下一个结果，然后像上次尝试一样递归调用:

Prelude> reenter prev_list = inverted_prev_list ++ reenter (prev_list ++ inverted_prev_list) where inverted_prev_list = map (1-) prev_list
Prelude> f = [0] ++ reenter [0]
Prelude> take 20 f
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1]