# Generating double linear sequence in Haskell

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  ## 2 Answers 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.

• Nice. What's the <> operator? – rickythefox Nov 24 '16 at 13:12
• Operator <> is a synonym for mappend from Monoid. – Petr Nov 25 '16 at 14:31

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