Search code examples
algorithmhaskellsequencelazy-sequences

Implementing an unusual sequence as an infinite list in Haskell


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.


Solution

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