1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
type 'a my_list =
| Item of ('a * 'a my_list)
| None
(** Return the length (number of elements) of a given list. *)
let length my_list =
let rec aux l n =
match l with
| Item (_, tl) -> aux tl (n + 1)
| None -> n
in aux my_list 0
(** Return the first element of the given list.
* Raise [Failure "hd"] if the list is empty.
*)
let hd = function
| Item (h, _) -> h
| None -> raise (Failure "hd")
(** Return the given list without its first element.
* Raise [Failure "tl"] if the list is empty.
*)
let tl = function
| Item (_, t) -> t
| None -> raise (Failure "Called tail on empty list")
(** Return the n-th element of the given list.
* Raise [Failure "hd"] or [Failure "tl"] if the list is too short.
* Raise [Invalid_argument "my_list.nth"] if n is negative.
*)
let rec nth my_list n =
match n with
| _ when n < 0 -> raise (Invalid_argument "my_list.nth")
| 0 -> (hd my_list)
| _ -> (nth (tl my_list) (n - 1))
(** Return the given list in the reverse order. *)
let rev my_list =
let rec aux my_list agg =
match my_list with
| Item(hd, tl) -> aux tl (Item(hd, agg))
| None -> agg
in aux my_list None
(** Return a list containing the result of f(x) for each element x in the given
* list. *)
let rec map f my_list =
match my_list with
| Item(hd, tl) -> Item(f hd, map f tl)
| None -> None
(** Return a list containing only the elements x in the given list for which
* f(x) returns true.
*)
let rec filter f my_list =
match my_list with
| None -> None
| Item(hd, tl) -> (
match f hd with
| true -> Item(hd, filter f tl)
| _ -> filter f tl
)
(** Return a list which results in the concatenation of l1 and l2. *)
let rec append l1 l2 =
match l1 with
| Item(hd, tl) -> Item(hd, (append tl l2))
| None -> l2
(** Return a list which results in the concatenation of reversed l1 and l2. *)
let rev_append l1 l2 =
append (rev l1) l2
(** Return a list consisting of the contenation of the given list of lists. *)
let rec flatten = function
| Item(hd, tl) -> append hd (flatten tl)
| None -> None
(** Return true if the given elem is contained in the given list. *)
let rec mem elem = function
| Item(hd, tl) -> (
match hd = elem with
| true -> true
| false -> mem elem tl
)
| None -> false
(** Return true if the given elem is contained in the given list. Same as
* my_list.mem but uses physical equality. *)
let rec memq elem = function
| Item(hd, tl) -> (
match hd == elem with
| true -> true
| false -> memq elem tl
)
| None -> false
|
