Is there a built-in function to get all consecutive subsequences of size n of a list in Haskell?
For example, I need a function:
gather :: Int -> [a] -> [[a]]
gather n list = ???
where gather 3 "Hello!" == ["Hel","ell","llo","ol!"]
.
I have a working implementation:
gather :: Int-> [a] -> [[a]]
gather n list =
unfoldr
(\x ->
if fst x + n > length (snd x) then
Nothing
else
Just
(take
n
(drop
(fst x)
(snd x)),
(fst x + 1, snd x)))
(0, list)
but I am wondering if there is something already built into the language for this? I scanned Data.List but didn't see anything.
Solution 1:
You could use tails
:
gather n l = filter ((== n) . length) $ map (take n) $ tails l
or using takeWhile
instead of filter
:
gather n l = takeWhile ((== n) . length) $ map (take n) $ tails l
EDIT: You can remove the filter step by dropping the last n
elements of the list returned from tails
as suggested in the comments:
gather n = map (take n) . dropLast n . tails
where dropLast n xs = zipWith const xs (drop n xs)
Solution 2:
The dropping of tails can be arranged for automagically, thanks to the properties of zipping,
import Data.List (tails)
g :: Int -> [a] -> [[a]]
g n = foldr (zipWith (:)) (repeat []) . take n . tails
or else a simple transpose . take n . tails
would suffice. Testing:
Prelude Data.List> g 3 [1..10]
[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9,10]]
Prelude Data.List> transpose . take 3 . tails $ [1..10]
[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9,10],[9,10],[10]]
(edit 2018-09-16:) The use of zipping can be expressed on a higher level, with traverse ZipList
:
g :: Int -> [a] -> [[a]]
g n = getZipList . traverse ZipList . take n . tails