2011-07-29 12:13:48 8 Comments

What does **Weak Head Normal Form** (WHNF) mean? What does **Head Normal form** (HNF) and **Normal Form** (NF) mean?

Real World Haskell states:

The familiar seq function evaluates an expression to what we call head normal form (abbreviated HNF). It stops once it reaches the outermost constructor (the “head”). This is distinct from normal form (NF), in which an expression is completely evaluated.

You will also hear Haskell programmers refer to weak head normal form (WHNF). For normal data, weak head normal form is the same as head normal form. The difference only arises for functions, and is too abstruse to concern us here.

I have read a few resources and definitions (Haskell Wiki and Haskell Mail List and Free Dictionary) but I don't get it. Can someone perhaps give an example or provide a layman definition?

I am guessing it would be similar to:

```
WHNF = thunk : thunk
HNF = 0 : thunk
NF = 0 : 1 : 2 : 3 : []
```

How do `seq`

and `($!)`

relate to WHNF and HNF?

## Update

I am still confused. I know some of the answers say to ignore HNF. From reading the various definitions it seems that there is no difference between regular data in WHNF and HNF. However, it does seem like there is a difference when it comes to a function. If there was no difference, why is `seq`

necessary for `foldl'`

?

Another point of confusion is from the Haskell Wiki, which states that `seq`

reduces to WHNF, and will do nothing to the following example. Then they say that they have to use `seq`

to force the evaluation. Is that not forcing it to HNF?

Common newbie stack overflowing code:

`myAverage = uncurry (/) . foldl' (\(acc, len) x -> (acc+x, len+1)) (0,0)`

People who understand seq and weak head normal form (whnf) can immediately understand what goes wrong here. (acc+x, len+1) is already in whnf, so seq, which reduces a value to whnf, does nothing to this. This code will build up thunks just like the original foldl example, they'll just be inside a tuple. The solution is just to force the components of the tuple, e.g.

`myAverage = uncurry (/) . foldl' (\(acc, len) x -> acc `seq` len `seq` (acc+x, len+1)) (0,0)`

-Haskell Wiki on Stackoverflow

### Related Questions

#### Sponsored Content

#### 31 Answered Questions

### [SOLVED] What exactly is RESTful programming?

**2009-03-22 14:45:39****hasen****1573853**View**3796**Score**31**Answer- Tags: http rest definition

#### 44 Answered Questions

### [SOLVED] What is a monad?

**2008-09-04 23:26:44****ljs****219356**View**1305**Score**44**Answer- Tags: haskell functional-programming monads terminology

#### 15 Answered Questions

### [SOLVED] Getting started with Haskell

**2009-06-18 13:17:11****anderstornvig****233380**View**757**Score**15**Answer- Tags: haskell functional-programming

#### 1 Answered Questions

### [SOLVED] Expression Evaluation In Haskell: Fixing the type of a sub-expression causes parent expression to be evaluated to different degrees

**2015-09-03 05:27:02****unshul****110**View**8**Score**1**Answer- Tags: haskell lazy-evaluation weak-head-normal-form

#### 4 Answered Questions

### [SOLVED] Test if a value has been evaluated to weak head normal form

**2015-02-24 02:51:30****Cirdec****846**View**16**Score**4**Answer- Tags: haskell lazy-evaluation thunk weak-head-normal-form

#### 2 Answered Questions

### [SOLVED] What does “⊥” mean in “The Strictness Monad” from P. Wadler's paper?

**2014-10-17 15:52:08****iceman****887**View**10**Score**2**Answer- Tags: haskell semantics strictness

#### 1 Answered Questions

### [SOLVED] Weak head normal form and order of evaluation

**2014-04-26 15:59:58****wafflecat****157**View**3**Score**1**Answer- Tags: haskell stack-overflow lazy-evaluation strictness weak-head-normal-form

#### 2 Answered Questions

### [SOLVED] Why is a built-in function applied to too few arguments considered to be in weak head normal form?

**2014-06-27 08:29:11****Robert Zaremba****874**View**14**Score**2**Answer- Tags: haskell lambda-calculus reduction partial-application weak-head-normal-form

#### 5 Answered Questions

### [SOLVED] Haskell: How does non-strict and lazy differ?

**2011-08-21 20:33:36****user295190****4921**View**60**Score**5**Answer- Tags: haskell definition lazy-evaluation

#### 3 Answered Questions

### [SOLVED] Haskell, Measuring CPU time of a function

**2011-03-21 14:46:21****h--n****2493**View**9**Score**3**Answer- Tags: haskell lazy-evaluation

## 6 comments

## @Heinrich Apfelmus 2011-07-30 15:58:18

