(* George Tzanetakis *) 
(* Part 1 *) 

fun nth ([],_) = raise Subscript 
  | nth ((l::ls), 0) = l 
  | nth ((l::ls), n) = nth(ls,n-1);

fun copy(0,ls) = [] 
  | copy(k,ls) = ls @ copy(k-1,ls);

fun scanl f b [] = [b] 
  | scanl f b (x::xs) = b :: scanl f (f(b,x)) xs

fun minl []  = raise Subscript
  | minl [x] = x
  | minl (m::n::ns) = if (m < n) then minl(m::ns)
		      else minl(n::ns)		      

fun maxl [] = raise Subscript
  | maxl [x] = x
  | maxl (m::n::ns) = if (m > n) then maxl(m::ns)
		      else maxl(n::ns)		      

fun tabulate(i,j) = if (i > j) then [] else i::tabulate(i+1,j)

fun member [] x     = false
  | member (y::ys) x  = x=y orelse member ys x

fun filter p [] = [] 
  | filter p (y::ys) = if (p(y)) then y::(filter p (ys)) else (filter p ys);

(* Part 2 *) 

val units = ["one", "two", "three", "four", "five", 
"six", "seven", "eight", "nine"];

val teens = ["ten", "eleven", "twelve", "thirteen", 
             "fourteen", "fifteen", "sixteen", "seventeen", 
             "eighteen", "nineteen"];

val tens = ["twenty", "thirty", "forty", "fifty", 
            "sixty", "seventy", "eighty", "ninety"];

fun digits2 n  = (n div 10, n mod 10)
fun digits3 n  = (n div 100, n mod 100)
fun digits6 n =  (n div 1000, n mod 1000) 

(* numbers <100 *) 
fun combine2(0,u)  = [nth(units, u-1)]
  | combine2(1,u)  = [nth(teens, u)]
  | combine2(t,0)  = [nth(tens, t-2)]
  | combine2(t,u)  = [nth(tens, t-2)] @ ["-"] @ [nth(units,u-1)];
fun convert2 n = combine2(digits2 n)

(* numbers < 1000 *) 
fun combine3(0, t) = convert2(t)
  | combine3(h, 0) = [nth(units,h-1)] @ [" hundred"]
  | combine3(h, t) = [nth(units,h-1)] @ [" hundred and "] @ convert2(t)
fun convert3 n = combine3(digits3 n)

fun link h = if (h < 100) then [" and "] else [" "]

(* handles everything *) 
fun combine6(0, h) = convert3(h)
  | combine6(m, 0) = convert3(m) @ [" thousand"] 
  | combine6(m, h) = convert3(m) @ [" thousand"] @ link(h) @ convert3(h) 

fun convert6 0 = ["zero"] 
  | convert6 n = combine6(digits6 n)

fun num2String(n) = foldr op^ "" (convert6(n));

(* Part 3 *) 
type polynomial = int list 		(* list of polynomial coefficients *)

fun multC([],c) = []
  | multC(p::ps:polynomial,c:int) = p*c::multC(ps,c)

fun multX (p:polynomial) = 0::p;
                               
infix 5 ++  				(* polynomial addition *)
infix 8 ** 				(* polynomial multiplication *)

fun [] ++ (y:polynomial) = y
  | (x:polynomial) ++ [] = x
  | (x::xs:polynomial) ++ (y::ys:polynomial) = (x+y)::(xs ++ ys);

fun [] ** (y:polynomial) = []
  | (x:polynomial) ** [] = [] 
  | (x::xs:polynomial) ** (y::ys:polynomial) = multC(y::ys,x) ++ multX(xs ** (y::ys));


fun p2string (p:polynomial) = let val (l::ls) = rev(p)
                                  val deg = length(ls) 
				  fun term1(0,_) = "" 
				    | term1(x,0) = Int.toString(x) 
                                    | term1(1,1) = "x"
				    | term1(1,d) = "x^" ^ Int.toString(d) 
				    | term1(x,1) = Int.toString(x) ^ "x" 
				    | term1(x,d) = Int.toString(x) ^ "x^" ^ Int.toString(d) 
                                  fun term2(0,_) = ""
				    | term2(x,d) = " + " ^ term1(x,d) 
                                  fun p2straux([],d) = ""
				    | p2straux(x::xs,d) = term2(x,d) ^ p2straux(xs,d-1) 
                              in 
				  term1(l,deg) ^ p2straux(ls,deg-1)  
			      end

(* Part 4 *) 

type direction = int 
type pen   = bool
type point = int * int
type state = direction * pen * point
type command = state -> state
type turtle  = command list -> state list

(* functions for manipulating state *) 
fun move ((0,p,(x,y)):state) = (0,p,(x+1,y)):state
  | move (1,p,(x,y)) = (1,p,(x,y+1))
  | move (2,p,(x,y)) = (2,p,(x-1,y))
  | move (3,p,(x,y)) = (3,p,(x,y-1))
  | move (_,p,(x,y))     = (0,p,(x,y))

fun right ((d,p,(x,y)):state) = ((d-1) mod 4,p,(x,y)):state
fun left  ((d,p,(x,y)):state) = ((d+1) mod 4,p,(x,y)):state
fun up    ((d,p,(x,y)):state) = (d, false, (x,y)):state 
fun down  ((d,p,(x,y)):state) = (d, true, (x,y)):state

(* convert list of commands to trail of points *) 
fun turtle (cs:command list):state list = 
    scanl (fn(x,f) => f x) (0, false, (0,0)) cs; 

(* convert list of states to trail of points *) 
fun trail (ts:state list) = let val downstates = 
                                filter (fn(_,x,_)=>x) ts 
                            in 
                                map (fn(_,_,(x,y))=>(x,y)) downstates
			    end;

(* create 2D bitmap from trail of points *) 
fun range xs = tabulate(minl(xs),maxl(xs));
fun bitmap ps = let val xran = range(map (fn(x,y)=>x) ps)
                    val yran = range(map (fn(x,y)=>y) ps)
	        in 
		    map (fn y=> map (fn x => (member ps (x,y))) xran) yran
		end

(* convert 2D grid of bools to 2D grid of chars *) 
fun bool2char false = " "  
  | bool2char true  = "o" 

fun symbolizef f bbs = map (fn bs=>map f bs) bbs
fun symbolize bbs = symbolizef bool2char bbs

(* convert 2D grid of characters to string representation *) 

fun layout sss = let 
                     fun l2string ls = (foldr (op^) "" ls);
	         in 
                     l2string (map (fn x=>x^"\n") (map l2string sss))
                 end

(* print the turtle path based on a sequence of commands *) 
fun printTurtle p = (print o layout o symbolize o bitmap o trail o turtle) p

(* some testing functions *) 
fun square k = let val side = copy(k-1,[move])@[right] 
               in [down] @ copy(4,side) @ [up] end;
fun diagonal k = let val d = [move] @ [left] @ [move] @ [right] 
                 in [down] @ copy(k, d) @[up] end;