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

Question

我是Haskell中的菜鸟,但有一些使用ActionScript 3.0面向对象的经验.从而致力于主要的编程转型.我已经阅读了关于Haskel的基本知识,比如算术.我可以编写简单的函数.

作为一个实际的任务,我必须在Haskell中通过计算机生成名为tms1 的Thue-Morse序列.所以它应该是这样的:

>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

我在网上做了一些研究,发现了这段代码.

资料来源: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))

但是这段代码没有给出理想的结果.任何帮助都非常感谢.

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]

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

在英语中,这可以表述为:

• 第零位为零.
• 对于偶数非零索引,该位与索引一半的位相同.
• 对于奇数索引,该位为1减去该位的一半(索引减1).

棘手的部分是从下标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)

如果您想要整个序列,请将lookupMorse映射到非负整数:

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

这是无限的Thue-Morse序列.要显示它,take其中一些,将它们转换为字符串,并连接结果序列:

>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"]