Haskell programs are

expressionsand they are run by performingevaluation.To evaluate an expression, replace all function applications by their definitions. The order in which you do this does not matter much, but it's still important: start with the outermost application and proceed from left to right; this is called

lazy evaluation.Example:

Evaluation stops when there are no more function applications left to replace. The result is in

normal form(orreduced normal form, RNF). No matter in which order you evaluate an expression, you will always end up with the same normal form (but only if the evaluation terminates).There is a slightly different description for lazy evaluation. Namely, it says that you should evaluate everything to

weak head normal formonly. There are precisely three cases for an expression to be in WHNF:`constructor expression_1 expression_2 ...`

`(+) 2`

or`sqrt`

`\x -> expression`

In other words, the head of the expression (i.e. the outermost function application) cannot be evaluated any further, but the function argument may contain unevaluated expressions.

Examples of WHNF:

Notes

Head normal form(HNF) is irrelevant for Haskell. It differs from WHNF in that the bodies of lambda expressions are also evaluated to some extent.## @user295190 2011-07-31 00:38:10

Is the use of

`seq`

in`foldl'`

force the evaluation from WHNF to HNF?## @Heinrich Apfelmus 2011-07-31 07:38:56

@snmcdonald: No, Haskell does not make use of HNF. Evaluating

`seq expr1 expr2`

will evaluate the first expression`expr1`

to WHNF before evaluating the second expression`expr2`

.## @marc 2011-07-29 13:20:35

The WHNF does not want the body of lambdas to be evaluated, so

`seq`

wants its first argument to be in WHNF, soevaluates to

instead of, what would be using HNF

## @Zhen 2011-07-31 08:37:26

Or I misunderstand the example, or you mix 1 and 2 in the WHNF and HNF.

## @marc 2011-08-01 08:06:17

@Zhen, you're right, fixed that

## @hammar 2011-07-31 11:59:52

I'll try to give an explanation in simple terms. As others have pointed out, head normal form does not apply to Haskell, so I will not consider it here.

## Normal form

An expression in normal form is fully evaluated, and no sub-expression could be evaluated any further (i.e. it contains no un-evaluated thunks).

These expressions are all in normal form:

These expressions are not in normal form:

## Weak head normal form

An expression in weak head normal form has been evaluated to the outermost data constructor or lambda abstraction (the

head). Sub-expressionsmay or may not have been evaluated. Therefore, every normal form expression is also in weak head normal form, though the opposite does not hold in general.To determine whether an expression is in weak head normal form, we only have to look at the outermost part of the expression. If it's a data constructor or a lambda, it's in weak head normal form. If it's a function application, it's not.

These expressions are in weak head normal form:

As mentioned, all the normal form expressions listed above are also in weak head normal form.

These expressions are not in weak head normal form:

## Stack overflows

Evaluating an expression to weak head normal form may require that other expressions be evaluated to WHNF first. For example, to evaluate

`1 + (2 + 3)`

to WHNF, we first have to evaluate`2 + 3`

. If evaluating a single expression leads to too many of these nested evaluations, the result is a stack overflow.This happens when you build up a large expression that does not produce any data constructors or lambdas until a large part of it has been evaluated. These are often caused by this kind of usage of

`foldl`

:Notice how it has to go quite deep before it can get the expression into weak head normal form.

You may wonder, why does not Haskell reduce the inner expressions ahead of time? That is because of Haskell's laziness. Since it cannot be assumed in general that every subexpression will be needed, expressions are evaluated from the outside in.

(GHC has a strictness analyzer that will detect some situations where a subexpression is always needed and it can then evaluate it ahead of time. This is only an optimization, however, and you should not rely on it to save you from overflows).

This kind of expression, on the other hand, is completely safe:

To avoid building these large expressions when we know all the subexpressions will have to be evaluated, we want to force the inner parts to be evaluated ahead of time.

`seq`

`seq`

is a special function that is used to force expressions to be evaluated. Its semantics are that`seq x y`

means that whenever`y`

is evaluated to weak head normal form,`x`

is also evaluated to weak head normal form.It is among other places used in the definition of

`foldl'`

, the strict variant of`foldl`

.Each iteration of

`foldl'`

forces the accumulator to WHNF. It therefore avoids building up a large expression, and it therefore avoids overflowing the stack.But as the example on HaskellWiki mentions, this does not save you in all cases, as the accumulator is only evaluated to WHNF. In the example, the accumulator is a tuple, so it will only force evaluation of the tuple constructor, and not

`acc`

or`len`

.To avoid this, we must make it so that evaluating the tuple constructor forces evaluation of

