I'm tasked with implementing a function that returns the Thue-Morse sequence all the way through. I've done it through primitive recursion but now I have to do it with a circular list (using list comprehension), and it'd have to return this when I call take on it:
>take 4 thueSeq
[[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]
Here's my (horrible) attempt at implementation:
> thueSeq = 0: [x | x <- zipWith (mod) (tail thueSeq) [1] ]
I'm aware right off the bat that it's wrong (the head is supposed to be [0], not 0) but writing [0] ++ [0,1] ++ ... didn't return a list of lists anyway.
My question is, first off, how do I "start off" the list with [[0],[0,1]] because from what I've seen with circular lists, they have the base cases and then recurse through. Secondly, my list comprehension is trying to apply (mod x 1) to each value, but that'd also be wrong since [[0,1]] would turn into [[0,1,0]] instead of [[0,1,1,0]]. So I'm thinking I have to apply it on every other element in the list (the 1st element, 3rd, 5th, etc.)?
From what I understand...
I have just written a simple flip function that maps 1 to 0 and 0 to 1
flipBit 1 = 0
flipBit 0 = 1
the function h takes a list and joins that list with the flipped version of the list
h xs = xs ++ (map flipBit xs)
*Main> h [0]
[0,1]
The main function fseq takes a list as an argument. It conses the argument into the recursive call
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 provides the function iterate :: (a -> a) -> a -> [a] that does exactly this.
We can now wrap this as follows:
thue_morse = fseq [0]
or using the function iterate
thue_morse = iterate h [0]
both give the result
*Main> take 4 thue_morse
[[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]
If you wanted to use list comprehensions, you could write something like this:
h xs = xs ++ (map flipBit xs)
thue_morse = [0] : [ h x | x <- thue_morse]