函数快速获取Haskell中的NGrams

Question

这是获取具有给定长度的序列/列表的所有子列表的好方法吗？

一种效率低下的方法是这样的

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

这只是获取原始列表的每个尾部的n第一个元素。我认为应该慢一点，因为每个尾元素都有长度检查。

一种更明智的方法应该是将长度的n序列“滑动”在输入序列上，并将每一张幻灯片的结果保存到右边。

-- | 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)

不知怎么我觉得我错过了一个更好的方法.

Answer 1

一个小小的数学能起很大的作用。

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