CODEWITHSUNDEEP
listhaskellcircular-list
Homerdough
Homerdough

Reputation: 173

Circular maps in haskell

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

Upvotes: 1

Views: 364

Answers (1)

beoliver
beoliver

Reputation: 5759

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]

Upvotes: 6

Related Questions