signature List= 
sig
 val empty : int list->bool;
 val head : int list-> int
 val tail : int list-> int list;
 val attach: int * int list-> int list;
 val length: int list -> int;
 val max : int list->int;
 val append : int list* int list-> int list;
 val reverse : int list-> int list;
 val insert : int * int list-> int list;
 val insort : int list-> int list;
 val msort : int list-> int list;
 val qsort : int list-> int list;
end;

structure LIST1: List=
struct

exception emptylist;

fun empty([]) = true
  | empty(x::xs) = false;

fun head([]) = raise emptylist
  | head(x::xs) = x;

fun tail([]) = raise emptylist
  | tail(x::xs) = xs;

fun attach(x,xs) = x::xs;

fun length([]) = 0
  | length(x::xs) = 1+length(xs);

fun len(ls) =
  let
	fun iter(ls,i) =
	  if empty(ls) then i
          else iter(tail(ls),i+1)
  in
	iter(ls,0)
  end;

fun max([]) = raise emptylist
  | max([x]) = x
  | max(x::ls) =   
 	let
		val y = max(ls)
	in
		if (x > y) then x else y
	end;

fun append([],l2) = l2
  | append(x::ls,l2) =  x::append(ls,l2)

fun reverse([]) = []
  | reverse(x::ls)  =     append(reverse(ls),[x])


fun rev(ls) =
  let
	fun iter([],revlist) = revlist
          | iter(x::xs,revlist) = iter(xs,x::revlist)
  in
        iter(ls,[])
  end;

fun insert(x,[]) = [x]
  | insert(x,y::ys) =
            if (x < y) then x::y::ys
            else y::insert(x,ys);

fun insort([]) = []
  | insort(x::xs) = insert(x,insort(xs));

fun insort_i(ls) =
  let 
      fun insort_iter([], result) = result
         | insort_iter(x::ls, result) = insort_iter(ls, insert(x, result));
   in
     insort_iter(ls, [])
end;

fun msort([])  = []
  | msort([x]) = [x]
  | msort(ls) =
       let
          fun split(ls) =
            let
               fun split_iter([],l1,l2,i) = (l1,l2)
                 | split_iter(x::xs,l1,l2,i) =
                      if (i mod 2 = 0) then
				split_iter(xs,x::l1,l2,i+1)
                      else      split_iter(xs,l1,x::l2,i+1)
            in
                split_iter(ls,[],[],0)
            end;
          val (l1,l2) = split(ls);
          fun merge([],l2) = l2
            | merge(l1,[]) = l1
            | merge(x::xs,y::ys) =
                     if (x <= y) then x::merge(xs,y::ys)
                     else y::merge(x::xs,ys)       
       in
          merge(msort(l1),msort(l2))
       end;

fun filter pred [] = []
  | filter pred (x::xs) =
    if pred(x) then x::(filter pred xs)
    else (filter pred xs);

fun qsort([]) = []
  | qsort(x::xs) = 
	let 
		fun comp opr x y = opr(y,x):bool;
	in
		append(qsort(filter (comp op<= x) xs), x::qsort(filter (comp op> x) xs))
      end;

end;