Search code examples
programming-languagesrecursionfunctional-programmingsmlcurrying

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.

Solution

    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).