HIGHER ORDER FUNCTIONS

----------------------------------------------------------------


***** FUNCTIONS AS PARAMETERS: MAP *****

To introduce the idea of functions as parameters, we will write
two recursive functions that are structurally very similar.  The
first function, "censor", is intended to remove offensive words
from a list.  This function will need to use the "member"
function given below.
    (*----------------------------------------*)
    fun member item [] = false
      | member item (x::xs) =
        (item = x) orelse (member item xs);
    (*----------------------------------------*)
    (*----------------------------------------*)
    member 1 [3,2,1,0];
    member "not-there" ["a list", "of", "strings"];
    (*----------------------------------------*)

To write the function censor, we will first write a function
that censors individual words.
    (*----------------------------------------*)
    fun censor_word x =
        if (member x ["midterm", "final",
                      "extension", "cobol"]) then
            "%*&^#!"
        else
            x;
    (*----------------------------------------*)

Given "censor_word", we can now write a very straightforward
recursive function that censors an entire list.
    (*----------------------------------------*)
    fun censor [] =[]
      | censor (x::xs) = (censor_word x)::(censor xs);
    (*----------------------------------------*)
    (*----------------------------------------*)
    censor ["I", "need", "an", "extension", "because", "I",
            "have", "a", "cobol", "midterm", "tomorrow."];
    (*----------------------------------------*)

Using a similar approach to that used in "censor", we can write
a function square_list that will square every element in a list
of integers.
    (*----------------------------------------*)
    fun square x = (x:int) * x;


    fun square_list [] = []
      | square_list (x::xs) = (square x)::(square_list xs);
    (*----------------------------------------*)
    (*----------------------------------------*)
    square_list [5,3,4,2];
    (*----------------------------------------*)

Notice that the functions "square_list" and "censor" are
practically identical.  The only difference is the function they
apply to each element of the input list.  Your programming
instincts should tell you to try and unify these two redundant
functions into something more general.

This turns out to be very simple in ML.  The function "map" will
serve as a general template for all recursive functions such as
"censor" and "square_list".  Unlike either of these functions,
"map" takes two parameters.  (Of course, it really only takes
one, but we can safely ignore that subtlety here.)  The second
parameter is a list, and the first parameter is a function that
will be applied to every element of the list.
    (*----------------------------------------*)
    fun map f [] = []
      | map f (x::xs) = (f x)::(map f xs);
    (*----------------------------------------*)
Pay careful attention to the type information returned by ML for
this example.

Using map, we can now rewrite both censor and square-list much
more elegantly.
    (*----------------------------------------*)
    fun censor2 aList = map censor_word aList;

    fun square_list2 aList = map square aList;
    (*----------------------------------------*)
    (*----------------------------------------*)
    censor2 ["When", "is", "the", "final"];
    square_list2 [0,6,3,2];
    (*----------------------------------------*)

Note that in this context, the function "square" is not being
called; rather, it is being passed as a parameter to "map".

The function "map" turns out to be extraordinarily useful.  It
is so useful, in fact, that programmers often attempt to use it
where it should not be used.  To avoid these pitfalls, commit
the follwing rule to memory.

The Law of Map: map takes a list of n things, and map returns a
list of n things.  No functional parameter supplied to map can
change this law.

***** NAMELESS FUNCTIONS *****

When passing functions as parameters, it is sometimes more
convenient to define the functional parameter on the fly rather
than as a separate entity.  The function below demonstrates this
technique.

For example, rather than defining a "censor_word" function, the
function "censor3" defines an anonymous function in place.  The
expression "(fn x => if (member x badwords) then "%*&^#!" else
x)" really is a function just like any other, but it happens not
to have a name.  Notice the slight syntactic differences between
this function and functions that are given a name.
    (*----------------------------------------*)
    fun censor3 badwords aList =
        map (fn x => if (member x badwords)
                     then "%*&^#!" else x)
            aList;
    (*----------------------------------------*)
    (*----------------------------------------*)
    censor3 ["Berkeley", "USC"]
            ["Are we playing", "USC", "or",
             "Berkeley", "this weekend?"];
    (*----------------------------------------*)

Each element of the list ["Are we..."] will in turn be used as
the parameter x of the nameless function.  The results of
applying this nameless function to the input list will be
collected as a new list and returned by "censor3".

