(* Code for Lecture 2: Datatypes                         *)

(************************************************************************)

(* Datatypes (non-recursive) *)

(* suit of cards *)
datatype suit = Clubs | Spades | Hearts | Diamonds

(* val dom : suit*suit -> bool

   dom(s1,s2) = true iff suit s1 beats or is equal to suit s2
                relative to the ordering S > H > D > C
   Invariants: none
   Effects: none
*)

fun dom(Spades:suit, _:suit):bool = true
  | dom(Hearts:suit, Diamonds:suit):bool = true
  | dom(Hearts:suit, Clubs:suit):bool = true
  | dom(Diamonds:suit, Clubs:suit):bool = true
  | dom(s1:suit, s2:suit):bool = (s1 = s2);

(* rank of cards *)
datatype rank =
 Two | Three | Four | Five | Six | Seven | Eight | Nine | Ten |
 Jack | Queen | King | Ace;

(* A card is a rank and a suit *)

type card = rank*suit

(* A hand is either empty or
   it consists of a card followed by the rest of the hand *)

(* Data-type (recursive!) *)
datatype hand = Empty | Hand of card * hand;

(* Some sample hands: *)

val hand0:hand = Empty;
val hand1:hand = Hand((Ace, Hearts), Empty);
val hand2:hand = Hand((Queen, Diamonds), hand1);
val hand5:hand = Hand((Ace, Spades),
                      Hand((Ten, Diamonds),
                           Hand((Seven, Clubs),
                               Hand((Queen, Spades),
                                   Hand((Eight, Clubs), Empty)))));


(* val extract : (suit*hand) -> hand
   extract(s, h) returns a hand consisting of all card in h of suit s.
   Invariants: none
   Effects: none
*)

fun extract (s:suit, Empty:hand):hand = Empty
  | extract (s:suit, Hand((r', s'), h'):hand):hand =
       if s = s' then Hand((r',s'), extract(s, h'))
       else extract(s, h');

(* extract all spades from hand5 *)
val spades5:hand = extract(Spades, hand5);


(* val count: hand -> int
   count(h) counts the number of cards in a hand h

*)

fun count (Empty) = 0
  | count (Hand(c, h)) = count(h) + 1


(************************************************************************)
(* Lists *)

(* Here is how one might define lists of elements of the same type: *)

datatype 'a mylist = Nil | Cons of 'a * 'a mylist;

(* Some sample values: *)

val list0 : int mylist = Nil;
val list1 : int mylist = Cons(1, Nil);
val list2 : int mylist = Cons(2, Cons(1, Nil));
val list3 : int mylist = Cons(3, list2);

val lst0 : real mylist = Nil;
val lst1 : real mylist = Cons(3.1, Cons(2.6, lst0));


(* And using the predefined ML lists, we have these values: *)

val rlist1 : real list = [3.1, 2.6, 7.8];
val rlist2 : real list = 8.6::5.4::nil;


(* val append: 'a list * 'a list -> 'a list
       append(l1, l2) returns a list consisting of the elements of l1
                      followed by the elements of l2.
   Invariants: none
   Effects: none

   NOTE:  This operation is defined in ML's Standard Basis
          via the right-associative infix operator "@".

   Observe that the running time is proportional to the length
   of the first argument.
*)

fun append(nil   : 'a list, l : 'a list) : 'a list = l
  | append(x::l' : 'a list, l : 'a list) : 'a list = x::append(l', l);


val app12  : real list = append(rlist1, rlist2);
val app12' : real list = rlist1 @ rlist2;


(* Remark : Writing functions without pattern matching
            *** Old style ***
            This requires to write first functions which
	    allow us to take apart lists.
*)

(* head: 'a list -> 'a

   Note: head may be undefined for the empty list
*)
fun head(h::t) = h

(* tail: 'a list -> 'a list *)
fun tail nil = nil
  | tail(h::t) = t


(* ************************************************************* *)
(* Handling undefined cases *)

datatype 'a option = NONE | SOME of 'a

(* Note that the optional datatype is non-recursive but parametric *)

fun headOpt nil = NONE
  | headOpt (h::t) = SOME h



(* ************************************************************* *)
fun app(l1, l2) =
  if l1 = nil then l2
    else
      head(l1)::(app(tail(l1), l2))



(* Here is a function that reverses a list.
   For example,   rev [1, 2, 3, 4] ==> [4, 3, 2, 1].

   The code below is extremely inefficient.
   Can you see why?
   Next lecture we will see a more efficient implementation.


   val rev : 'a list -> 'a list
       rev(l) returns a list consisting of the elements of l in reverse order.
   Invariants: none
   Effects: none

*)

fun rev(nil : 'a list) : 'a list = nil
  | rev(x::l) = (rev l) @ [x];


(* What is the tail-recursive version of this? *)

fun rev'(l) =
  let
    fun rev_tr(nil, acc) = acc
      | rev_tr(h::t, acc) = rev_tr(t, h::acc)
  in
    rev_tr(l, [])
  end

(************************************************************************)