Section Notes 3, Thursday, Jan 22, 2004

1. Office hours

2. Reduction, Maps, Filters

   You can go to: http://www.standardml.org/Basis/ to find information about the standard library. To look up a particular function, click on the "index" link at the bottom, and find your function for the appropriate structure.

   foldl and foldr are ways of making recursion simpler

   This is what you'll find in the documentation on www.smlnj.org:

   foldr f init [x1, x2, ..., xn]
   returns
   f(x1, f(x2, ..., f(xn, init)...))
   
   or init if the list is empty.
   

   
   val foo = "first"::"second"::"third"::nil;
   
   fun concat nil = ""
     | concat x = hd(x) ^ concat( tl(x) );
   
   fun concatReduceR x = foldr (op ^) "" x;
   concatReduceR foo;
   fun concatReduceL x = foldl (op ^) "" x;
   concatReduceL foo;
   
   

   More from the documentation:

   map f l
   applies f to each element of l from left to right, returning the list of results.

   List.find f l
   applies f to each element x of the list l, from left to right, until f x evaluates to true. It returns SOME(x) if such an x exists; otherwise it returns NONE.

   Note that you need to put List.filter instead of just filter because it's not a top-level function (you can check out the documentation to see which functions are and aren't)

   filter f l
   applies f to each element x of l, from left to right, and returns the list of those x for which f x evaluated to true, in the same order as they occurred in the argument list.

3. Equality types

   fun baz 3.2 = 0;
   fun baz' (a:real) = 0;
   

4. Polymorphic Type Inference

   fun foo (x,y) = x::y;
   foo ("barre", 4::5::nil); 
   
   
   
   fun salad (bar, green) = (bar, bar::green, (fn bar => bar + 3));
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   fun reverse nil result = result
     | reverse (x::xs) result = reverse xs (result::xs);
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   (*
   = stdIn:1.1-93.53 Error: right-hand-side of clause doesn't agree with function result type [circularity]
     expression:  'Z -> 'Z
     result type:  'Z list -> 'Z
     in declaration:
       reverse = (fn arg => (fn  => ))
   *)
   

   To help debug, ascribe.

   fun reverse (nil:'a list) (result:'a list) = result
     | reverse ((x::xs):'a list) (result:'a list) = reverse xs (result::x);
   
   (*
   = stdIn:94.61-94.72 Error: operator and operand don't agree [UBOUND match]
     operator domain: 'a list * 'a list list
     operand:         'a list * 'a
     in expression:
       result :: x
   *)
   

5. Supplemental Exercises from lecture notes 6

fun f a b = (a ^ ".", b);










fun g (c, d) = (f c c)::d;











fun m x nil = nil
  | m x (y::ys) = (x y)::(m x ys);










fun squid(a, b, c) =
    let val d = [2.0,3.0];
        val e:(int * (int * string)) = (3, c);
    in
        if a > hd(d) then [hd(b), #2(c)] else tl(b)
    end;



















(*
val f = fn : string -> 'a -> string * 'a
val g = fn : string * (string * string) list -> (string * string) list
val m = fn : ('a -> 'b) -> 'a list -> 'b list
val squid = fn : real * string list * (int * string) -> string list
val it = () : unit
*)