CODEWITHSUNDEEP
programming-languagesrecursionfunctional-programmingsmlcurrying
lbj-ub
lbj-ub

Reputation: 1423

Partial Evaluation and Currying

I have begun to understand a few examples related to currying but I am still not comfortable with the concept of currying as I would like to be. I know that currying can be used to do partial evaluation but I am not sure how it would work in certain cases.

I know how it works in the example below:

fun funkyPlus x y = x*x+y;

so let's say we only pass an argument for x then it is equivalent to the following:

fun funkyPlus 3 = (fn x => fn y => x*x+y)3

which ends up returning

fn y => 9+y

Now, I am trying to apply this idea to the built in function foldl.

I know the code for it is:

fun foldl f b [] = b
   |foldl f b (h::t) = foldl f f(h,b) t.

My question is, what if we do not pass all the arguments to foldl (i.e. we only pass it the first argument which is the function ('a*'b->'b)). In the first example I gave, it was fairly simple to see how the function works when only one of the arguments is passed to it. However, I am having trouble seeing how foldl would work when there is only one argument passed to it.

Help.

Upvotes: 5

Views: 504

Answers (2)

Tom Crockett
Tom Crockett

Reputation: 31619

The first step is to turn your top-level set of equations for foldl into a lambda expression which uses case analysis, like so:

val rec foldl = fn f => fn b => fn lst => 
  case lst of [] => b
        | (h::t) => foldl f (f(h,b)) t

Now you can use the same logic as before. Taking as an example the function fn (x, y) => x * y, we can see that

val prod = foldl (fn (x, y) => x * y)

is equivalent to

val prod = (fn f => fn b => fn lst => 
  case lst of [] => b
        | (h::t) => foldl f (f(h,b)) t) (fn (x, y) => x * y)

which beta-reduces to

val prod = fn b => fn lst => 
  case lst of [] => b
        | (h::t) => foldl (fn (x, y) => x * y) ((fn (x, y) => x * y)(h,b)) t

which beta-reduces to

val prod = fn b => fn lst => 
  case lst of [] => b
        | (h::t) => foldl (fn (x, y) => x * y) (h * b) t

Now since we know from our first definition that prod is equivalent to foldl (fn (x, y) => x * y), we can substitute it into its own definition:

val rec prod = fn b => fn lst => 
  case lst of [] => b
        | (h::t) => prod (h * b) t

We can then mentally convert this back to a function defined by equations if we like:

fun prod b [] = b
  | prod b (h::t) = prod (h * b) t

That's about what you'd expect, right?

Upvotes: 1

Josh Lee
Josh Lee

Reputation: 177875

  1. This does not mean what you think:

    fun funkyPlus 3 = (fn x => fn y => x*x*y)3

    It defines a function which takes an argument that must be 3, and which evaluates to its RHS if it is 3 and is undefined otherwise. What you mean to say is this: If we only provide an argument for x, we have the following:

    funkyPlus 3
→ (fn x => fn y => x*x+y) 3

    and so forth.

  2. Secondly, there is an error in your foldl:

    fun foldl f b [] = b|foldl f b (h::t) = foldl f f(h,b) t;
                                                 ^^^^^
Type clash: expression of type
  'a * 'b
cannot have type
  'c list

    This is because (h,b) is parsed as the third argument to foldl and not as the argument to f. Parenthesize it:

    fun foldl f b [] = b|foldl f b (h::t) = foldl f (f(h,b)) t;
> val ('a, 'b) foldl = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

Now, getting to your question, ML can tell us that an expression like foldl add would have type int -> int list -> int.

But in general, it may help to realize that function application is entirely mechanical. If we have these two definitions:

fun foldl f b [] = b
  | foldl f b (h::t) = foldl f (f(h,b)) t;
add (x,y) = x + y;

then var example = foldl add would be equivalent to this:

fun example b [] = b
  | example b (h::t) = example (h::t) (add(h,b)) t;

All that’s been done is that add has been substituted for f in the body of foldl, nothing more (although I have taken the liberty of replacing foldl add with example in the body).

Upvotes: 2

Related Questions