load "List" ; (* hanoi(n,from,via,to) TYPE: int * string * string * string -> string PRE: n >= 0 POST: description of the moves to be done for transferring n disks from tower from to tower to, using tower via *) (* VARIANT: n *) fun hanoi(0,from,via,to) = "" | hanoi(n,from,via,to) = hanoi(n-1,from,to,via) ^ from ^ "->" ^ to ^ " " ^ hanoi(n-1,via,from,to) (*======================== Sorting ========================*) (* split L TYPE: 'a list -> ('a list * 'a list) PRE: (none) POST: (A,B) such that A@B is a permutation of L, but A and B are of the same length, up to one element EX: split [5,7,3,12,1,7,2,8,13] = ([5,7,3,12], [1,7,2,8,13]) *) (* ALGORITHM: naive! *) fun split L = let val t = (length L) div 2 in (List.take (L,t), List.drop (L,t)) end (* merge L M TYPE: int list -> int list -> int list PRE: L and M are non-decreasingly sorted POST: a non-decreasingly sorted permutation of the list L@M EX: merge [3,5,7,12] [1,2,7,8,13] = [1,2,3,5,7,7,8,12,13] *) (* VARIANT: |L|*|M| *) fun merge [] M = M | merge L [] = L | merge (L as x::xs) (M as y::ys) = if x > y then y :: merge L ys else x :: merge xs M (* function sort L TYPE: int list -> int list PRE: (none) POST: a non-decreasingly sorted permutation of L EX: sort [5,7,3,12,1,7,2,8,13] = [1,2,3,5,7,7,8,12,13] *) (* ALGORITHM: merge sort *) (* VARIANT: |L| *) fun sort [] = [] | sort [x] = [x] | sort xs = let val (ys,zs) = split xs in merge (sort ys) (sort zs) end (* partition(p,L) (* p is called the 'pivot' *) TYPE: int * int list -> int list * int list PRE: (none) POST: (S,B) where S has all x

=p of L EX: partition(5,[7,3,12,1,7,2,8,13])=([3,1,2],[7,12,7,8,13]) *) (* VARIANT: |L| *) fun partition (p,[]) = ([],[]) | partition (p,x::xs) = let val (S,B) = partition (p,xs) in if x < p then (x::S,B) else (S,x::B) end (* SPECIFICATION: same as for sort above *) (* ALGORITHM: quicksort *) (* VARIANT: |L| *) fun sort1 [] = [] | sort1 (x::xs) = let val (S,B) = partition (x,xs) in (sort1 S) @ (x :: (sort1 B)) end local (* sort' L A TYPE: int list -> int list -> int list PRE: (none) POST: (a non-decreasingly sorted permutation of L) @ A EX: sort' [5,7,3,12] [1,4,2,3] = [3,5,7,12,1,4,2,3] *) (* ALGORITHM: quicksort *) (* VARIANT: |L| *) fun sort' [] A = A | sort' (x::xs) A = let val (S,B) = partition (x,xs) in sort' S (x :: (sort' B A)) end in (* SPECIFICATION: same as for sort above *) fun sort2 L = sort' L [] end