`acc`

and`len`

. We do this by using`seq`

.## @user295190 2011-07-31 14:44:36

Thank you for spelling it out. I can understand what the other answers were trying to say now. I needed that extra explanation, that all NF are WHNF but not all WHNF. It makes senses because NF is the outermost and only expression.

## @hammar 2011-07-31 14:46:26

Head normal form requires that the body of a lambda is reduced as well, while weak head normal form does not have this requirement. So

`\x -> 1 + 1`

is WHNF but not HNF.## @user295190 2011-07-31 14:46:34

Wikipedia states HNF is "[a] term is in head normal form if there is no beta-redex in head position". Is Haskell "weak" because it does not beta-redex sub-expressions?

## @user295190 2011-07-31 14:52:42

Got it. Great Answer.

## @Bergi 2014-05-13 10:26:10

How do strict data constructors come into the play? Are they just like calling

`seq`

on their arguments?## @hammar 2014-05-13 10:41:57

@Bergi: Yes, data constructors with strict fields will force those fields to be evaluated to WHNF when the constructor itself is evaluated.

## @Captain Obvious 2015-01-17 09:53:47

You say 1 + 2 is not NF, however you also say 1 + 2 is not WHNF, so what is it?

## @Captain Obvious 2015-01-18 08:37:19

What is 1 + 2 ???

## @hammar 2015-01-19 12:43:00

@CaptainObvious: 1 + 2 is neither NF nor WHNF. Expressions aren't always in a normal form.

## @egdmitry 2015-03-10 19:13:22

"Notice how it has to go quite deep before it can get the expression into weak head normal form." — it only appears to be in WHNF on the last line (21), right?

## @hammar 2015-03-11 12:16:29

@egdmitry: Yes. The point is that in order to get there, it first has to evaluate all the recursive calls to

`foldl`

before it can do the sums, generating a lot of unnecessary thunks in the process.## @CMCDragonkai 2015-04-03 13:11:20

In your second example of

`foldl'`

with the tuple, could you potentially use deepSeq inside`foldl'`

which would subsume the`seq`

usage inside`f`

?## @hammar 2015-04-03 20:30:10

@CMCDragonkai: Yes,

`deepseq`

would also work.## @mucaho 2015-06-06 10:43:01

You wrote

`data List = Cons a (List a) | Nil`

. Did you forget the type parameter here -`data List a = ...`

?## @hammar 2015-06-06 13:29:32

@mucaho: Indeed I did. Good catch!

## @Zorobay 2017-05-31 09:49:11

When I try your last example in ghci (

`foldl'`

with`f (acc, len) x = (acc + x, len +1)`

) it gives me (6,3) directly, without using`seq`

. How come?## @hammar 2017-06-02 15:34:01

@Zorobay: In order to print the result, GHCi ends up evaluating the expression completely to NF, not just to WHNF. One way to tell the difference between the two variants is to enable memory stats with

`:set +s`

. You can then see that`foldl' f`

ends up allocating more thunks than`foldl' f'`

.## @aculich 2012-02-18 16:27:14

The section on Thunks and Weak Head Normal Form in the Haskell Wikibooks description of laziness provides a very good description of WHNF along with this helpful depiction:

## @CMCDragonkai 2015-04-03 13:14:31

I know people say to ignore head normal form, but can you give an example in that diagram you have what a head normal form looks like?

## @Chris Smith 2011-07-29 13:19:00

A good explanation with examples is given at http://foldoc.org/Weak+Head+Normal+Form Head normal form simplifies even the bits of an expression inside of a function abstraction, while "weak" head normal form stops at function abstractions.

From the source, if you have:

that is in weak head normal form, but not head normal form... because the possible application is stuck inside of a function that can't be evaluated yet.

Actual head normal form would be difficult to implement efficiently. It would require poking around inside of functions. So the advantage of weak head normal form is that you can still implement functions as an opaque type, and hence it's more compatible with compiled languages and optimization.

## @alternative 2011-07-29 13:12:53

Basically, suppose you have some sort of thunk,

`t`

.Now, if we want to evaluate

`t`

to WHNF or NHF, which are the same except for functions, we would find that we get something like`t1 : t2`

where`t1`

and`t2`

are thunks. In this case,`t1`

would be your`0`

(or rather, a thunk to`0`

given no extra unboxing)`seq`

and`$!`

evalute WHNF. Note that## @user295190 2011-07-29 16:25:25

So seq reduces WHNF to HNF?

## @alternative 2011-07-29 17:57:09

@snmcdonald Ignore HNF. seq says that when this is evaluated to WHNF, evaluate the first argument to WHNF.