CODEWITHSUNDEEP
haskellfunctional-programmingevaluationcurrying
Tim
Tim

Reputation: 99428

How does outermost evaluation work on an application of a curried function?

mult is defined as a curried function:

mult    ::  Int ->  Int ->  Int
mult    x   =   \y  ->  x   *   y

In mult (1+2) (2+3),

Innermost evaluation works on the expression as following, according to Programming in Haskell by Hutton:

mult    (1+2)   (2+3)
= { applying    the first   +   }
mult    3   (2+3)
= { applying    mult    }
(\y ->  3   *   y)  (2+3)
= { applying    +   }
(\y ->  3   *   y)  5
= { applying    the lambda  }
3   *   5
= { applying    *   }
15

How does outermost evaluation work on mult (1+2) (2+3)? Does outermost evaluation works as the following?

mult (1+2) (2+3)
= mult (1+2) 5
= (\y -> (1+2) * y) 5
= (1+2) * 5  // Is (1+2) evaluated before (1+2) * 5, because builtin function "*" is strict, i.e. application of builtin function always happen after evaluation of its args?
= 3*5
= 15

Thanks.

Upvotes: 1

Views: 438

Answers (2)

Bergi
Bergi

Reputation: 664538

Write down the parse tree:

         o
       /   \
     o       o
    / \     /|\
mult   o   2 + 3
      /|\
     1 + 2

(For simplicitly I'm treating the binary infix + operators as a single application, it could have been ((+) 1) 2 as well)

Now the outermost function application is that of mult (1+2) to the argument 2+3, but it's not reducible because the function is not a single value but an application itself. We have to evaluate that first:

(mult (1+2)) (2+3)
((\x->\y->x*y) (1+2)) (2+3) -- the value that `mult` refers to
(\y->(1+2)*y) (2+3) -- evaluate the application of `\x->`

Now we can evaluate the root function application:

(1+2) * (2+3) -- application of `\y->`

Now the outermost expression is the *, but as you know these integer operators are strict so they need to evaluate their arguments first (left-to-right, IIRC):

3 * (2+3)
3 * 5
15

Upvotes: 1

Will Ness
Will Ness

Reputation: 71065

The outermost redex in mult (1+2) (2+3) i.e.

          mult
       /        \
      +          +
    1   2      2   3

is mult x y where x = (1+2) and y = (2+3).

There are two inner redexes, (1+2) and (2+3). The leftmost innermost redex is thus (1+2).

Reducing by the leftmost innermost redex proceeds as follows:

mult (1+2) (2+3)
=
mult 3 (2+3)
=
mult 3 5
= {- mult x = \y -> x * y -}
(let x = 3 in (\y -> x * y)) 5
=
let x = 3 in let y = 5 in x * y
=
3 * 5
=
15

Reducing by the topmost redex proceeds as follows:

mult (1+2) (2+3)
= {- mult x = \y -> x * y -}
(let x = (1+2) in (\y -> x * y)) (2+3)
=
let x = (1+2) in let y = (2+3) in x * y
=
(1+2) * (2+3)
=
3 * (2+3)
=
3 * 5
=
15

Upvotes: 1

Related Questions