Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there a built-in function to get all consecutive subsequences of size n of a list in Haskell?

Tags:

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.

like image 839
iobender Avatar asked Jul 06 '14 20:07

iobender


2 Answers

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)
like image 110
Lee Avatar answered Sep 27 '22 01:09

Lee


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
like image 43
Will Ness Avatar answered Sep 26 '22 01:09

Will Ness