递归函数的惰性模式

Question

我将找到解决这个问题的方法：

将给定列表拆分为具有给定子列表长度和跳过长度的子列表，例如：

groupEvery 3 1 [1..6] = [[1,2,3], [2,3,4], [3,4,5], [4,5,6]]
groupEvery 3 2 "abcdefghij" = [ "abc", "cde", "efg", "ghi", "ij"]

参数groupEvery n p l详细信息是：

• n 是子列表的长度：Int
• f 是跳过的长度：Int
• xs 是输入列表：[a]

这是我的解决方案：

groupEvery :: Int -> Int -> [a] -> [[a]] -> [[a]]
groupEvery n p xs acc
    | length xs <= n = acc ++ [xs]
    | otherwise = groupEvery n p dropped (acc++[segment])
        where
            dropped = drop p xs
            segment = take n xs

但这个解决方案并不懒惰，例如take 3 Lib2.groupEvery 3 1 [1..] []从未完成。我的问题是关于

• 该groupEvery功能有更好的解决方案吗？
• 我们如何编写累积一些数据的递归惰性函数？换句话说，这种递归函数是否有任何结构可以累积结果并且是惰性的？

Answer 1

主要问题是您使用累加器并且仅在遍历整个输入列表时才返回列表。此外，length l还将浏览整个列表。您不需要计算长度。这也是低效的：如果列表很长，它每次都会进行线性运行。

您可以在列表上进行模式匹配，对于空列表返回一个空列表，对于非空列表产生take n xs并使用 递归drop p xs。

groupEvery :: Int -> Int -> [a] -> [[a]]
groupEvery _ _ [] = []
groupEvery n p xs = take n xs : groupEvery n p (drop p xs)

由此产生：

ghci> take 3 (groupEvery 3 1 [1..])
[[1,2,3],[2,3,4],[3,4,5]]

take n您可以通过组合和来进一步改进该功能drop p，这样您只需遍历min n p列表的各个部分一次。我把它留作练习。