(* Part 1: define a function that computes the parity of a list of
What we want is a function even_parity such as even_parity l
returns a boolean that combined with the elements of l the
Copyright By PowCoder代写 加微信 powcoder
number of 1’s (true) is even.
This is a simple but important algorithm in data communication, its
purpose is to detect errors (one bit flips). It is very easy to
implement in circuit but it is not very reliable.
let rec even_parity = function
| [] -> false
| true::xs -> not (even_parity xs)
| false::xs -> even_parity xs
(* This version is very natural but it is not tail recursive. Let’s
make the tail recursive version. *)
let even_parity_tr l =
let rec parity p = function
| p’::xs -> parity (p<>p’) xs
parity false l
(* Part 2: Now prove that both functions are equivalent. You will need to use facts about the <> (XOR) operation *)
let ex_1 = [true]
let ex_2 = [true; true]
let ex_3 = [false; true; true; false; true]
let t_1 = even_parity ex_1 = even_parity_tr ex_1
let t_2 = even_parity ex_2 = even_parity_tr ex_2
let t_3 = even_parity ex_3 = even_parity_tr ex_3
(* High order – croupier for simplified roulette *)
(* We have a simplified roulette, where we have only two colours that
we can bet but if zero comes out, everyone loses *)
type colour = Red | Black (* The two colours we can bet on *)
type result = colour option (* The result of a run, it could be one of the colours or no colour if zero came up *)
type bet = int * colour (* The bet amount and to what colour *)
(* It is simple to see who won *)
let compute (am, col : bet) : result -> int = function
| None -> 0
| Some col’ -> if col = col’ then am * 2 else 0
Solve all these questions without using recursion or pattern
matching on lists, but instead just use the HO functions we saw
(* Q1: given a list of bets compute the results *)
(* Q2: given a list of bets and a result compute a list of winning bets *)
(* Q3: given a list of bets and a result compute how much money the casino needs to pay back *)
(* Q4: given a list of bets and a result compute if everyone won *)
(* Q5: given a list of bets and a result compute if someone won *)
(* Q6: given a list of bets return the highest winning *)
(* Level-up (a bit more complicated) *)
(* Q7: given a list of bets and a result compute the balance for the casino, how much it made *)
(* Ninja level *)
(* Q8: Can you sort the results by the amount they made? *)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com