Added first draft of my_list

Signed-off-by: Olivier Gayot <olivier.gayot@sigexec.com>

1 files changed, 65 insertions, 0 deletions

diff --git a/my_list.mli b/my_list.mli
new file mode 100644
index 0000000..b21aa5d
--- /dev/null
+++ b/my_list.mli
@@ -0,0 +1,65 @@
+type 'a my_list =
+    | Item of ('a * 'a my_list)
+    | None
+
+(** Return the length (number of elements) of a given list. *)
+let rec length = function
+    | Item (_, tail) -> 1 + (length (tail))
+    | None -> 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