Implementing an unusual sequence as an infinite list in Haskell

Question

I have two elements as the beginning of the list [1, 2]

This unusual sequence is that it replicates the digits in the number of digits of a certain type that follows the three elements. For example, after 1 and 2, we would have another 2, followed by two 1's. The first few elements of the desired list would yield

[1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2] because

1  2   2  1 1   2  1  2   2  1   2   2

where the previous digits represent the length of the mini-sequences of the same digit.

So far I've tried using the replicate function for repeating the same digit based on an element earlier in the list.

selfrle :: [Int]
selfrle = 1 : 2 : [x | a <- [0..], let x = replicate (selfrle !! a) (selfrle !! (a + 1))) ]

The problem is I can't figure out why it's not working.

Answer 1

The accepted answer seems concise and very efficient but hard to reason with especially if you are a beginner and neglect Haskell's laziness.

We can rephrase it like

a = 1:2:2: (concat . zipWith replicate (drop 2 a) . cycle) [1, 2]

We must remember that a is just a semi constructed list like 1:2:2:?: ... ?:[] and we start using it just by discarding the first two items (drop 2 a) which leaves us with 2:?: ... ?:[] to apply to zipWith replicate and this is sufficient for us to run our logic indefinitelly. Keep in mind 2:?: ... ?:[] is a list to be calculated just like cycle [1,2]. The availability of the initial item 2 enables the next item to be calculated and then the next item and then the next and so forth.

This is a beautiful pattern in Haskell to generate infinite lists if you know the initial items. Take for instance the fibonacci series

fib = 1:1: (zipWith (+) fib (tail fib))

All you need to do is to tweak your mindset to think like fib is already there but not yet calculated.

Another Approach with State Monad:

However, i believe that the given Kolakoski series could also be a good case study to learn the State monad. Let's see if we can get the same performance..?

import Control.Monad.Trans.State

invert :: Int -> Int
invert = (+1) . (`mod` 2)

rle :: Int -> State Int [Int]
rle n = state $ \s -> (replicate n s, invert s)

kolakoski :: [Int] -> Int -> [Int]
kolakoski ps s = ps ++ kolakoski xs i
                 where (xs,i) = runState (mapM rle ps >>= pure . concat) s

• We have an invert function when fed with 1 gives 2 and when fed with 2 gives 1.
• rle takes an Int type and returns a State type, a function which takes the state and replicates it by n and returns the replicated list along with a new state, invert s. So our state alternates like 1,2,1,2... along the way.

However when tested with ghci (:set +s), while both show linear time complexity, this takes 10 times longer to finalize. Anybody care to comment..?

Answer 2

We can write this slightly more elegant than @DanD's answer, by using an extra variable b on which we "tie a knot":

a :: [Int]
a = 1 : 2 : b
    where b = 2 : concat (zipWith replicate b (cycle [1, 2]))

We here thus first yield 1 : 2 : b, with b that starts with 2 and then the concatenation of the replicates of b with an endless list with [1, 2, 1, 2, …].

Answer 3

Not that unusual as it appears in the OEIS at https://oeis.org/A000002 and is named there as the Kolakoski sequence. There they even give a Haskell program by John Tromp dated 2011:

a = 1:2: drop 2 (concat . zipWith replicate a . cycle $ [1, 2])

Answer 4

The first thing you can do it get your types right. replicate builds a list, so the x in your list comprehension has the type [Int], and the entire list comprehension is a list of all the x values, and its type is [[Int]]. You cannot use a list of lists of Int as the tail of a list, when the first two elements are 1 and 2. The types just don't match: you need to decide whether this is a list of Int, or a list of lists of Int.

Based on your description, I suspect you want to fix this by flattening the list comprehension using concat, like so:

selfrie = 1 : 2 : concat [x | a <- [0..],
                              let x = replicate (selfrie !! a) (selfrie !! (a + 1))]

If you try this, you won't get the list you described. I don't know how to help with the next part, and that's because I don't understand your description of the desired list. This isn't a programming question so much as a specification question, so perhaps you could go back to the original source and see how it's explained there?