haskell中严格版本的含义是什么？

Question

关注<Real World Haskell>,据说 foldl'是严格的版本foldl.

但是我很难理解,这strict意味着什么？

foldl f z0 xs0 = lgo z0 xs0
         where
            lgo z []     =  z
            lgo z (x:xs) = lgo (f z x) xs


foldl' f z0 xs0 = lgo z0 xs0
    where lgo z []     = z
          lgo z (x:xs) = let z' = f z x in z' `seq` lgo z' xs

Answer 1

它并不广为人知,但foldl'在其累加器论证中实际上并不严格!回想一下类型:

foldl' :: (a -> b -> a) -> a -> [b] -> a

它在参数2中的严格性取决于为参数1给出的函数的严格性,如你所看到的那样const:

Prelude Data.List> foldl' (const (+1)) undefined [1]
2
Prelude Data.List> foldl' (const (+1)) undefined [1..4]
5

你会天真地想到,"foldl'是严格的"意味着"累加器参数中的严格".以上矛盾说明了这一点.

然而,它更加阴险,因为严格性仅仅是在循环的cons情况下函数应用的结果.如果你输入基础案例,你仍然会得到底部,但不是诱导案例:

Prelude Data.List> foldl' (const (+1)) undefined []
*** Exception: Prelude.undefined

所以参数2中 的严格性也取决于参数3 的值!

这就是我写它的方式:第二个参数中的"完全"严格.

foldl' f z0 xs0 = go z0 xs0
  where
    go !z []     = z
    go !z (x:xs) = go (f z x) xs

正如你所看到的那样,它的第二个论点是真正严格的:

Prelude Data.List.Stream> foldl' (\a b -> 1) undefined [undefined]
*** Exception: Prelude.undefined

与Haskell2010版本相比:

Prelude Data.List.Stream> Data.List.foldl' (\a b -> 1 ) undefined [undefined]
1

这个实际具有实际影响 - 当前的定义不会一致地取消其累加器参数.

历史记录:当我们在2007年为流融合论文指定列表库的严格语义时发现了这一点,并且在Duncan Coutt的博士论文中给出了指定严格性的方法.

Answer 2

foldl和(严格的)foldl'接近于语义上的等价物.不同之处在于性能,尤其是在横切大型列表时.懒惰有建立一个thunk和foldl'的开销是更有效的方式来达到这个结果,因为它不会构建一个巨大的thunk.

在Haskell Wiki上有一篇非常好的文章详细解释了这一点

严格的函数类似于C语言或其他语言中的函数,因为它们的参数通常都是热切评估的.