Script 5, 4/9/2010

0. Some more basic ideas

(a) Mutually recursive functions

   fun f(...) = ... f ... g ...
   and g(...) = ... g ... f ...

   e.g. even and odd:

   fun even 0 = true
     | even n = odd (n-1)
 
   and odd 0 = false
     | odd n = even (n-1)

(b) Higher-order functions
   function composition
   
     val op o = fn (f,g) = (fn x => f(g x));
        o : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b

   curry, uncurry

     fun curry f = fn x => fn y => f(x,y)
     fun curry f x y = f(x,y)
     val curry = fn : ('a * 'b -> 'c) -> 'a -> 'b -> 'c

     fun uncurry f = fn (x,y) => f x y
     fun uncurry f (x,y) = f x y
     val uncurry = fn : ('a -> 'b -> 'c) -> 'a * 'b -> 'c
    
   list functionals : map, foldl(r), filter, exists, etc.

     fun map f nil = nil | map f (x::xs) = f x :: map f xs
     val  map = fn : ('a -> 'b) -> 'a list -> 'b list

     - map Int.toString [1,2,3];
     val it = ["1","2","3"] : string list

     fun foldl f b nil = b
       | foldl f b (x::xs) = foldl f (f x b) xs
  
     val foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

     - foldl (op ::) nil [1,2,3];
     val it = [3,2,1] : int list

     - foldr (op ::) nil [1,2,3];
     val it = [1,2,3] : int list

     - foldl (op +) 0 [1,2,3];
     val it = 6 : int

  functional environments
   fun empty (s: string) = raise Fail "empty"
   
   fun bind (s, v, env) = fn s' => if s' = s then v else env s'

   fun lookup (s, env) = env s

   [functional objects]


(c) Tail recursive functions, accumulator arguments

   fun rev nil = nil
     | rev (x::xs) = rev xs @ [x]

   -- quadratic cost!

   fun rev1(nil, ys) = ys
     | rev1(x::xs, ys) = rev1(xs, x::ys)

   fun rev xs = rev1(xs,nil)

   -- linear cost and tail recursive!


1. equality

* equality types
  1. structural equality -- defined on a family of types
    primitive types, tuples and records, "concrete" datatypes
  
    - 1 = 3;
    val it = false : bool

    - "abc" = "a"^"bc";
    val it = true : bool

    - (2,true) = (2,true);
    val it = true : bool

    - [1,3,5] = rev [5,3,1];
    val it = true : bool

    - datatype 'a tree = Lf | Br of 'a * 'a tree * 'a tree;
    datatype 'a tree = Br of 'a * 'a tree * 'a tree | Lf

    - Lf = Lf;
    stdIn:18.4 Warning: calling polyEqual
    val it = true : bool

    - Br(3,Lf,Lf) = Br(3,Lf,Lf);
    val it = true : bool

  but function types are not included:

    - fun foo x = x;
    val foo = fn : 'a -> 'a

    - foo = foo;
    stdIn:22.1-22.10 Error: operator and operand don't agree [equality type required]
      operator domain: ''Z * ''Z
      operand:         ('Y -> 'Y) * ('X -> 'X)
      in expression:
        foo = foo

  2. pointer equality on refs and arrays (values with state)

    - ref 3 = ref 3;
    val it = false : bool


* equality polymorphism
  member example

   fun member (x, nil) = false
     | member (x, y::ys) = if x = y then true else member(x, ys)
   val member = fn : ''a * ''a list -> bool

  ''a is an equality type variable.  It ranges not over all
  types, but only over "equality types"


------------------------------------------------------------------
Effects in SML

1. exceptions
   - type safe
   - raise, handle
     exn type, exception constructors
     dynamically scoped handlers

   - exception safety?


2. State (ref, array)
   counter
   graph representation (cyclic)