list - 递归函数的惰性模式

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 部分一次。我把它留作练习。