Haskell的懒惰如何运作？

Question

考虑这个将列表中所有元素加倍的函数:

doubleMe [] = []
doubleMe (x:xs) = (2*x):(doubleMe xs)

然后考虑表达式

doubleMe (doubleMe [a,b,c])

很明显,在运行时,这首先扩展为:

doubleMe ( (2*a):(doubleMe [b,c]) )

(很明显,因为据我所知,没有其他可能性存在).

但我的问题是:为什么现在这个扩展到了

2*(2*a) : doubleMe( doubleMe [b,c] )

代替

doubleMe( (2*a):( (2*b) : doubleMe [c] ) )

？

直觉上,我知道答案:因为Haskell很懒惰.但有人可以给我一个更准确的答案吗？

是否有一些特殊的关于导致这种情况的列表,或者这个想法比仅仅列表更通用？

Answer 1

doubleMe (doubleMe [a,b,c])不扩展到doubleMe ( (2*a):(doubleMe [b,c]) ).它扩展到:

case doubleMe [a,b,c] of
  [] -> []
  (x:xs) -> (2*x):(doubleMe xs)

这是外部函数调用首先扩展.这是惰性语言和严格语言之间的主要区别:扩展函数调用时,不首先评估参数 - 而是将函数调用替换为其主体,并将参数保留为现在.

现在doubleMe需要扩展,因为模式匹配需要知道其操作数的结构才能进行评估,因此我们得到:

case (2*a):(doubleMe [b,c]) of
  [] -> []
  (x:xs) -> (2*x):(doubleMe xs)

现在模式匹配可以用第二个分支的主体替换,因为我们现在知道第二个分支是匹配的分支.因此,我们替换(2*a)为x与doubleMe [b, c]对xs,给我们:

(2*(2*a)):(doubleMe (doubleMe [b,c]))

这就是我们如何得出结果.

Answer 2

你的"显而易见的"第一步实际上并不那么明显.实际上发生的事情是这样的:

doubleMe (...)
doubleMe ( { [] | (_:_) }? )
doubleMe ( doubleMe (...)! )

并且只有在那一点它才真正"进入"内部功能.所以它继续下去

doubleMe ( doubleMe (...) )
doubleMe ( doubleMe( { [] | (_:_) }? ) )
doubleMe ( doubleMe( a:_ ! ) )
doubleMe ( (2*a) : doubleMe(_) )
doubleMe ( (2*a):_ ! )

现在这里外部doubleMe函数对它的[] | (_:_)问题有"回答" ,这是内部函数中任何东西都被评估的唯一原因.

实际上,下一步也不一定是你的意思:它取决于你如何评估外部结果!例如,如果整个表达式是tail $ doubleMe ( doubleMe [a,b,c] ),那么它实际上会扩展得更像

tail( { [] | (_:_) }? )
tail( doubleMe(...)! )
tail( doubleMe ( { [] | (_:_) }? ) )
...
tail( doubleMe ( doubleMe( a:_ ! ) ) )
tail( doubleMe ( _:_ ) )
tail( _ : doubleMe ( _ ) )
doubleMe ( ... )

即它实际上永远不会真正到达2*a!

Answer 3

其他人已经回答了一般性问题.让我在这一点上添加一些内容:

是否有一些特殊的关于导致这种情况的列表,或者这个想法比仅仅列表更通用？

不,名单并不特别.dataHaskell中的每个类型都有一个懒惰的语义.让我们尝试使用整数对的类型的简单示例(Int, Int).

let pair :: (Int,Int)
    pair = (1, fst pair)
 in snd pair

上面fst,snd是成对投影,返回一对的第一/第二组成部分.还要注意,这pair是一个递归定义的对.是的,在Haskell中,您可以递归地定义所有内容,而不仅仅是函数.

在惰性语义下,上面的表达式粗略地评估如下:

snd pair
= -- definition of pair
snd (1, fst pair)
= -- application of snd
fst pair
= -- definition of pair
fst (1, fst pair)
= -- application of fst
1

相比之下,使用急切的语义,我们会像这样评估它:

snd pair
= -- definition of pair
snd (1, fst pair)
= -- must evaluate arguments before application, expand pair again
snd (1, fst (1, fst pair))
= -- must evaluate arguments
snd (1, fst (1, fst (1, fst pair)))
= -- must evaluate arguments
...

在热切的评估中,我们坚持在应用之前评估参数fst/snd,并且我们获得了无限循环的程序.在某些语言中,这将触发"堆栈溢出"错误.

在惰性求值中,即使参数未得到充分评估,我们也会很快应用函数.这使得立即snd (1, infiniteLoop)返回1.

因此,懒惰评估不是特定于列表.Haskell中任何东西都是懒惰的:树,函数,元组,记录,用户定义的data类型等.

(Nitpick:如果程序员真的要求它们,就可以定义具有严格/热切评估组件的类型.这可以使用严格注释或使用扩展类型等扩展来完成.虽然有时它们有用途,但它们'在Haskell程序中不常见.)