如何在Haskell中创建Prouhet-Thue-Morse序列？

Question

我是Haskell的新手，但有一些ActionScript 3.0面向对象的经验。因此正在进行一次重大的编程转变。我已经阅读了关于Haskel的基础知识，例如算术。我可以编写简单函数。

作为一个实际的任务，我需要在Haskell中使用计算机生成Thue-Morse sequence（称为tms1）。应该像这样：

>tms1 0
0
>tms1 1
1
>tms1 2
10
>tms1 3
1001
>tms1 4
10010110

等等……根据维基百科，我应该使用公式。

t0 = 0
t2n = tn
t2n + 1 = 1 − tn

我不知道如何在Haskell中实现这个公式。你能指导我创建一个吗？ 这是我目前得到的：

module ThueMorse where
tms1 :: Int -> Int
tms1 0 = 0
tms1 1 = 1
tms1 2 = 10
tms1 3 = 1001
tms1 x = tms1 ((x-1)) --if x = 4 the output will be 1001, i don't know how to make this in a recursion function

我在互联网上做了一些研究，找到了这段代码。

Source: http://pastebin.com/Humyf6Kp

代码：

module ThueMorse where
tms1 :: [Int]
tms1 = buildtms1 [0] 1
    where buildtms1 x n 
        |(n `rem` 2 == 0) = buildtms1 (x++[(x !! (n `div` 2))]) (n+1)
        |(n `rem` 2 == 1) = buildtms1 (x++[1- (x !! ((n-1) `div` 2))]) (n+1)

custinv []  = []
custinv x   = (1-head x):(custinv (tail x))

tms3 :: [Int]
tms3 = buildtms3 [0] 1
    where buildtms3 x n = buildtms3 (x++(custinv x)) (n*2)

intToBinary :: Int -> [Bool]
intToBinary n   | (n==0) = []
                | (n `rem` 2 ==0) = intToBinary (n `div` 2) ++ [False]
                | (n `rem` 2 ==1) = intToBinary (n `div` 2) ++ [True]

amountTrue :: [Bool] -> Int
amountTrue [] = 0
amountTrue (x:xs)   | (x==True) = 1+amountTrue(xs)
                    | (x==False) = amountTrue(xs)

tms4 :: [Int]
tms4= buildtms4 0
    where buildtms4 n
        |(amountTrue (intToBinary n) `rem` 2 ==0) = 0:(buildtms4 (n+1))
        |(amountTrue (intToBinary n) `rem` 2 ==1) = 1:(buildtms4 (n+1))

但是这段代码并没有得到期望的结果。非常感谢任何帮助。

- user962775

---

问题似乎在于您丢弃了前导零。使用列表而不是数字也可以避免您反复转换数字。我总是认为：如果我用大量代码解决一个微不足道的问题，那么我一定做错了什么。 - fuz

你可以将 a \rem` 2 == 0/1写成even a和odd a。custinv x可以定义为map (\a -> 1-a) x，甚至可以简化为 custinv = map (1-)。amountTrue x = sum (fromEnum x)或者amountTrue x = length (filter id x)`。 - sdcvvc

Answer 1

我建议在你的代码中使用一个布尔列表；这样你就不需要显式地转换数字。我使用如下定义的序列：

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
...

请注意，前导零非常重要！

现在可以很容易地给出递归定义：

morse = [False] : map step morse where step a = a ++ map not a

这段代码之所以能够正常运行，是因为我们从未访问尚未定义的元素。打印列表由读者自行练习。

以下是另一个定义，利用了可以通过将1替换为10，将0替换为01来获得下一步的事实：

morse = [False] : map (concatMap step) morse where step x = [x,not x]

编辑

以下是由sdcvvc使用iterate函数提供的更简单的定义。 iterate f x返回一个重复应用f到x的列表，从没有应用开始：

iterate f x = [x,f x,f (f x),f (f (f x)),...]

以下是定义：

morse = iterate (\a -> a ++ map not a) [False]
morse = iterate (>>= \x -> [x,not x]) [False]

- fuz

---

使用 iterate：第一定义：morse = iterate (\a -> a ++ map not a) [False]，第二定义：morse = iterate (>>= \x -> [x,not x]) [False]。 - sdcvvc

Answer 2

您对序列的定义似乎是一系列位序列的序列：

0  1  10 1001 10010110 ... etc.
t0 t1 t2 t3   t4

但维基百科页面将其定义为单个比特序列：

0  1  1  0  1  ... etc
t0 t1 t2 t3 t4

这是维基百科中定义所涉及的表达式。有了这个知识，你提到的递归关系的定义就更容易理解了：

t0 = 0
t2n = tn
t2n + 1 = 1 − tn

这可以用中文表述为：

• 第零位是零。
• 对于偶数非零下标，该位与一半下标处的值相同。
• 对于奇数下标，该位等于一减去在 (下标减一的一半处) 的值。

从下标的 2n 和 2n+1 转换为奇数和偶数，并理解每种情况下 n 的含义，是比较棘手的。完成这一步后，编写一个计算序列第 n 位的函数就很简单了。

lookupMorse :: Int -> Int
lookupMorse 0 = 0;
lookupMorse n | even n    =     lookupMorse (div  n    2)
              | otherwise = 1 - lookupMorse (div (n-1) 2)

如果你想要整个序列，可以将 Morse 码的查找映射应用于非负整数：

morse :: [Int]
morse = map lookupMorse [0..]

这是无限的Thue-Morse序列。为了展示它，取其中几个，将它们转换成字符串，然后连接得到结果序列：

>concatMap show $ take 10 morse
"0110100110"

最后，如果您想使用“比特序列的顺序”定义，则需要首先从序列中删除一些比特，然后再取一些。要删除的数字与要取的数字相同，除了零索引的情况：

lookupMorseAlternate :: Int -> [Int]
lookupMorseAlternate 0 = take 1 morse
lookupMorseAlternate n = take len $ drop len morse
    where
        len = 2 ^ (n-1)

这导致了另一种序列定义：

morseAlternate :: [[Int]]
morseAlternate = map lookupMorseAlternate [0..]

你可以像这样使用它：

>concatMap show $ lookupMorseAlternate 4
"10010110"
>map (concatMap show) $ take 5 morseAlternate
["0", "1", "10", "1001", "10010110"]

- Boris

Answer 3

就像这样简单：

invertList :: [Integer] -> [Integer]
invertList [] = []
invertList (h:t) 
    |h == 1 = 0:invertList t
    |h == 0 = 1:invertList t
    |otherwise = error "Wrong Parameters: Should be 0 or 1"

thueMorse :: Integer -> [Integer]
thueMorse 1 = [0]
thueMorse n = thueMorse (n - 1) ++ invertList (thueMorse (n - 1))

- Cesar

---

我认为这里的所有结果都偏移了一步。如果你将thueMorse 1 = [0]更改为thueMorse 0 = [0]，那么它就可以正常工作了。 - rickerbh