Lecture 2

---
Administrative

 - TA's office hours and place
   o Wed. 12:00-2:00pm, 051 East Main St., Room 005

 - Before the class bulletin board is cgi enabled, you can not post 
   anything there; It's for me to post announcements or some of the emails 
   (Q&A about assignments) between us that I consider are of common 
   interests to the whole class. 

 - Access ML?
   o your acad account to access SML         

 - any feedback so far ?


--- 

Core ML (continued)

> (* comments are enclosed by (* *) and may be nested like this one *)

> Pattern matching

  - fun fact 0 = 1 
      | fact n = n * fact(n-1)

  - fun fact n = if n=0 then 1
      else n * fact(n-1)

 The conditional expression "if E then E1 else E2"
 abbreviates the the function application
   (fn true => E1 | false => E2 ) (E)

 Wild cards are often useful (at lease save naming space) in pattern matching.

 - fun first (x, y) = x;
 val first = fn : 'a * 'b -> 'a

 - first (x, _) = x;
 val first = fn : 'a * 'b -> 'a

 Two occurrences of a wildcard are treated distinctly in type.

 - middle (_, x, _) = x;

 val middle = fn : 'a * 'b * 'c -> 'b
 instead of
 val middle = fn : 'a * 'b * 'a -> 'b


> List

 1) empty list   [], or nil, is just syntax sugar
 2) [1,2,3]
    1::2::3::nil
  
   :: cons may be considered as a function tacking two arguments, 
   one element and one list.

 e.g.,

 - fun length [] = 0
    |  length (x::xs) = 1 + length xs;

   val length = fn: 'a list -> int

 This is one application of polymorphism: you don't have to say what kind of list
 your function length takes as argument.


> Type declaration

  - int list

  inside a list every element must be of the same type.

 e.g., 

 - fun append [] ys = ys
    |  append (x::xs) ys = x :: append xs ys

 Note: SML has a built-in infix operator @ for appending lists. 

 - [1, 2] @ [3, 4];
 val it = [1, 2, 3, 4] : int list


> Functionals (higher-order functions)

 Take functions as arguments

 e.g., 

 - fun compose (g, f) = fn x => g (f x);
 val compose = fn : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b

 - val second = compose (hd, tl)
 val second = fn : 'a lisi -> 'a

 One useful functional on lists
 - fun map f [] = []
     | map f (x::xs) = f x :: map f xs

   val map = fn: ('a -> 'b) -> 'a list -> 'b list

 here is an application of function "map":

 - map (add 2) [1,2,3]
   
   val it = [3,4,5] : int list

 argument types for function map when applied to (add 2) is
  (int -> int) -> int list -> int list

 Another useful functional on lists

 - fun foldr f c [] = c
     | foldr f c (x::xs) = f(x, foldr f c xs)
                                      ^
                                      |
                                      this f must be in un curried version

 What foldr does is to try to implement generalization form such as
  from single +  to summing over a list, when f is +

 Here is an example of using foldr to define other functions

 - fun cons (x, xs) = x::xs

 - fun append xs ys =
        foldr cons ys xs

 Another example:

 - fun inc (x, n) = 1 + n;
 
 - fun length xs = foldr inc 0 xs

 Exercise: What is the type of foldr? 


 Function that you pass as argument to foldr has to be 
 in uncurried version

 Historical reason:
  val sum = foldr (op +) 0

 where + is a infix function

 foldr (op +) 0 [1,2,3]
  1+(2+(3+0))

 foldl
  ((0+1)+2)+3

 Excise: write code for functin foldl

 - fun inc (x, n) = 1+n

 -  val length = foldr inc 0

 To save name space, ML allows anonymous function. So you do not have 
 to define a helper function "inc". (recall "Lambda" terms in scheme). 
 Function length can then be defined as,

 - fun length xs = foldr (fn (x,n) => 1+n) 0 xs;

 A function to convert a function from curried verion 
 into uncurried version

 - fun uncurry f = fn (x,y) => f x y;

  Exercise: what is the type for "uncurry"

 Note: Thinking of a function by its type often helps you to write the function. 

 Excise: write an inverse function of uncurry, namely, a function to convert
        a function from uncurried version into curried version.