讨论Haskell的性能的时候总少不了个各种Normal Form,所以特意翻资料看了一下。
Normal Form
NF指已经被完全求值、不能再归约的表达式。一个表达式里有多个可归约表达式(redex)时,non-strict语义保证不同的求值顺序最终得到一样的Normal Form(前提是求值能结束)。
deepseq a b
会把a
求值到NF。
Weak Head Normal Form
WHNF指求值到最外层构造器或者函数抽象或者一个部分调用的内建函数,所以看到一个表达式是个函数或者构造器,那它就是WHNF了。
Lazy evaluation就是把表达式求值到WHNF,seq a b
会把a
求值到WHNF。
值得注意的是WHNF对子表达式没做要求,子表达式可以是NF或WHNF,以前我不知道这点,总想不明白为什么NF也是WHNF。因为NF肯定也求值到最外层,子表达式如果有也都是NF了,所以NF都是WHNF。
WHNF原来是SPJ造出来的。
Head Normal Form
比较完整的只找到FOLDOC上的解释:
(HNF) A term describing a lambda expression whose top level is either a variable, a data value, a built-in function applied to too few arguments, or a lambda abstraction whose body is not reducible. I.e. the top level is neither a redex nor a lambda abstraction with a reducible body.
An expression in HNF may contain redexes in argument postions whereas a normal form may not.
Haskell里是没有HNF的。