Exercise idea: Golomb sequence

[Average-user]

Golomb sequence

See: OEIS page of Golomb Sequence for more information.

I like the idea of the Golomb sequence as an exercise. There are many possible implementations like the recursive definition:

g :: Int -> Int  
g 1 = 1
g n = 1 + g (n - g (g (n-1)))

or using the self-descriptive characteristics of the sequence:

golomb :: Int -> Int
golomb n = sucGolomb !! (n-1)

sucGolomb :: [Int]
sucGolomb = 1 : 2 : 2 : f 3
    where f x = (replicate (golomb x) x) ++ (f (x+1))

but non of them it's really close of being efficient. So this might be good as an example of how and when to use recursive functions.

import Prelude hiding (replicate, length, drop)
import Data.Sequence ((><), index, replicate, fromList, length, drop)

golomb :: Int -> Int
golomb n = fn (fromList [1, 2, 2]) 3 2
  where fn gl x t = if n <= length gl
                      then gl `index` (pred n)
                      else let n_gl = (><) gl (replicate t x)
                             in fn n_gl (succ x) (n_gl `index` x)

And there are probably a lot of better (faster and cleaner) implementations out there. But this one at least implicates to try an alternative to lists.

[Insti]

It sounds like you might be prefer to work through the project euler problems?

[Average-user]

Maybe, but why do you think that this might not fit here?

[Average-user]

I saw that problem in another place (not project euler) and a lot of people were debating their ideas. And at least on Haskell, i think that it's a good exercise to try alternatives to lists, cause there are very useful really often.