CS代写 - PowCoder代写

FP playground: working with lists¶

#require “fp” (* loads the main FP library I wrote for this course *)

Having superficially covered a range of FP core concepts in the introduction lecture, we will now put this knowledge into practice by learning about list processing. This is a hands-on tutorial with lots of examples for you to cut your teeth on!

Along the way, we will learn about FP concepts such as algebraic types, record types, pattern matching, …

1. What is a list?¶

In FP, a list is an ordered collection of elements of the same type. OCaml offers the following syntax for writing lists (note: elements are separated by ;, not ,):

let x = [ 4; 2; 35; 0 ]

[ “hello”; “cambridge” ]

Here, OCaml infers the type of x to be int list: this is a new kind of type we haven’t seen before!

This is an example of a parameterised type: there can be lists of ints, lists of strings, lists of bools, … lists of anything really! That is why OCaml uses ‘a list as its native list type. Here, ‘a means “any type” ─ you will see later how we can write functions that operate on ‘a list values (e.g. length: ‘a list -> int).

Let’s look at another example:

let us_presidents = [ “Obama”, 2009, 2017; “Trump”, 2017, 2021 ]

OCaml offers the following operators on lists:

:: for appending a single element at the front
@ for concatenating two lists together.

let x = 11 :: x

let empty = [] in
11 :: 4 :: 2 :: 35 :: 0 :: empty

let x = x @ [ 8 ]

Exercise 1/A
Use :: to update us_presidents so that it now also includes “Bush”, 2001, 2009:

let us_presidents =
(* your answer here *)

Now, how would add at the end of the list? 🤔

Impossible exercise 1/B
Use @ to update us_presidents so that it now also includes , whose term started in 2021.

let us_presidents = (* your answer here *)

2. Sum types: representing heterogeneous data¶

How do we add to the list?
He was elected in 2021, and it is unclear how long he will serve. Thus we simply cannot represent it using a string * int * int value… and so we can’t add it to a (string * int * int) list.

But don’t fret! OCaml has a very expressive algebraic type system. We’ve already learned about product types (e.g. string * int * int), so let’s now learn about sum types:

type maybe_ended =
| Still_in_office
| Ended of int

Still_in_office

Ended 2005

Here, type maybe_ended very naturally expresses the fact that a president may, or may not, have finished his/her term.

We can now pack the last 4 US presidents, including the current one, in a single list:

