递归函数的惰性模式

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

主要问题是您使用了累加器，并且在遍历整个输入列表时仅 return 列表。此外 length l 将遍历整个列表。你不需要计算长度。这也是低效的：如果列表很长，它每次都会生成一个线性运行.

您可以在列表上进行模式匹配，对于空列表 return 空列表，对于 non-empty 列表产生 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 部分一次。我把它留作练习。

Answer 2

您在这里对“累加器”的使用含糊不清。

有用的术语是“状态传递和构建”、“输出列表创建”、“尾递归”和“保护递归”，在严格设置中也称为“尾递归模缺点”。

是的，我们可以通过受保护的递归逐渐创建输出列表，同时安排从一个调用到下一个调用的传递和累积/构建状态：

makeList elt next state = go state
  where
  go state = elt state : go (next state)
  --- which is just
  -- go = map elt . iterate next

("guarded" 递归，由 lazy 数据构造函数保护，此处 :).

具体来说，你的例子是

groupEvery n p  =  makeList (take n) (drop p)

直到终止条件：

> takeWhile (not . null) $ groupEvery 3 2 [1..20]
[[1,2,3],[3,4,5],[5,6,7],[7,8,9],[9,10,11],[11,12,13],
 [13,14,15],[15,16,17],[17,18,19],[19,20]]

递归函数的惰性模式

Lazy mode of recursive function

recursion

haskell

list

lazy-evaluation