7
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

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

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)
\$\endgroup\$
  • \$\begingroup\$ Comonads are probably a bit overkill for a Haskell beginner... \$\endgroup\$ – Petr Pudlák Nov 20 '16 at 17:33
  • \$\begingroup\$ That's why I left the first version in place. \$\endgroup\$ – Gurkenglas Nov 20 '16 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.