How to create a Prouhet–Thue–Morse sequence in Haskell?

I'm a noob in Haskell, but some experience with ActionScript 3.0 Object Orientated. Thus working on a major programming transition. I've read the basic knowledge about Haskel, like arithmetics. And I can write simple functions.

As a practical assignment I have to generate the Thue-Morse sequence called tms1 by co开发者_JAVA百科mputer in Haskell. So it should be like this:

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

and so on... According to wikipedia I should use the formula.

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

I have no idea how I can implement this formula in Haskell. Can you guide me to create one? This is what I got so far:

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

I did some research on the internet and found this code.

Source: http://pastebin.com/Humyf6Kp

Code:

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))

But this code doesn't give the desired result. Any help is well appreciated.

---

I would suggest using a list of booleans for your code; then you don't need to explicitly convert the numbers. I use the sequence defined like this:

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
...

Notice that the leading zeros are quite important!

A recursive definition is now easy:

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

This works because we never access an element that is not yet defined. Printing the list is left as an excercise to the reader.

Here is another definition, using the fact that one can get the next step by replacing 1 with 10 and 0 with 01:

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

Edit

Here are easier definitions by sdcvvc using the function iterate. iterate f x returns a list of repeated applications of f to x, starting with no application:

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

And here are the definitions:

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

---

Your definition of the sequence seems to be as a sequence of bit sequences:

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

but the wikipedia page defines it as a single bit sequence:

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

This is the formulation that the definitions in Wikipedia refer to. With this knowledge, the definition of the recurrence relation that you mentioned is easier to understand:

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

In English, this can be stated as:

• The zeroth bit is zero.
• For an even, non-zero index, the bit is the same as the bit at half the index.
• For an odd index, the bit is 1 minus the bit at half the (index minus one).

The tricky part is going from subscripts 2n and 2n+1 to odd and even, and understanding what n means in each case. Once that is done, it is straightforward to write a function that computes the *n*th bit of the sequence:

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

If you want the whole sequence, map lookupMorse over the non-negative integers:

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

This is the infinite Thue-Morse sequence. To show it, take a few of them, turn them into strings, and concatenate the resulting sequence:

>concatMap show $ take 10 morse
"0110100110"

Finally, if you want to use the "sequence of bit sequences" definition, you need to first drop some bits from the sequence, and then take some. The number to drop is the same as the number to take, except for the zero-index case:

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

This gives rise to the alternative sequence definition:

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

which you can use like this:

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

---

Easy like this:

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))