Generating double linear sequence in Haskell

Question

Need some comments on making the below code more effective. I'm pretty new to Haskell.

The sequence in generateSeq is generated by the rule that if x is in the sequence then x*2+1 and x*3+1 are also in the sequence.

getNumberAt gets the n'th number in the (sorted) generated sequence.

The code works but somehow I feel that I'm overcomplicating this. Any pointers are appreciated!

    generateSeq :: Int -> [Integer]
    generateSeq x
        | x == 0 = [1]
        | otherwise = sort $ prev++toAppend
                         where prev = generateSeq(x-1)
                               toAppend = [next*2+1,next*3+1]
                               next = head $ drop(x-1) prev

    getNumberAt :: Int -> Integer
    getNumberAt n = nub(generateSeq n)!!n


    -- Test this!
    main =
       print $ getNumberAt 321

Answer 1

Plus points for including top-level signatures (just missing for main). Some style nits - in Haskell it's uncommon to omit spaces between a function and its argument, rather than drop(x-1) it's more common to write drop (x-1). And include spaces after commas in lists.

More importantly, as you probably observed, your method is quite inefficient. Just try to compute its value for 4000 or so. First, you sort the sequence every time. Second, you generate the whole sequence again in each step, just a bit longer.

For the latter, a solution is to memoize the results, so that you compute each such intermediate list only once. This would look something like:

import Data.List

generateSeq :: Int -> [Integer]
generateSeq x
    | x == 0 = [1]
    | otherwise = sort $ prev ++ toAppend
                     where prev = generatedSeqs !! (x - 1)
                           toAppend = [next*2 + 1, next*3 + 1]
                           next = head $ drop (x-1) prev

generatedSeqs :: [[Integer]]
generatedSeqs = map (map head . group . generateSeq) [0..]

getNumberAt :: Int -> Integer
getNumberAt n = (generatedSeqs !! n) !! n

For the former, repeated sorting: Let's consider, how would a human create such sequence. Probably she would keep two lists. One would some part of the sequence, and the other would be candidates yet to be added to the sequence. At each step, the smallest candidate n is appended, and 2*n+1 and 3*n+1 added to the candidates. Translating this into code yields

import Data.Set

a002977_list :: [Integer]
a002977_list = loop $ singleton 1
  where
    loop set = x : loop (set' <> fromList [2*x + 1, 3*x + 1])
      where
        (x, set') = deleteFindMin set

The argument to the helper function is a Set of candidates, which provides an efficient way for picking the smallest element.

You probably wonder why I named the function a002977_list. The sequence is of course a known one and is described, together with code samples how to generate it (the above code is adapted from there), at OESIS.

But I strongly encourage you to try to improve your solution first, before looking there.

Answer 2

Repeatedly sorting is asympotically slower than keeping a sorted data structure, nub takes quadratic time, head . drop (x-1) = (!!x), and try to use library-defined recursion combinators instead of explicitly using recursion.

import qualified Data.Set as S

generateSeq :: [Integer]
generateSeq = unfoldr (fmap foo . S.minView) $ singleton 1 where
  foo :: (Integer, S.Set Integer) -> (Integer, S.Set Integer)
  foo (x, s) = (x, S.insert (2*x+1) $ S.insert (3*x+1) s)

looks up comonad stuff on a hunch

import qualified Data.Set as S
import Control.Comonad

generateSeq :: [Integer]
generateSeq = unfoldr ((fmap . extend . uncurry) foo . S.minView) $ singleton 1 where
  foo :: Integer -> S.Set Integer -> S.Set Integer
  foo x = S.insert (2*x+1) . S.insert (3*x+1)