6

关注<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
4

3 回答 3

13

它并不广为人知，但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 的博士论文中给出。

于 2013-01-11T16:39:17.557 回答
7

foldl 和（严格的） foldl' 在语义上接近等价。不同之处在于性能，尤其是在您遍历大型列表时。懒惰具有构建 thunk 的开销，而 foldl' 是获得该结果的更有效方法，因为它不会构建巨大的 thunk。

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

严格函数的工作方式与 C 或其他语言中的函数类似，因为它们的参数通常会被急切地求值。

于 2013-01-11T13:54:56.263 回答
1

严格函数是一个函数，其参数在主体之前被评估。

于 2013-01-11T13:30:13.493 回答