haskell

Question

例如

partitions [1,2,3] =
  [([],[1,2,3])
  ,([1],[2,3])
  ,([1,2],[3])
  ,([1,2,3],[])]

partitions :: [a] -> [([a], [a])]
partitions (x:xs) = ([], x:xs):[(x:ys, rs) | (ys, rs) <- partitions xs]

不知道是不是偷懒的解决办法。例如 partitions [1..] 是无限的。此外，take 5 $ partitions [1..] 也是无限的。考虑到这个函数的结果是无限的，我认为这是显而易见的。但是，我不确定是不是懒惰，如果我正确理解懒惰的话。

Answer 1

有不同程度的懒惰。

有人可能会说你的函数是严格的，因为 partitions undefined 触发了一个异常，但那太迂腐了。

很可能 "lazy" 你实际上是指 "it will produce a part the output after having accessed only a part of the input"。然后会出现几个程度的惰性，具体取决于输出的每个部分需要多少输入。

在你的例子中，函数的形状如下：

foo [] = (some constant value)
foo (x:xs) = C expression1 ... expressionN

其中 C 是一个值构造函数。更准确地说，C = (:) 和 N=2。由于 Haskell 构造函数是惰性的（除非涉及 bang 注释），因此 foo (x:xs) 的结果将始终是非底部的：消耗输入列表中的一个元素足以产生输出列表中的一个元素。

您可能会对 partitions [1..] 的输出感到困惑，因为它是一对 (xs, ys) 的无限列表，其中每个 ys 都是一个无限列表。这使得懒惰的概念变得更加复杂，因为你现在可能会想知道，例如 "how much input is accessed for me to take the 100th pair of the output, and then access the 500th element of its second component?"。这样的问题是完全合理的，一般来说很难回答。

不过，您的代码永远不会要求完整的输入列表来输出输出的有限部分。这使得 "lazy".

为了完整起见，让我展示一个非惰性函数：

partitions (x:xs) = case partitions xs of
   []     -> expression0
   (y:ys) -> expression1 : expression2

以上，要求递归调用的结果在产生输出列表的头部之前。在生成输出的任何部分之前，这将需要整个输入。

haskell - 是我的分区很懒吗？

haskell - is it my partitions lazy?

lazy-evaluation