CODEWITHSUNDEEP
haskell
softshipper
softshipper

Reputation: 34071

Why the evaluation stops?

I have following code:

foldr const 0 ([1] ++ undefined)

and I've got as the result 1.

I know, that foldr is right associated. Writing out the example from above:

const 1 (const undefined 0)

Why expression in the parentheses does not get evaluated as first?

Because function application has higher precedence then parentheses?

Upvotes: 0

Views: 131

Answers (3)

simon1505475
simon1505475

Reputation: 675

What I believe you are expecting what is called "applicative evaluation order". In other words, in f (g x), you expect g x to be evaluated first, then f to be called on the result.

In your example, that would mean that evaluation would start with evaluating 0, [1] and undefined which is where I believe you expect the crash.

Haskell has what is called "call by need" or "lazy evaluation". In f (g x), f is evaluated first, providing it as an argument a program (often referred to as "thunk") to evaluate g x. That means that if the value of g x is never needed by f, it never gets evaluated.

Here is how your example would get evaluated (I'm placing the definition of foldr below for reference):

  foldr const 0 ([1] ++ undefined)          -- one step of evaluation of ++
= foldr const 0 (1 : ([] ++ undefined))     -- second equation of foldr
= const 1 (foldr const 0 ([] ++ undefined)) -- evaluate const
= 1

And here is the definitions of foldr and (++):

foldr _ z []     =  z
foldr f z (x:xs) =  f x (foldr f z xs)

(++) [] ys = ys
(++) (x:xs) ys = x : (xs ++ ys)

Upvotes: 2

Rein Henrichs
Rein Henrichs

Reputation: 15605

To properly evaluate const 1 (const undefined 0), we need to know the definition of const, the evaluation strategy used by GHC, and the behavior of currying in functions which (appear to) take multiple arguments. (Not necessarily in that order.)

Definition of const

The definition of const is

const c _ = c

Currying

Functions which seem to take multiple arguments are actually curried:

f x y = (f x) y

We can explicitly curry const using eta abstraction (f x = y becomes f = \x -> y), turning it into a function that takes an argument and gives another function:

const c _ = c
= { eta abstraction }
const c = \_ -> c

Combining these two concepts means that whenever we see const x y, we can replace it with (\_ -> x) y:

const x y
= { currying }
(const x) y
= { const c = \_ -> c }
(\_ -> x) y

Outermost Evaluation and Short Circuiting

Evaluation in Haskell* starts with the outermost reducible expression (redex) and is triggered by pattern matching. This means that in f (g x), f is evaluated before g x (it is outermost). g x is then only evaluated if the evaluation of f demands it. Then, in turn, x is only evaluated if the evaluation of g demands it.

One of the properties of outermost-first evaluation is *short-circuiting(: if the evaluation of an outer expression doesn't demand a result from an inner expression, the inner expression is never evaluated. In particular, this means that (\_ -> x) y = x regardless of what y is, because \_ -> x doesn't demand the evaluation of y.

Evaluating const 1 (const undefined 0)

Putting these together, we can evaluate const 1 (const undefined 0)

const 1 (const undefined 0)
= { const x y = (\_ -> x) y }
(\_ -> 1) (const undefined 0)
= { (\_ -> x) y = x }
1

Once you understand this, it's easy enough to skip over the currying and just write:

const 1 (const undefined 0)
= { definition of const }
1

because const c _ = c, c = 1, and we know the second argument is never evaluated.

(You also asked about precedence but precedence is not relevant to the evaluation of const 1 (const undefined 0).)

* Strictly speaking**, Haskell does not define an evaluation order. It specifies that evaluation must be non-strict and leaves the implementation of this semantics up to Haskell implementations. GHC uses lazy evaluation, which is outermost-first evaluation combined with sharing (which says that x will be evaluated at most once in let x = 1 + 1 in x * x).

** Yes, this is a pun.

Upvotes: 3

sepp2k
sepp2k

Reputation: 370112

Why expression in the parentheses does not get evaluated as first?

Haskell uses lazy evaluation. This means an argument is evaluated if and when it is used by the function. This differs from eager evaluation where all arguments of the function are executed before the function is called.

Because function application has higher precedence then parentheses?

Precedence has nothing to do with it. Precedence just determines what's an operand to what (i.e. is "x ??? y !!! z" an application of the operator ??? to the operands x and y !!! z or of the operator !!! to x ??? y and z). It does not affect evaluation order.

Upvotes: 6

Related Questions