为什么这样评估？

Question

我有这个功能

doubleMe :: Num a => [a] -> [a]
doubleMe [] = []
doubleMe (x:xs) = (2*x):(doubleMe xs)

考虑一下:

doubleMe(doubleMe([1,2,3]))

显然,第一步是

doubleMe(doubleMe([1,2,3])) = doubleMe(2:doubleMe[2,3])

因为没有其他可能性.

这是我想知道的下一步.究竟是为什么

doubleMe(2:doubleMe[2,3]) = 4:(doubleMe(doubleMe([2,3])))

代替

doubleMe(2:doubleMe[2,3]) = doubleMe(2:4:doubleMe([3]))

？

到目前为止我唯一能够提出的答案是

因为它有道理.否则Haskell不会在列表上懒散地行事.

但这不是一个答案,而是一个问题.真正的答案是什么？

Answer 1

显然,第一步是 doubleMe(doubleMe([1,2,3])) = doubleMe(2:doubleMe[2,3])

其实不是很明显!

为了区分,

doubleMe' = doubleMe

并考虑

doubleMe' $ doubleMe [1,2,3]

正如你所说,第一步的唯一原因,即

? doubleMe' $ 2 : doubleMe [2,3]

是因为doubleMe'需要能够以它的参数匹配要么[]或_:_.为此,运行时开始计算doubleMe [1,2,3]一点,即一个递归步骤.产量2 : doubleMe [2,3]足以满足doubleMe':

? 4 : doubleMe' (doubleMe [2,3])

请注意,实际上该语言不需要此评估顺序:允许编译器对其进行重新排序(例如,出于性能原因),因此实际上内部列表会立即完全处理 - 如果它可以证明这不会改变语义,即对于一个无限的列表,doubleMe [1..]如果你只要求前几个结果,就不能陷入永恒的循环中.

GHC不进行此类重新排序.