例如
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..]也是无限的.鉴于此函数的结果是无限的,我认为这很明显.但是,如果我正确地理解懒惰,我不确定它是否是懒惰的.
有不同程度的懒惰.
有人可能会说你的函数是严格的,因为partitions undefined触发了一个例外,但那太迂腐了.
可能是"懒惰"你实际上意味着"它只会在访问输入的一部分后产生输出的一部分".然后出现几度懒惰,这取决于输出的每个部分需要多少输入.
在您的情况下,函数的形状如下:
foo [] = (some constant value)
foo (x:xs) = C expression1 ... expressionN
where C值是一个值构造函数.更确切地说,C = (:)和N=2.由于Haskell构造函数是惰性的(除非涉及爆炸注释),因此结果foo (x:xs)将始终为非底部:在输入列表中使用元素足以生成输出列表的元素.
您可能会对partitions [1..]作为无限列表对的输出感到困惑,(xs, ys)其中每个对ys都是无限列表.这使得懒惰的概念变得更加复杂,因为您现在可能想知道,例如"我输入了多少输入来获取第100对输出,然后访问其第二个组件的第500个元素？".这些问题是完全合法的,一般来说很难回答.
但是,您的代码永远不会要求完整的输入列表输出有限的输出部分.这使它"懒惰".
为了完整起见,让我展示一个非懒惰的功能:
partitions (x:xs) = case partitions xs of
[] -> expression0
(y:ys) -> expression1 : expression2
在上面,在产生输出列表的头部之前需要递归调用的结果.这将在生成输出的任何部分之前要求整个输入.