我试着用简单的语言解释一下。正如其他人指出的那样,head范式并不适用于Haskell,所以我在这里不考虑它。
标准形式
正常形式的表达式被完全求值,没有子表达式可以被进一步求值(即它不包含未求值的符号)。
这些表达式都是标准形式:
42
(2, "hello")
\x -> (x + 1)
这些表达式不是正常形式:
1 + 2 -- we could evaluate this to 3
(\x -> x + 1) 2 -- we could apply the function
"he" ++ "llo" -- we could apply the (++)
(1 + 1, 2 + 2) -- we could evaluate 1 + 1 and 2 + 2
弱头正常型
弱head标准形式的表达式已经被求值到最外层的数据构造函数或lambda抽象(head)。子表达式可以求值,也可以不求值。因此,每个正规形式的表达式也是弱头正规形式,尽管相反的情况并不普遍。
要确定表达式是否为弱头正规形式,我们只需查看表达式的最外层。如果它是一个数据构造函数或,它是弱头正规形式。如果是函数应用,就不是。
这些表达式是弱头范式:
(1 + 1, 2 + 2) -- the outermost part is the data constructor (,)
\x -> 2 + 2 -- the outermost part is a lambda abstraction
'h' : ("e" ++ "llo") -- the outermost part is the data constructor (:)
如上所述,上面列出的所有正规形式表达式也是弱头正规形式。
这些表达式不是弱头正规形式:
1 + 2 -- the outermost part here is an application of (+)
(\x -> x + 1) 2 -- the outermost part is an application of (\x -> x + 1)
"he" ++ "llo" -- the outermost part is an application of (++)
堆叠溢位
将一个表达式求为弱头标准式可能需要先将其他表达式求为WHNF。例如,要计算1 +(2 + 3)到WHNF,我们首先必须计算2 + 3。如果对单个表达式求值会导致太多这样的嵌套求值,则会导致堆栈溢出。
当您构建一个大型表达式时,该表达式直到对其中的大部分进行了计算才会产生任何数据构造函数或lambda,就会发生这种情况。这通常是由foldl的这种用法引起的:
foldl (+) 0 [1, 2, 3, 4, 5, 6]
= foldl (+) (0 + 1) [2, 3, 4, 5, 6]
= foldl (+) ((0 + 1) + 2) [3, 4, 5, 6]
= foldl (+) (((0 + 1) + 2) + 3) [4, 5, 6]
= foldl (+) ((((0 + 1) + 2) + 3) + 4) [5, 6]
= foldl (+) (((((0 + 1) + 2) + 3) + 4) + 5) [6]
= foldl (+) ((((((0 + 1) + 2) + 3) + 4) + 5) + 6) []
= (((((0 + 1) + 2) + 3) + 4) + 5) + 6
= ((((1 + 2) + 3) + 4) + 5) + 6
= (((3 + 3) + 4) + 5) + 6
= ((6 + 4) + 5) + 6
= (10 + 5) + 6
= 15 + 6
= 21
请注意,在将表达式转换为弱头部正常形式之前,它必须走得相当深。
你可能会想,为什么Haskell不提前减少内心的表达?那是因为哈斯克尔的懒惰。由于不能一般地假定每个子表达式都需要,所以表达式是由外向内求值的。
(GHC有一个严格性分析器,它可以检测到总是需要子表达式的某些情况,然后它可以提前计算它。然而,这只是一个优化,您不应该依赖它来避免溢出)。
另一方面,这种表达是完全安全的:
data List a = Cons a (List a) | Nil
foldr Cons Nil [1, 2, 3, 4, 5, 6]
= Cons 1 (foldr Cons Nil [2, 3, 4, 5, 6]) -- Cons is a constructor, stop.
为了避免在知道必须对所有子表达式求值时构建这些大表达式,我们希望强制提前对内部部分求值。
seq
Seq是一个特殊的函数,用于强制表达式求值。它的语义是,seq x y意味着每当y被求为弱头标准形式时,x也被求为弱头标准形式。
它是用于foldl'定义的其他地方,foldl的严格变体。
foldl' f a [] = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs
每次迭代foldl'迫使累加器到WHNF。因此,它可以避免构建一个大表达式,从而避免堆栈溢出。
foldl' (+) 0 [1, 2, 3, 4, 5, 6]
= foldl' (+) 1 [2, 3, 4, 5, 6]
= foldl' (+) 3 [3, 4, 5, 6]
= foldl' (+) 6 [4, 5, 6]
= foldl' (+) 10 [5, 6]
= foldl' (+) 15 [6]
= foldl' (+) 21 []
= 21 -- 21 is a data constructor, stop.
但正如HaskellWiki上的例子所提到的,这并不是在所有情况下都可以节省您的时间,因为累加器只计算到WHNF。在下面的例子中,累加器是一个元组,因此它只强制求元组构造函数的值,而不是acc或len。
f (acc, len) x = (acc + x, len + 1)
foldl' f (0, 0) [1, 2, 3]
= foldl' f (0 + 1, 0 + 1) [2, 3]
= foldl' f ((0 + 1) + 2, (0 + 1) + 1) [3]
= foldl' f (((0 + 1) + 2) + 3, ((0 + 1) + 1) + 1) []
= (((0 + 1) + 2) + 3, ((0 + 1) + 1) + 1) -- tuple constructor, stop.
为了避免这种情况,必须在求元组构造函数值时强制求acc和len值。我们通过使用seq来做到这一点。
f' (acc, len) x = let acc' = acc + x
len' = len + 1
in acc' `seq` len' `seq` (acc', len')
foldl' f' (0, 0) [1, 2, 3]
= foldl' f' (1, 1) [2, 3]
= foldl' f' (3, 2) [3]
= foldl' f' (6, 3) []
= (6, 3) -- tuple constructor, stop.