Answers to SML Exercises


1) identity: 'a -> 'a


2) Hot(true), Hot(false), Cold(5), etc.


3) a) hot_maker : 'a -> bool_or_int

   b) Hot: bool -> bool_or_int


4) [Defined only for n > 0]

    fun sum (1: int) = 1 
      | sum n = n + addints(n-1) 
 


5) This causes a syntax error because declarations separated by the
keyword "and" must be of the same kind (e.g. both val, both fun, both
datatype, or both exception declarations). Here SML expects to find
another function declaration after the "and", starting with keyword
"fun", but instead it discovers the keyword "val" indicating a general
value declaration.  Note also that function declarations separated by
"and" can be mutually recursive (see the even/odd example in Exercise
8 below).


6) fun intmax (x,y) =  if x > y then x  else y;


7a) [defined only for x > 0]

   fun power_of_two 1 = true
     | power_of_two x =
        (x mod 2 = 0) andalso power_of_two (x div 2);

7b) power_of_two 8 => (8 mod 2 = 0) andalso power_of_two 4
    =>  (0=0) andalso power_of_two 4
    => 	true andalso power_of_two 4
    =>  power_of_two 4
    =>  (4 mod 2 = 0) andalso power_of_two 2
    =>  (0=0) andalso power_of_two 2
    => 	true andalso power_of_two 2
    =>  power_of_two 2
    =>  (2 mod 2 = 0) andalso power_of_two 1
    =>  (0=0) andalso power_of_two 1
    => 	true andalso power_of_two 1
    =>  power_of_two 1
    =>  true
	

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


9) 7, 8, 8, and 2.


10) [assume second argument is sorted in ascending order]

    (* insert : int -> int list -> int list *)
    fun insert n [] = n :: nil
      | insert n (x::xs) = 
        if (n > x) then x::(insert n xs) else n::x::xs;


11) This version of insertion_sort is polymorphic, and can sort lists
    of any type 'a provided a comparison function for 'a is supplied
    as the first (curried) argument.

    (* insertion_sort : ('a * 'a -> order) -> 'a list -> 'a list *)
    fun insertion_sort _ [] = []
      | insertion_sort cmp (x::xs) = insert cmp x (insertion_sort cmp xs)

    (* insert : ('a * 'a -> order) -> 'a -> 'a list -> 'a list *)
    and insert _ x [] = [x]
      | insert cmp x (l as y::ys) =
        (case cmp (x, y)
	   of GREATER => y :: insert cmp x ys
            | _       => x :: l);

12) 


13) val C = fn : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b


14) a) val newfunc = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
    b) foldl


15a) datatype COORDS = Cords of real * real * real; 

15b) val p1 = Cords(1.2,3.4,0.0);

15c) 
    fun square (x:real) = x * x;

    fun distance (Cords(x1,y1,z1):COORDS) (Cords (x2,y2,z2):COORDS) =
        Math.sqrt(square(x2-x1) + square(y2-y1) + square(z2-z1));

15d) distance (Cords(1.2,2.6,4.5)) (Cords (2.3,4.7,7.7));


16) datatype PERSON = P of {name: string, fname: string, age:int, dob:int};


17a) val i = ref 10; 
17b) inc(i);
17c) dec(i);
17d) i := 20; 


18) [defined only for n >= 0]

    fun fib 0 = 0	
      | fib 1 = 1
      | fib n = fib(n - 1) + fib(n-2);


19) 
    fun sign i = 	
        if i > 0 then 1	
        else if i < 0 then ~1
        else 0;

    fun sign i =
        case Int.compare(i,0)
          of LESS => ~1
           | EQUAL => 0
           | GREATER => 1
          


20) 
    fun cube(n) = n * n * n;         (* cube: int -> int *)

    fun cube(x: real) = x * x * x;   (* cube : real -> real *)

    fun cube(x) = Math.pow(x, 3.0);  (* cube : real -> real *)


21a) 

    fun sumodd [] = 0
      | sumodd (x::xs) =
          if odd x then x + sumodd xs else sumodd xs; 

    fun sumodd xs =
        foldl (fn (x,s) => if odd x then x+s else s) 0 xs;

21b)

    fun sump p [] = 0
      | sump p (x::xs) =
          if (p x) then x + (sump p xs) else sump p xs; 

    fun sump p xs =
        foldl (fn (x,s) => if p x then x+s else s) 0 xs;


21c)

    fun notsump p [] = 0
      | notsump p (x::xs) =
          if (p x) then (notsump p xs) else x + (notsump p xs); 

    fun notsump p xs = sump (not o p) xs;

    fun notsump p = sump (not o p);


22a)

    fun isVegan (Vgn _) = true
      | isVegan _ = false;

    fun getVegan [] = []
      | getVegan (x as Vgn _ :: xs) = x :: getVegan xs
      | getVegan (_ :: xs) = getVegan xs

    (* or, if you know the List library module *)
    val getVegan = List.filter isVegan
    (* getVegan : item list -> item list *)

22b)

    fun isOmn (Omn _) = true
      | isOmn _ = false

    (* cheapest_omn : item list -> item option *)
    fun cheapest_omn items =
        let fun scan (item0 as Omn(name0,price0), ((item as Omn(name,price))::rest) =
                if price < price0 then scan(item, rest)
		else scan(item0, rest)
              | scan (item, nil) = item
         in case List.filter isOmn items
              of nil => NONE
               | item::items = SOME(scan(item, items))
        end

22c) 
    fun item_name (Vgn(name,_)) = name
      | item_name (Vgt(name,_)) = name
      | item_name (Omn(name,_)) = name

    fun item_price (Vgn(_, price)) = price
      | item_price (Vgt(_, price)) = price
      | item_price (Omn(_, price)) = price

    (* lookup_price : string * item list -> real option *)
    fun lookup_price(name, items) =
        case List.find (fn item => item_name item = name) items
          of NONE => NONE
           | SOME item => SOME(item_price item)

22d)
    type order = string * int

    (* order_cost : item list -> order -> real option *)
    fun order_cost menu (name, number) =
        case lookup_price(name, menu)
	  of NONE => NONE
           | SOME p => SOME(Real.fromInt number * p)

22e)
    (* orders_cost : item list -> order list -> real option *)
    fun orders_cost menu orders =
        let fun loop (NONE::_, c) = NONE
              | loop (SOME icost :: rest, c) = loop(rest, iconst+c)
              | loop (nil, c) = SOME c
         in loop(map (order_cost menu) orders, 0.0)
        end