在Haskell中是否有一个内置函数可以获取列表的所有连续子序列（大小为n）？

Question

例如，我需要一个函数：

gather :: Int -> [a] -> [[a]]
gather n list = ???

其中 gather 3 "Hello!" == ["Hel","ell","llo","ol!"]。

我有一个可用的实现：

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)

但我想知道语言本身是否已经有相关的功能？我查看了Data.List，但没有找到相关内容。

- iobender

Answer 1

你可以使用tails：

gather n l = filter ((== n) . length) $ map (take n) $ tails l

或者使用takeWhile代替filter:

gather n l = takeWhile ((== n) . length) $ map (take n) $ tails l

编辑：根据评论中的建议，您可以通过删除从tails返回的列表的最后n个元素来跳过过滤步骤：

EDIT: 您可以按评论中的建议，通过删除从tails返回的列表的最后n个元素来跳过过滤步骤：

gather n = map (take n) . dropLast n . tails
  where dropLast n xs = zipWith const xs (drop n xs)

- Lee

---

我会使用 takeWhile 而不是 filter，但这只是一个相当温和的优化。 - Carl

这个看起来在语义上是正确的，但操作起来有些粗糙：检查每个子列表的长度似乎太麻烦了。有一个常见的技巧可以说“取一个列表中除了最后n个元素之外的所有元素”，即\xs -> zipWith const xs (drop n xs); 也许你可以在这里使用这个技巧。 - Daniel Wagner

@DanielWagner - 感谢您的建议，这样更加简洁。 - Lee

Answer 2

使用“压缩”属性，尾部的删除可以自动完成。

import Data.List (tails)

g :: Int -> [a] -> [[a]]
g n = foldr (zipWith (:)) (repeat []) . take n . tails

否则，一个简单的transpose . take n . tails就足够了。测试：

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

---

(编辑于2018-09-16:)使用traverse ZipList可以以更高级的方式表达zip的用法：

g :: Int -> [a] -> [[a]]
g n = getZipList . traverse ZipList . take n . tails

- Will Ness

---

我喜欢这两个的原因是它们都可以处理字符串和整数列表。虽然调用参数可能需要改进，但这并不重要。我的函数可以处理整数，但如果没有额外的逻辑，就无法处理字符串。使用“zipWith enumFromTo [1..no] [sz..]”可以生成一个包含3个四元素列表的列表。 - fp_mora

重点在于重新排列给定的列表，而不是重新创建它。zipWith enumFromTo 创建了模仿结果的整数列表，但如果我们必须重新排列 sort ([1,4..20] ++ [1,5..30]) 的结果呢？重新排列忽略了元素的性质，只是操纵列表结构，而不管它包含什么。就像列表是一系列盒子（每个盒子中都装有某些元素），我们正在处理盒子，而不是其中的内容。（这些盒子实际上并没有保存值，而是保存指向这些值的指针 - 每个盒子保存一个指针）。 - Will Ness

这就是在 Haskell 中所说的“参数性”，当我们说“[a]”是一个“参数化”的类型，一个“'something'”列表，无论那个“something”是什么 - 这个“something”就是类型 [] a 即 [a] 中的参数 a。因此，当我们重新排列一个列表时，我们创建了新的“列表结构”，即新的盒子链，保存着原始盒子中相同值的新指针。就像 Lisp 中一样。 - Will Ness

在Lisp中，可以使用set-car!或set-cdr!更改盒子的指针。但在Haskell中不行。但从概念上讲，这种模型防止了在重新排列时值的过度复制，如果我们说我们有实际包含值的盒子（新链将保存其盒子中的值的副本），则无法避免。当然，在Haskell中，由于其引用透明性，除了性能效果（内存大小、速度、垃圾收集量等）之外，无法区分复制的值和指向相同值的新指针（使用普通的Haskell值）。 - Will Ness

[#t,#t,#t] Racket 放弃了 set-car 等操作。正如您所说，这违反了引用透明性和不可变性。我现在看到列表是必需的参数。递归函数使用 tail、take 和 length。我喜欢以下代码比我的上一个递归函数更好，它可以处理任何列表或字符串。非常感谢您的帮助…… g2 sz ls= [take sz t|t<- tails ls,length t>=sz] - fp_mora