This version of censor is different from its ancestors in that
it takes an additional parameter which defines the list of words
to be censored.  The nameless function can see this "badwords"
parameter.

***** A CATALOG OF USEFUL LIST MANIPULATING FUNCTIONS *****

The function "map" is just one example of a higher order
function.  As you might imagine, there are innumerable
situations where it is convenient to use functional arguments.
Some of the more commonly used higher order list-maniplating
functions are described below.

The function "forall" is used to determine if every element in a
list has a certain property.
    (*----------------------------------------*)
    fun forall f [] = true
      | forall f (x::xs) = (f x) andalso (forall f xs);
    (*----------------------------------------*)
    (*----------------------------------------*)
    fun all_positive aList =
        forall (fn x => x > 0) aList;

    all_positive [1,2,3,4];
    all_positive [~1,2,3,4];
    (*----------------------------------------*)

A closely related function is "exists", which determines if any
element of a list has a certain property.
    (*----------------------------------------*)
    fun exists f [] = false
      | exists f (x::xs) = (f x) orelse (exists f xs);
    (*----------------------------------------*)

We can use this function in an extended example to determine
whether a number is prime.  To begin, we introduce a function
"fromto" which, although not higher order itself, is often used
in conjunction with higher order functions.
    (*----------------------------------------*)
    (* generates a list of numbers from low to hi *)
    exception illegal_range;
    fun fromto low hi =
        if low > hi then
            raise illegal_range
        else if low = hi then
            [low]
        else
            low::(fromto (low+1) hi);
    (*----------------------------------------*)
    (*----------------------------------------*)
    fromto 1 10;
    (*----------------------------------------*)

We will also need some simple mathematical functions:
    (*----------------------------------------*)
    (* Round a real up to the next integer 8)
    fun round x = floor(x + 0.5);

    (* Does top/bottom = an integer? *)
    fun divides bottom top = top mod bottom = 0;
    (*----------------------------------------*)

Finally, we need an algorithm for testing a number for
primality.  An obvious (albeit not very efficient) approach is
simply to see if any integer up to the square root evenly
divides our candidate.
    (*----------------------------------------*)
    fun prime 1 = true
      | prime 2 = true
      | prime n =
        not (exists (fn x => (divides x n))
                    (fromto 2 (round (sqrt (real n)))));
    (*----------------------------------------*)
    (*----------------------------------------*)
    prime 127;
    prime 7869;
    (*----------------------------------------*)

Filter is useful for extracting every element of a list that
passes a certain test.  The test is passed as a functional
argument.
    (*----------------------------------------*)
    fun filter f [] = []
      | filter f (x::xs) =
          if (f x) then x::(filter f xs)
                       else (filter f xs);
    (*----------------------------------------*)
Given the functions above, we can use filter to find all the
primes between a pair of numbers:
    (*----------------------------------------*)
    fun primes low hi = filter prime (fromto low hi);

    primes 1 100;
    (*----------------------------------------*)

The final high-order function we will look at is called
"reduce".  This is a very powerful function, and it is often
misunderstood.  The easiest way to introduce "reduce" is through
two non-higher-order functions:
    (*----------------------------------------*)
    (* Adds up every number in a list *)
    fun sumlist [] = 0
      | sumlist (x::xs) = x + sumlist xs;

    (* Appends two lists (same as "@") *)
    fun append [] aList = aList
      | append (x::xs) aList = x :: (append xs aList);
    (*----------------------------------------*)

If you look carefully at these two examples, you will notice
that they have the same recursive structure.  We can isolate
this structure in the function reduce.  Reduce takes three
inputs (one, really, but again we will ignore that): a function
to apply in the recursion, a base case to return when the
recursion terminates, and a list to recurse down.
    (*----------------------------------------*)
    fun reduce f base nil = base
      | reduce f base (x::xs) =
          f x (reduce f base xs);
    (*----------------------------------------*)

Using reduce, we can rewrite both sumlist and append without any
explicit recursion.
    (*----------------------------------------*)
    fun plus x y = (x:int) + y;

    fun sumlist L = reduce plus 0 L;
    (*----------------------------------------*)
    (*----------------------------------------*)
    fun cons x y = x::y;

    fun append L1 L2 = reduce cons L2 L1;
    (*----------------------------------------*)