What does the 'outermost part' of expression mean in Haskell

Question

True beginner here, and I'm reading about the differences between NF and WHNF, and one of the definitions I come across states

To determine whether an expression is in weak head normal form, we only have to look at the outermost part of the expression.

I'm not sure what criteria to apply to determine what the 'outermost' part is. For example (from a stack overflow answer by @hammer):

'h' : ("e" ++ "llo") -- the outermost part is the data constructor (:)
(1 + 1, 2 + 2)       -- the outermost part is the data constructor (,)
\x -> 2 + 2          -- the outermost part is a lambda abstraction

Especially in the first example there, the (:) operator is in the middle of the 'h' and the other expression, so how is it the outermost part?

In general, when looking at an expression, how does one determine what the outermost part is?

Answer 1

Good question. Here, "outermost" (or "topmost") describes the location in reference to a kind of standard, abstract view of the expression that can differ from its actual syntax. For example, these two expressions:

(1, 2)
(,) 1 2

have identical meaning in Haskell. It turns out that in both cases, the constructor (,) is the outermost part of the expression, even though the expressions have different syntactic form with the comma appearing in different physical locations in the syntax.

Generally speaking, Haskell's "standard syntax" involves function application of the form:

fexpr expr1 .. exprn

However, the language also allows other kinds of syntax:

1 + 2                -- infix operators
(3, 4)               -- tuples
[5,6,7,8]            -- lists
"abc"                -- strings

These alternate syntaxes can be converted to the standard syntax like so:

1 + 2   ==>   (+) 1 2
(3, 4)  ==>   (,) 3 4
[5,6,7,8]   ==>  (:) 5 ((:) 6 ((:) 7 ((:) 8 [])))
"abc"   ==>   (:) 'a' ((:) 'b' ((:) 'c' []))

Though it's far from obvious, (+) is a variable whose value is a function (like sqrt); while (,) and (:) are constructors (just like True or Just). Even more confusing and further from obvious, even though [1,2,3] is special syntax, the empty list [] is a (unary) constructor! That's why I still used empty lists on the right-hand side in my standard syntax versions.

Anyway, once converted to the standard syntax, an expression will either be a constructor application, like one of these:

True               -- a nullary constructor
(,) (1+2) (2+3)    -- constructor expecting two args and fully applied
(:) 5              -- constructor partially applied and expecting one more arg

and we say that the "outermost part" of the expression is this constructor application, or it will be an unapplied lambda abstraction:

(\x y -> (+) x (length y))

and we say that the "outermost part" of the expression is this unapplied lambda abstraction, or it will be something else:

w                    -- a variable
(\x -> x) 10         -- an applied lambda abstraction
(f x) y ((*) 2 z)    -- some other function application
(+) 10 (length (1:[]))  -- another function application

and we say the "outermost part" of the expression is a variable reference or a function application or whatever.

Anyway, if the outermost part is either a constructor application or an unapplied lambda abstraction, then it's said to be in weak head normal form. If it's something else, it's not.

So, Just (5+6) is in WHNF because the outermost part is the application of the constructor Just. On the other hand, sqrt (5+6) is not in WHNF because the outermost part is the application of the variable sqrt, and a variable isn't a constructor.

Similarly, 5+6 itself is not in WHNF because the outermost part is the application of the variable (+) to 5 and 6, while [5,6] is in WHNF because the outermost part is the application of the (implied) constructor (:) to 5 and [6].