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