Subsequences of length n on list performance

Question

I have implemented a version of this answer https://stackoverflow.com/a/212677/212612 (I do not know what was intended by the user responding)

sublistofsize 0 _        = [[]]
sublistofsize _ []       = []
sublistofsize n (x : xs) = sublistsThatStartWithX ++ sublistsThatDontStartWithX
  where sublistsThatStartWithX = map (x:) $ sublistofsize (n-1) xs
        sublistsThatDontStartWithX = sublistofsize n xs

I'm not sure what it is sublistsThatStartWithX = map (x:) $ sublistofsize (n-1) xs

I assume that the mapping (x :) gives an idea of ​​performance, but does not know how to solve it. I did profiling onprint $ length $ sublistofsize 5 $ primesToTakeFrom 50

COST CENTRE                                  MODULE                                        no.     entries  %time %alloc   %time %alloc
sublistofsize                             Main                                          112     4739871   46.9   39.9    96.9  100.0
 sublistofsize.sublistsThatDontStartWithX Main                                          124     2369935    2.2    0.0     2.2    0.0
 sublistofsize.sublistsThatStartWithX     Main                                          116     2369935   47.8   60.1    47.8   60.1

Have I implemented this in a good way? Are there any faster ways to do this?

Answer 1

I assume the mapping (x :) gives the task performance wise

No. mapencoded efficiently and runs in linear mode, there is no problem.

. sublistofsize (n-1) xs sublistofsize n xs, - sublistofsize m (_:_:ys) - sublistofsize (m-1) ys, .

,

subsequencesOfSize :: Int -> [a] -> [[a]]
subsequencesOfSize n xs = let l = length xs
                          in if n>l then [] else subsequencesBySize xs !! (l-n)
 where
   subsequencesBySize [] = [[[]]]
   subsequencesBySize (x:xs) = let next = subsequencesBySize xs
                             in zipWith (++) ([]:next) (map (map (x:)) next ++ [[]])

, , , zipWith , next - n n + 1.

GHCI :set +s, , , :

*Main> length $ subsequencesOfSize 7 [1..25]
480700
(0.25 secs, 74132648 bytes)
(0.28 secs, 73524928 bytes)
(0.30 secs, 73529004 bytes)
*Main> length $ sublistofsize 7 [1..25] -- @Vixen (question)
480700
(3.03 secs, 470779436 bytes)
(3.35 secs, 470602932 bytes)
(3.14 secs, 470747656 bytes)
*Main> length $ sublistofsize' 7 [1..25] -- @Ganesh
480700
(2.00 secs, 193610388 bytes)
(2.00 secs, 193681472 bytes)
*Main> length $ subseq 7 [1..25] -- @user5402
480700
(3.07 secs, 485941092 bytes)
(3.07 secs, 486279608 bytes)

Answer 2

"Haskell-ish" .

, , ([[a]]), , .

map (x:) - , - , , .

, (++) , , .

, otherResults , prefix , :

sublistofsize' 0 _        prefix otherResults = reverse prefix : otherResults
sublistofsize' _ []       prefix otherResults = otherResults
sublistofsize' n (x : xs) prefix otherResults =
   sublistofsize' (n-1) xs (x:prefix) (sublistofsize' n xs prefix otherResults)

sublistofsize n xs = sublistofsize' n xs [] []

Answer 3

, , , , , . , , n-1 - xs, , .

:

  nthtail 0 xs = xs
  nthtail _ [] = []
  nthtail n (x:xs) = nthtail (n-1) xs

  subseq 0 _ = [[]]
  subseq n xs =
    if null t
      then []
      else go n xs t
    where
      t = nthtail (n-1) xs  -- n should always be >= 1 here
      go 0 _ _  =  [[]]
      go _ _ [] = []
      go n xs@(x:xt) t = withx ++ withoutx
        where withx = map (x:) $ go (n-1) xt t
              withoutx = go n xt (tail t)