HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Generating all size-k consecutive subsets in Haskell

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
allsizesubsetsgeneratinghaskellconsecutive

Problem

I am interested in splitting any list into consecutive subsets based on a k-value. For example, [1,2,3,4,5] splits into [[1,2],[2,3],[3,4],[4,5]] when k=2. If k is bigger than the entire list, then an empty list will be returned.

I am unhappy with my current solution and would like to have suggestions on how to improve it. Specifically I would like to be able to code a more terse solution. I find that terseness in functional programming languages, such as Haskell, is important to keep in mind. I feel that there is a way of expressing my Haskell solution using a fold possibly, but I just cannot see how at this moment.

consSizeK :: Int -> [a] -> [[a]]
consSizeK _ [] = []
consSizeK k list@(_:tail)
    | k > length list = []
    | otherwise = (take k list) : consSizeK k tail

Solution

Each evaluation of length list will take time proportional to the length of the list, which will slow this down.

We know that there will be length xs - n + 1 sublists of xs of length n. We can use this to make the code much faster.

sublists n xs = take (length xs - n + 1) $ sublists' n xs
    where sublists' _ [] = [[]]
          sublists' n xs@(_:rest) = take n xs : sublists' n rest


For comparison, with

main = print $ sum $ map length $ sublists 2 [1 .. 100000]


I get the following timings on my machine, compiled with -O.

Original version:

$ time ./orig
199998

real    0m14.890s
user    0m0.015s
sys     0m0.015s


This version:

$ time ./new
199998

real    0m0.065s
user    0m0.015s
sys     0m0.015s

Code Snippets

sublists n xs = take (length xs - n + 1) $ sublists' n xs
    where sublists' _ [] = [[]]
          sublists' n xs@(_:rest) = take n xs : sublists' n rest
main = print $ sum $ map length $ sublists 2 [1 .. 100000]
$ time ./orig
199998

real    0m14.890s
user    0m0.015s
sys     0m0.015s
$ time ./new
199998

real    0m0.065s
user    0m0.015s
sys     0m0.015s

Context

StackExchange Code Review Q#82240, answer score: 2

Revisions (0)

No revisions yet.