More about ML

Higher Order Function

The Order of a Function
```
  The order of a function is defined by the following induction :

  Basis : A function is "first-order" if its arguments and result are all "data", 
                 that is, not functions.
  Induction: A function is of order one more than the largest of the orders of its
                 arguments and result.
```
Some common Higher-Order Functions
- map
  The map function takes a function F and a list [a₁,a₂,...,a_n], and produces the list [F(a₁), F(a₂),..., F(a_n)].
  That is, it applies F to each element of the list and returns the list of resulting values.
```
         fun map (F, nil) = nil 
         |   map(F, x::xs) = F(x) :: map(F,xs)

         val map = fn : ( 'a -> 'b) * 'a list -> 'b list 
```
- reduce
  The reduce function takes a function F with two arguments and a list [a₁,a₂,...,a_n].
  The function F normally is assumed to compute some associative operation such as addition (or multiplication), that is, F(x,y) = x + y.
  (or F(x,y) = x * y .)
  The result of reduce on F and [a₁,a₂,...,a_n] is F(a₁, F(a₂,F(...,F(a_n-1,a_n)...))).
```
    
        exception EmptyList;

        fun reduce(F, nil) = raise EmptyList   
        |   reduce(F,[a]) = a 
        |   reduce(F,x::xs) = F(x,reduce(F,xs)) ;

        val reduce = fn : ('a * 'a -> 'a) * 'a list -> 'a


another defintion of reduce :

        fun reduce f  [] v = v 
        |   reduce f (a::y) v = f(a, reduce f y v) ;

        val reduce = fn : ( 'a * 'b -> 'b) -> 'a list -> 'b -> 'b
```
- filter
  The function filter takes a predicate P, that is , a function whose value is boolean, and a list [a₁,a₂,...,a_n]. The result is the list of all those elements on the given list that satisfy the predicate P.
```
        fun filter(P,nil) = nil
        |   filter(P,x::xs) =
               if P(x) then x::filter(P,xs)
               else filter(P,xs) ;

        val filter = fn : ('a -> bool) * 'a list -> 'a list
```
- folding List
  ML provides the user a pair of functions called foldr and foldl. Both functions perform a variety of fold operation, which takes a list L =[a₁,a₂,...,a_n] and treats each element a_i as if it were a function; call this function F_ai. When we apply a folding operation to L, we construct the function that is the composition of all the functions F_a1,F_a2,...,F_an.
  The difference between foldr and foldl is that foldr composes the functions F_ai starting from the end (i.e. from the right), and foldl composes them starting from the left.
  That is, foldr , given the list [a₁,a₂,...,a_n] and initial value b, computes
  F_a1(F_a2(...(F_an(b))...)
  while foldl computes
  F_an(F_an-1(...(F_a1(b))...))
```
           fun foldr F y nil = y
           |   foldr F y (x::xs) = F(x, foldr F y xs) ;

           val foldr = fn : ('a * 'b) -> 'b -> 'b -> 'a list -> 'b
```

The structure List

Function List.take(L,i) returns the first i elements of the list L.

      List.take([1,2,3,4,5],3) ;
      val it = [1,2,3] : int list

List.drop(L,i) returns what is left when the first i elements are removed from list L.
```
 
      List.drop([1,2,3,4,5],3) ;
      val it = [4,5] : int list
```
Function List.nth(L,n) returns the nth element of list L, counting from 0 as the first element.
```
       List.nth([1,2,3,4,5],3) ;
       val it = 4: int
```
Function List.tabulate takes a pair consisting of an integer n and a function f that has an integer domain, and returns the list[f(0),f(1),f(2),...,f(n-1)] .
```
        List.tabulate(5, fn x => x*x) ;
        val it = [0,1,4,9,16] : int list
```
List.foldl , List.foldr
List.filter , list.all

examples

Set

fun empty(x) = if x = [] then true else false;

fun singleton (x)  = if x = [] then false 
                     else if tl(x) = [] then true 
                          else false ;

fun member(x,s) = if s = [] then false
                  else if x = hd(s) then true
                       else member(x,tl(s)) ;

fun insert(x,s) = if member(x,s) then s else x::s ;

fun delete(_,[]) = [] 
    | delete (x, y::ys) =
          if x = y then ys else y::delete(x,ys) ;

fun intersection(xs,ys) = List.filter (fn x =>member(x,ys)) xs ;


fun union(xs, ys) = List.foldl insert ys xs ;

fun diff(xs,ys) = List.filter(fn x => not (member(x,ys))) xs ;

fun distinct(xs) = if xs = [] then []
                   else if member(hd(xs),tl(xs))  then distinct(tl(xs))
                        else hd(xs)::distinct(tl(xs)) ;

fun union1(xs,ys) = List.foldr insert ys xs ;

fun subset(xs,ys) = List.all(fn x => member(x,ys)) xs ;

fun equal(xs , ys ) = subset(xs,ys) andalso subset(ys,xs) ;

fun insertAll(a,nil) = nil
     |   insertAll(a,L::Ls) = (a::L)::insertAll(a,Ls);
fun powerSet(nil) = [nil]
     |   powerSet(x::xs) =
             powerSet(xs)@insertAll(x,powerSet(xs));

Examples using reduce

fun reduce f  [] v = v 
        |   reduce f (a::y) v = f(a, reduce f y v) ;

fun length(x) = reduce (fn (_,y) => 1 + y) x 0 ;    

fun append(x,z) = reduce (fn(h,t)=>h::t) x z ;

fun remove_if f x = reduce (fn (h,x)=> if f(h) then t else (h::t)) x [] ;

fun map f x = reduce (fn(h,t)=> (f(h)::t)) x [] ;

Tail recursion

Add all the elements from a list

fun sum_aux(L,res) = if L = nil then res
                     else sum_aux(tl(L), res + hd(L)) ;

fun sumList_tr(L) = sum_aux(L,0) ;

Multiply all the elements in a list

fun mulList_aux(L,res) = if L = nil then res
                         else mulList_aux(tl(L), hd(L)* res) ;

fun mulList_tr(L) = mulList_aux(L,1) ;

factorial

fun fact1(n,result) = if n = 0 then result
                      else  fact1(n-1,n*result) ;
fun fact2(n) = fact1(n,1) ;

Fibonacci

fun fib_aux(n,fn1,fn2) = if n = 0 orelse n = 1 then n
            else if n = 2 then fn1 + fn2 
                    else fib_aux(n-1,fn1+fn2 , fn1) ;

fun fib_tr(n) = fib_aux(n,1,0) ;

Higher Order Function

map

reduce

filter

folding List

The structure List

examples