This example provides a brief overview - for a more in-depth explanation of normal forms and examples, see this question.
The reduced normal form (or just normal form, when the context is clear) of an expression is the result of evaluating all reducible subexpressions in the given expression. Due to the non-strict semantics of Haskell (typically called laziness), a subexpression is not reducible if it is under a binder (i.e. a lambda abstraction - \x -> ..
). The normal form of an expression has the property that if it exists, it is unique.
In other words, it does not matter (in terms of denotational semantics) in which order you reduce subexpressions. However, the key to writing performant Haskell programs is often ensuring that the right expression is evaluated at the right time, i.e, the understanding the operational semantics.
An expression whose normal form is itself is said to be in normal form.
Some expressions, e.g. let x = 1:x in x
, have no normal form, but are still productive. The example expression still has a value, if one admits infinite values, which here is the list [1,1, ...]
. Other expressions, such as let y = 1+y in y
, have no value, or their value is undefined
.
The RNF corresponds to fully evaluating an expression - likewise, the weak head normal form (WHNF) corresponds to evaluating to the head of the expression. The head of an expression e
is fully evaluated if e
is an application Con e1 e2 .. en
and Con
is a constructor; or an abstraction \x -> e1
; or a partial application f e1 e2 .. en
, where partial application means f
takes more than n
arguments (or equivalently, the type of e
is a function type). In any case, the subexpressions e1..en
can be evaluated or unevaluated for the expression to be in WHNF - they can even be undefined
.
The evaluation semantics of Haskell can be described in terms of the WHNF - to evaluate an expression e
, first evaluate it to WHNF, then recursively evaluate all of its subexpressions from left to right.
The primitive seq
function is used to evaluate an expression to WHNF. seq x y
is denotationally equal to y
(the value of seq x y
is precisely y
); furthermore x
is evaluated to WHNF when y
is evaluated to WHNF. An expression can also be evaluated to WHNF with a bang pattern (enabled by the -XBangPatterns
extension), whose syntax is as follows:
f !x y = ...
In which x
will be evaluated to WHNF when f
is evaluated, while y
is not (necessarily) evaluated. A bang pattern can also appear in a constructor, e.g.
data X = Con A !B C .. N
in which case the constructor Con
is said to be strict in the B
field, which means the B
field is evaluated to WHNF when the constructor is applied to sufficient (here, two) arguments.