CS代写 i(* Code for Lecture 3: Datatypes *)

i(* Code for Lecture 3: Datatypes *)

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

Copyright By PowCoder代写 加微信 powcoder

(* Datatypes (non-recursive) *)

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

(* We can extend the pre-defined types of int, float, char, string, etc.
with user-defined types.

Here declare a collection of elements belonging to the type suit;
we also say Clubs, Spades, Hearts, and Diamonds inhabit the type suit.
Often, we simply say Clubs (Spades, Hearts, Diamonds) *is* of type suit.

– the order in which we declare these elements does not matter
– Elements (= constructors) Need to begin with a capital letter
– Taking apart elements of a type is done by pattern matching
using the expression

match with
| ->
| ->
| ->

(* 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

let rec dom (s1, s2) = match (s1, s2) with
| (Spades, _) -> true
| (Hearts, Diamonds) -> true
| (Hearts, Clubs) -> true
| (Diamonds, Clubs) -> true
| (s1, s2) -> s1 = s2

– Allow pattern matching on the possible elements of a type
– Allows deep pattern matching
– Wildcard _ matches anything
_ (s1, s2) is a generic pattern which matches anything, but
we have names, namely s1 and s2, to refer to the parts of the tuple.
– All variables in a pattern must be distinct;
i.e. (s1, s1) is not a valid pattern.

(* rank of cards *)
type 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

(* Recursive Data-type *)
(* Let’s define the collection of cards in my hand. We want to define
it in such a way, that it can describe the fact that I have
2 cards in my hand, 77 cards in my hand, or no card at all in my hand.

We will define it recursively:

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

More precisely, we can define the elements of type hand as follows:
– Empty is of type hand
– If c is a card and h is of type hand
then Hand (c, h) is of type hand.
– Nothing else is of type hand.

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

(* Empty and Hand are constructors. They allow us to construct
an element of type hand.

(* Some sample hands: *)

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

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

let rec extract (s:suit) (h:hand) = match h with
| Empty -> Empty
| Hand ((r’, s’), h’) ->
if s = s’ then Hand((r’,s’), extract s h’)
else extract s h’

(* Note: For clarity, I annotated the variable names s and h with their
corresponding type. This is not necessary since in general OCaml will infer
their types.
(* extract all spades from hand5 *)
let (spades5:hand) = extract Spades hand5

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

let rec count h = match h with
| Empty -> 0
| Hand (c, h) -> count h + 1

(* find : (rank * hand) -> suit option

find the first card with rank r in h and
return its correpsonding suit s by Some(s)
if there is no card with rank r,
return None

To write this function we make use of the pre-defined,
parameterized datatype ‘a option.

type ‘a option = None | Some of ‘a

let rec find (r, h) = match h with
| Empty -> None
| Hand ((r’, s’), h’) -> if r = r’ then Some s’
else find (r, h’)

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

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

type ‘a mylist = Nil | Cons of ‘a * ‘a mylist

(* Some sample values: *)

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

let lst0 : float mylist = Nil
let lst1 : float mylist = Cons(3.1, Cons(2.6, lst0))

(* And using the predefined ML lists, we have these values: *)
let rlist1 : float list = [8.6;5.4]
let rlist2 : float list = 8.6::5.4::[]

(* 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.

let rec append l1 l2 = match l1 with
| [] -> l2
| x::l’ -> x::append l’ l2

let app12 : float list = append rlist1 rlist2
let app12′ : float 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

let head (h::t) = h;;
^^^^^^^^^^
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:

let head (h::t) = h

(* tail: ‘a list -> ‘a list *)
let tail l = match l with
| [] -> []
| h::t -> t

(* Destructor style *)
let rec app (l1, l2) =
if l1 = [] then l2
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.

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

let rec rev l = match l with
| [] -> []
| x::l -> (rev l) @ [x]

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

let rev’ l =
let rec rev_tr l acc = match l with
| [] -> acc
| h::t -> rev_tr t (h::acc)
rev_tr l []

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

(* Mergesort *)

(*split lst = (l,l’) s.t. lst = merge(l,l’)

split: ‘a list -> (‘a list * ‘a list) *)

let rec split l = match l with
| [] -> ([ ],[ ])
| [h] -> ([h],[ ])
| (h1::h2::t) ->
let (left, right) = split t in
(h1::left, h2::right)

(* merge (l,l’) = lst

assumes l and l’ are both sorted (<), returns the sorted combination merge: 'a list * 'a list -> ‘a list *)
let rec merge l x = match l, x with
| [] , x -> x
| x , [] -> x
| h::t , h’::t’ ->
if (h <= h') then h::merge t x h'::merge l t' (* mergeSort: 'a list -> ‘a list *)
let rec mergeSort l = match l with
| [] -> []
| [x] -> [x]
let (slst, slst’) = split lst in
merge (mergeSort slst) (mergeSort slst’)

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com