patternMinor
Generating all size-k consecutive subsets in Haskell
Viewed 0 times
allsizesubsetsgeneratinghaskellconsecutive
Problem
I am interested in splitting any list into consecutive subsets based on a k-value. For example,
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.
[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 tailSolution
Each evaluation of
We know that there will be
For comparison, with
I get the following timings on my machine, compiled with
Original version:
This version:
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 restFor 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.015sThis version:
$ time ./new
199998
real 0m0.065s
user 0m0.015s
sys 0m0.015sCode Snippets
sublists n xs = take (length xs - n + 1) $ sublists' n xs
where sublists' _ [] = [[]]
sublists' n xs@(_:rest) = take n xs : sublists' n restmain = 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.015sContext
StackExchange Code Review Q#82240, answer score: 2
Revisions (0)
No revisions yet.