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.