haskell 中的圆形地图

Circular maps in haskell

我的任务是实现一个 return 整个过程都是 Thue-Morse 序列的函数。我已经通过原始递归完成了它,但现在我必须使用循环列表(使用列表理解)来完成它,并且当我调用它时它必须 return 这个:

>take 4 thueSeq
[[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]

这是我的(可怕的)实施尝试:

> thueSeq = 0: [x | x <- zipWith (mod) (tail thueSeq) [1] ]

我马上意识到它是错误的(头部应该是 [0],而不是 0)但是写 [0] ++ [0,1] ++ ... 并没有 return 列表列表.

我的问题是,首先,我如何 "start off" 使用 [[0],[0,1]] 的列表,因为从我看到的循环列表来看,它们有基本情况,然后递归。其次,我的列表理解试图将 (mod x 1) 应用于每个值,但这也是错误的,因为 [[0,1]] 会变成 [[0,1,0]] 而不是 [[0,1,1,0]]。所以我想我必须将它应用于列表中的每个其他元素(第一个元素、第三个、第五个等)?

据我了解...

我刚刚编写了一个简单的翻转函数,将 1 映射到 0,将 0 映射到 1

flipBit 1 = 0
flipBit 0 = 1

函数 h 获取一个列表并将该列表与列表的翻转版本

连接起来
h xs = xs ++ (map flipBit xs)

*Main> h [0]
[0,1]

主函数fseq接受一个列表作为参数。它将参数包含在递归调用中

fseq xs = xs : fseq (h xs)

*Main> take 4 $ fseq [0]
[[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]

Haskell 提供的函数 iterate :: (a -> a) -> a -> [a] 正是这样做的。

我们现在可以将其包装如下:

thue_morse = fseq [0]

或使用函数iterate

thue_morse = iterate h [0]

都给出结果

*Main> take 4 thue_morse
[[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]

如果你想使用列表理解,你可以这样写:

h xs = xs ++ (map flipBit xs)
thue_morse = [0] : [ h x | x <- thue_morse]