let us_presidents =
[ “Bush”, 2001, Ended 2009
; “Obama”, 2009, Ended 2017
; “Trump”, 2017, Ended 2021
; “Biden”, 2021, Still_in_office

OCaml also has record types, which may be more natural here:

type president =
{ name : string
; started : int
; ended : int option

OCaml comes with a pre-defined “option” type, defined as a polymorphic sum type as follows:

type ‘a option =
| Some of ‘a

[ “string”]

Some “hello”

We can represent a single president as e.g.

let bush = { name = “Bush”; started = 2001; ended = Some 2009 }

and access its record fields using the . notation:

So we can now construct our list of US presidents as follows:

3. The list type as a polymorphic recursive sum type¶

OCaml allows you to define recursive types, and this can be used to define a polymorphic list type, like so:

type ‘a my_list =
| Empty (* empty list *)
| Append of ‘a * ‘a my_list
(* an element, potentially followed by more elements *)

let x = [ 11; 4; 2]

Exercise 3/A Use the type my_list to construct the same list as x above, as an int my_list value.

let x = 11 :: 4 :: 2 :: []

let x_alternative = Append (11, Append (4, Append (2, Empty)))

type ‘a binary_tree =
| Leaf of ‘a
| Split of ‘a binary_tree * ‘a binary_tree

|——|—- 6
—| |—- 5
|——|—- |—- 7

Split (Split (Leaf 50.0000, Leaf 6.), Split (Split (Leaf 5., Leaf 7.), Leaf 25.))

4. Pattern matching¶

OCaml allows you to perform value-name bindings via pattern-matching.

let x = “foo”, 3.14

let xs, xf = x

What is going on here? OCaml knows that x is a pair, and therefore that it can be identified to a pattern of the form xs, xf. When we write

let xs, xf = x

OCaml automatically transform this into two let bindings:

let xs = [the first element of the pair]
let xf = [the second element of the pair]

Pattern matching works for pretty much everything 😎, and makes coding considerably more convenient. The general keyword for pattern matching is match, and is used as follows:

match x with
| a, b -> a ^ ” bar”

match x with
| a, b -> b +. 2.5

(* you get an error if you match against the wrong pattern *)
match x with
| a, b, c -> a

The notation is intuitive: we match a given value x to a relevant pattern (here, (a, b), and the variable names used inside the pattern (here, a and b) become bound to their corresponding values in x inside the expression that follows the -> arrow.

Notice that in the code above, we are not actually using b anywhere. It is common practice in this case to be explicit about this, and use _ instead of b:

match x with
| first, _ -> first

Exercise 4/A Write a function that takes an argument x : int * int and returns the sum of the two components.

let f x = (* your answer here, which should use the match keyword *)

f (5, 6) (* should be 11 *)

Exercise 4/B Write a function that takes an argument x : (int * (int * string)) and returns the string component.

let f x = (* your answer here *)

f (3, (14, “well done”)) (* should be “well done” *)

let f (_, (_, a)) = a

Now, let’s look at pattern matching for sum types, e.g. to deal with values of type ‘a option:

let maybe_print x =
match x with
| Some msg -> Fp.Utils.print_msg msg
| None -> ()

maybe_print (Some “I have a dream”)

maybe_print None

Pro tip ─ when the first thing you do inside a function is to pattern match the final argument, you can use the function keyword directly, like this:

let maybe_print = function
| Some msg -> Fp.Utils.print_msg msg
| None -> ()

Exercise 4/C Write a function iter which takes a function f : ‘a -> unit and a value x : ‘a option as arguments, and

performs f a if if x = Some a
does nothing if x = None.

let iter f x = match x with
| None -> ()
| Some y -> f y

Now use this iter function to rewrite the maybe_print function above in a single line.

let maybe_print = iter Fp.Utils.print_msg

Exercise 4/D Write a function map which takes a function f : ‘a -> ‘b and a value x : ‘a option as arguments, and

returns Some (f a) if x = Some a
returns None if x = None.

let map f x = (* your answer here *)

map (fun x -> x + 1) None

map (fun x -> x + 1) (Some 35)

Congratulations! You have just implemented two of the most important higher-order functions in FP (iter and map). We’ll do the same for lists later in this notebook. But first, let’s finish learning about pattern matching.

You can pattern-match records as well, like so:

let still_in_office = function
| { ended = None; _ } -> true
| _ -> false (* _ is a pattern that matches EVERYTHING *)

These two cases shouldn’t be switched, because _ matches everything and would make the second pattern matching case redundant. OCaml complains about this:

let still_in_office = function
| _ -> false (* _ is a pattern that matches EVERYTHING *)
| { ended = None; _ } -> true

still_in_office bush

which is equivalent to

bush.ended

let still_in_office x =
match x.ended with
| None -> true
| Some _ -> false

Here’s another example:

let check_valid_dates = function
| { started = s; ended = Some y; _ } -> y >= s
| _ -> true

check_valid_dates { name = “test”; started = 2010; ended = Some 2005 }

Exercise 4/D Write a function most_recent that takes two US president records p1 and p2, and returns the most recent one.

let most_recent p1 p2 = (* your answer here *)

let most_recent p1 p2 =
match p1.started > p2.started with
| true -> p1
| false -> p2

Finally, lists can be pattern-matched using the :: constructs we saw above, as follows:

let first_element = function
| [] -> None
| a :: _ -> Some a

let has_more_than_two_elts x =
match x with
| [] -> false
| [ _ ] -> false
| [ _; _ ] -> false
| _ -> true

let x = [ 3 ] in
has_more_than_two_elts x

I hope you find pattern matching very intuitive!

5. List processing¶

Let’s get started with the real stuff! We are now going to write a number of functions applied to lists, to reinforce everything we’ve learned so far.

Exercise 5/A Write a function length : ‘a list -> int that computes the length of a list.

(* autoformat = Ctrl-l (small L) *)
(* your answer below *)

Exercise 5/B Write a function rev : ‘a list -> ‘a list that reverse a list

(* note to self: show the students how to write the TAIL-RECURSIVE version *)

Exercise 5/C Write a function nth : ‘a list -> int -> ‘a option that extracts the nth element of a list, if it exists (returns None if the list is shorter than n).

Exercise 5/D Write a function mem : ‘a list -> ‘a -> bool such that mem x a is true if and only if the list x contains element a.

Exercise 5/E Write a function map : (‘a -> ‘b) -> ‘a list -> ‘b list such that map f [x1; x2; …; xN] returns [f x1; f x2; …; f xN].

Exercise 5/F Write a function zip : ‘a list -> ‘b list -> (‘a * ‘b) list such that for two lists x = [x1; …; xN] and y = [y1; …; yN] of the same length, zip x y returns [(x1, y1); … ; (xN, yN)].

Exercise 5/G Write a function map2 : (‘a -> ‘b -> ‘c) -> ‘a list -> ‘b list -> ‘c list such that map2 f x y returns [f x1 y1; … ; f xN yN].

Exercise 5/H Rewrite zip as an instance of map2.

Exercise 5/I Write a function init: int -> (int -> ‘a) -> ‘a list such that init n f equals [f 1; f2; …; f n].

Exercise 5/J Write a function fold: (‘b -> ‘a -> ‘b) -> ‘b -> ‘a list -> ‘b such that fold f init x equals f (… (f (f init x1) x2) …) xN.

Exercise 5/K Reuse the fold function to write a function iter : (‘a -> unit) -> ‘a list -> unit that performs f x1; f x2; … f xN. Do you see how this can be used to perform a “for loop”?

Exercise 5/L Reuse the fold function to write filter : ‘a list -> (‘a -> bool) -> ‘a list such that filter x f filters out every element a of x for which f a is false (i.e. only retains those elements a for which f a is true).

Exercise 5/M Rewrite nth using fold.

Exercise 5/N Rewrite mem using fold.

From these exercises, it should now be clear that map, fold, and map2 (and fold2 which we haven’t had time to implement) are very basic primitives from which many useful functions can be derived. We call these iterators.

Time permitting, we will discuss scaling issues typically encountered for recursive functions, and how to avoid these issues by writing so-called tail recursive functions.

6. Utility functions¶

Let’s write a function that times the execution of a (‘a -> ‘b) -> ‘a -> ‘b * float.

let timeit f x =
let t0 = Unix.gettimeofday () in
let result = f x in
let t1 = Unix.gettimeofday () in
result, t1 -. t0

Infix operators:

This is how OCaml lets you define your own infix operators: for example, in the standard library, ( * ) is defined as:

let ( * ) x y = Int.mul x y

let ( |> ) x f = f x (* also already defined in the standard library *)

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

Related Posts