performance - Haskell 的 `seq` 冗余地评估参数？

Question

这个问题在这里已经有了答案:





What is the monomorphism restriction?

(1 个回答)


4年前关闭。




如果我理解讨论 here正确，seq不应将一个值计算两次，如 x `seq` x应该评估 x一次。

那我为什么会有这种行为？

λ> :set +s
λ> let fib x = if x <= 1 then x else fib (x - 1) + fib (x - 2)
(0.01 secs, 102,600 bytes)
λ> fib 30
832040
(2.49 secs, 638,088,448 bytes)
λ> let x = fib 30 in x
832040
(2.47 secs, 638,088,792 bytes)
λ> let x = fib 30 in x `seq` x
832040
(4.95 secs, 1,276,067,128 bytes)

这显然是双重评估？我是不是误会了什么？

编辑 :正如下面@danidiaz 所问的那样，我也评估了

λ> (\x -> x `seq` x) (fib 30)
832040
(2.51 secs, 638,087,888 bytes)
λ> let x = (fib 30) :: Int in x `seq` x
832040
(2.52 secs, 732,476,640 bytes)

现在更令人惊讶了。

编辑 2:我看到这个问题已被标记为之前询问单态限制的问题的副本。当我遇到这个问题时，我不知道这是由于限制。因此，如果有人发现他/她自己处于我的位置，我想这个问题的答案会有所帮助。

Answer 1

对于这个答案的第一部分，:set -XNoMonomorphismRestriction在 ghci 中。稍后会解释。

天真地，人们会期望在 Haskell let x = 5 in (x + 1,x + 2)总是等价于 (\x -> (x + 1, x + 2)) 5 .但是他们有不同的类型!

let x = 5 in (x + 1,x + 2) :: (Num a, Num b) => (a, b)

(\x -> (x + 1,x + 2)) 5 :: Num b => (b, b)

原因是 Haskell 的一个特性，称为 let-bound polymorphism。 .与 lambda 绑定(bind)标识符不同，标识符绑定(bind)在 let 中。可以在 let 的主体中以不同方式实例化.例如:

ghci> let f = id in (f True, f 'a')
(True,'a')

ghci> (\f -> (f True, f 'a')) id
*** ERROR ***

现在，你没有给你的 fib 一个类型签名。功能，并且推导出的功能类似于

fib :: (Ord a, Num a) => a -> a

这将适用于 Num 的不同实例喜欢 Int , Float ， ETC。

但正因为如此，当你写 x `seq` x , ghci 不能确​​定这两个 x s其实是同一类型的!如果它们可能不同，那么它们就不能被共享。

这就是为什么 (\x -> x `seq` x) (fib 30)确实有分享。因为 x是 lambda-bound，编译器确信这两个事件确实是相同的值。 let x = (fib 30) :: Int in x `seq` x 相同因为我们已经使用显式类型移除了多态性。

还有另一种出路。打开 -XMonomorphismRestriction 扩展增加了类型默认的数量，导致 let表达式比人们预期的更单态。在这种情况下，这也应该足以恢复共享。