(* This is set so that we can see datatype terms fully *)

val _ = (Control.Print.printDepth := 100)

fun downFrom 0 = nil
  | downFrom n = n :: (downFrom (n-1))

(* map : ('a -> 'b) -> 'a list -> 'b list *)
fun map f nil     = nil
  | map f (x::xs) = (f x) :: (map f xs)

val alts = map (fn x => x mod 2 = 0) (downFrom 6)

(* foldr : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b *)
fun foldr oper bv nil = bv
  | foldr oper bv (h::t) = oper (h, foldr oper bv t)

fun factorial n = foldr (op*) 1 (downFrom n)

val onetwenty = factorial 5

fun doesSomething xs = foldr (op::) nil xs

fun foldlq oper bv nil = bv
  | foldlq oper bv (h::t) = foldlq oper (oper (h,bv)) t

(* foldl : ('b * 'a -> 'b) -> 'b -> 'a list -> 'b *)
fun foldl oper bv nil = bv
  | foldl oper bv (h::t) = foldl oper (oper (bv,h)) t;

fun doesSomethingElse xs = foldl (fn (l,e) => e::l) nil xs

val ds  = doesSomething [1,3,6,8]
val dse = doesSomethingElse [1,3,6,8]

(* filter : ('a -> bool) -> 'a list -> 'a list *)

fun filter p xs = if null xs then nil
                  else if p (hd xs)
		  then (hd xs)::(filter p (tl xs))
		  else (filter p (tl xs))

val fl =  filter (fn x => x mod 2 = 0) [1,4,4,0,3,2,1,2]

fun filterp p nil    = nil
  | filterp p (h::t) = if p h then h::(filterp p t)
                              else filterp p t

val flp =  filterp (fn x => x mod 2 = 0) [1,4,4,0,3,2,1,2]


(* Syntax for datatype definition 

datatype NewType =     
    constructor-1 of type-tuple-1
  | constructor-2 of type-tuple-2
  | constructor-3 of type-tuple-3
  ...
  | constructor-k of type-tuple-k

*)

(* series of cases...
   union of variants ...
   disjoint union of several (tuple) types ...

   algebraic datatypes
 *)


(* Here is my own version of "int list". *)

datatype MyIntList =
   EmptyIntList of unit
 | LargerIntList of int * MyIntList

val count1to3 = LargerIntList (1, LargerIntList (2, LargerIntList (3, EmptyIntList ())))

fun mapMIL f (EmptyIntList ()) = EmptyIntList ()
  | mapMIL f (LargerIntList (a,bs)) = LargerIntList (f a, mapMIL f bs)
(* Here is my own version of "'a list". *)

datatype 'a MyList =
   E
 | L of 'a * ('a MyList)

fun mymap f E          = E
  | mymap f (L (x,xs)) = L (f x, mymap f xs)

fun mymaptoo f ml =
    case ml of
         E => E
       | (L (x,xs)) => L (f x, mymaptoo f xs)

val myOneTwoThree = L (1, L (2, L (3, E)))
val twoTrue = L (true, L (true, E))
val my1 = mymap (fn x => x*x) myOneTwoThree
val my2 = mymaptoo not twoTrue

(* here is a binary search tree definition (with integer keys) *)

datatype intBST =
    Leaf
  | Branch of int * intBST * intBST

fun contains v Leaf = false
  | contains v (Branch (k,l,r)) =
      if v = k then true
      else if v < k
      then contains v l
      else contains v r

(* withAlso : int -> intBST -> intBST *)
fun withAlso v Leaf = Branch (v,Leaf,Leaf)
  | withAlso v (t as (Branch (k,l,r))) = 
      if v = k then t
      else if v < k then (Branch (k, withAlso v l, r))
                    else (Branch (k, l, withAlso v r))

local
  fun buildWith' nil t     = t
    | buildWith' (k::ks) t = buildWith' ks (withAlso k t)
in
  fun buildWith keys = buildWith' keys Leaf
end

val tree = buildWith [3,5,1,7,8,9,2]

datatype arith =
    Num of int
  | Var of string
  | Negate of arith
  | Plus of arith * arith
  | Times of arith * arith

val MinusThreeTimesTwoPlusX = Plus (Times (Negate (Num 3), Num 2), Var "x")