B: A brief review of SML

B.1: About the four main functional languages

B.2: Functions, pattern matching, and integers

SML n over m
(* over : int -> int -> int *)
fun over n 0 = 1
  | over n m = if n = m
                  then 1
                  else over (n-1) m + over (n-1) (m-1) ;
SML over curried
over (n-1) (m-1)
SML over uncurried
over(n-1,m-1)
SML n over' m
(* over' : int * int -> int *)
fun over'(n,0) = 1
  | over'(n,m) = if n = m
                    then 1
                    else over'(n-1,m) + over'(n-1,m-1) ;
SML over main
(* over_4_3,over_4_2 : int *)
val over_4_3 = over 4 3 ;
val over_4_2 = over 4 2 ;

B.3: Local function and value definitions

SML n over m with let
(* over : int -> int -> int *)
fun over n 0 = 1
  | over n m = if n = m
                  then 1
                  else let
                          val k = n-1
                       in
                          over k m + over k (m-1)
                       end ;

B.4: Reals, booleans, strings, and lists

SML locate element in list
(* locate : 'a -> 'a list -> bool *)
fun locate a []      = false
  | locate a (x::xs) = (a = x) orelse locate a xs ;
SML locate main
(* locate_nil,locate_bool,locate_int : bool *)
(* locate_char,locate_string,locate_real : bool *)
val locate_nil    = locate 2 [] ;
val locate_bool   = locate true [false,false] ;
val locate_int    = locate 2 [1,2,3] ;
val locate_char   = locate "x" ["a","b","c","d"] ;
val locate_string = locate "foo" ["foo","bar"] ;
val locate_real   = locate 3.14 [0.0, 6.02E23] ;
SML implode explode
(* true_explode,true_implode : bool *)
val true_explode = (explode "foo" = ["f","o","o"]) ;
val true_implode = (implode ["b","a","r"] = "bar") ;

B.5: Type synonyms and algebraic data types

SML type synonym for pair of integers
type int_pair = int * int ;
SML integer tree type
datatype int_tree = Int_Branch of int_tree * int_tree
                  | Int_Leaf of int ;
Miranda number tree type
num_tree ::= Num_Branch num_tree num_tree |
             Num_Leaf num ;
SML a sample integer tree
(* sample_int_tree : int_tree *)
val sample_int_tree
    = Int_Branch(Int_Leaf 1,
                 Int_Branch(Int_Leaf 2,Int_Leaf 3)) ;
SML walk and add integer tree
(* walk_add : int_tree -> int *)
fun walk_add (Int_Branch(left,right))
    = walk_add left + walk_add right
  | walk_add (Int_Leaf data)
    = data ;
SML add integer main
(* add_int_main : int *)
val add_int_main = walk_add sample_int_tree ;

B.6: Higher order functions

SML polymorphic tree type
datatype 'a tree = Branch of 'a tree * 'a tree
                 | Leaf of 'a ;
SML a sample integer instance of a polymorphic tree
(* sample_poly_tree : int tree *)
val sample_poly_tree
    = Branch(Leaf 1,
             Branch(Leaf 2,Leaf 3)) ;
SML polymorphic tree walk
(* poly_walk : ('a->'a->'a) -> 'a tree -> 'a *)
fun poly_walk comb (Branch(left,right))
    = comb (poly_walk comb left) (poly_walk comb right)
  | poly_walk comb (Leaf data)
    = data ;
SML polymorphic walk and add integer tree main
(* poly_add_int_main : int *)
val poly_add_int_main
    = let
         fun add x y = x+y
      in
         poly_walk add sample_poly_tree
      end ;
SML a sample string instance of a polymorphic tree
(* string_poly_tree : string tree *)
val string_poly_tree
    = Branch(Leaf "Good",
             Branch(Leaf "Bad",Leaf "Ugly")) ;
SML walk and concatenate string tree main
(* film : string *)
val film
    = let
         fun concat x y = x ^ " " ^ y
      in
         poly_walk concat string_poly_tree
      end ;

B.7: Modules

SML Tree structure
structure Tree = struct

   datatype 'a tree = Branch of 'a tree * 'a tree
                    | Leaf of 'a
                    | Empty ;

   (* empty : 'a tree *)
   val empty = Empty ;

   (* walk : ('a->'a->'a) -> 'a -> 'a tree -> 'a *)
   fun walk comb default (Branch(left,right))
       = comb (walk comb default left)
              (walk comb default right)
     | walk comb default (Leaf data)
       = data
     | walk comb default (Empty)
       = default

end ;
SML a sample real tree qualified
(* sample_real_tree : real Tree.tree *)
val sample_real_tree
    = Tree.Branch(Tree.Leaf 1.0,
                  Tree.Branch(Tree.Leaf 2.0,Tree.Leaf 3.0));
SML a sample real tree unqualified
(* sample_real_tree : real Tree.tree *)
val sample_real_tree
    = let
         open Tree
      in
         Branch(Leaf 1.0,
                Branch(Leaf 2.0,Leaf 3.0))
      end ;
SML walk and add real tree main
(* add_real_main : real *)
val add_real_main
    = let
         fun add x y = x+y
      in
         Tree.walk add 0.0 sample_real_tree
      end ;
SML TREE signature
signature TREE = sig
   datatype 'a tree = Branch of 'a tree * 'a tree
                    | Leaf of 'a
                    | Empty ;
   val empty : 'a tree ;
   val walk  : ('a->'a->'a) -> 'a -> 'a tree -> 'a
end ;
SML My Tree structure
structure My_Tree : TREE = Tree ;
SML Non Empty Tree structure
signature NON_EMPTY_TREE = sig
   datatype 'a tree = Branch of 'a tree * 'a tree
                    | Leaf of 'a
                    | Empty ;
   val walk : ('a->'a->'a) -> 'a -> 'a tree -> 'a
end ;

structure Non_Empty_Tree : NON_EMPTY_TREE = Tree ;

B.8: Libraries