Function to get NGrams fast in Haskell

Question

Is this a good way to get all sublists of a sequence/list that have a given length?

An inefficient way to do it would be something like

f n = (filter (\x -> (length x) > n)) . (take n) . tails

This just takes the n first elements of each tail of the original list. I think it should be slow because of the length check on every tail-element.

A smarter way would should be to "slide" a sequence of length n over an input sequence and save the result of each slide by one to the right.

-- | Get all the subsequences of a given sequence sq of length n
ngrams::Int -> Seq a -> Seq (Seq a)
ngrams n sq | length sq < n = empty
ngrams n sq | otherwise = ngrams' restSequence initialWindow empty
 where
 initialWindow = take n sq
 restSequence = drop n sq
 ngrams' (viewl -> EmptyL) window acc = acc |> window
 ngrams' (viewl -> x :< s) window@(viewl -> a :< r) acc = 
 ngrams' s (r |> x) (acc |> window)

Somehow I have the feeling I am missing an obvious way to do this better...

Answer 1

A little math goes a long way.

ngrams :: Int -> [a] -> [[a]]
ngrams n l = take (length l - (n - 1)) . map (take n) . tails $ l

• Christof Schramm: Thanks for your reply. I guess this is still not optimal because it won't work on an infinite list. I guess that each call to take also takes n operations for each tail, right ?
• bisserlis: Re: infinite lists, neither would your Seq version. Re: take, yes but no, remember that it will be evaluated lazily, so you'll only compute the elements of take n as you use them, it won't walk the spine of the ngram twice.
• Tashi Walde: I think it is better to replace take (length) l - (n-1) by zipWith (flip const) (drop (n-1) l). This increases lazyness and makes the function work for infinite lists.