New FASTER! SIMPLER! algorithm

[fireball-separation.git] / ocaml_new / listx.ml

diff --git a/ocaml_new/listx.ml b/ocaml_new/listx.ml
new file mode 100644 (file)
index 0000000..821e281
--- /dev/null
+++ b/ocaml_new/listx.ml
@@ -0,0 +1,71 @@
+(* Non-empty lists *)
+type 'a listx =
+  | Nil of 'a
+  | Cons of ('a * 'a listx)
+
+let rec fold_left f acc l =
+  match l with
+  | Nil x -> f acc x
+  | Cons (x, l') -> fold_left f (f acc x) l'
+
+let hd =
+ function
+  | Nil x
+  | Cons (x,_) -> x
+
+let rec map f =
+  function
+  | Nil x -> Nil (f x)
+  | Cons (x, l') -> Cons (f x, map f l')
+
+let rec append l =
+  function
+  | Nil x -> Cons (x, l)
+  | Cons (x, l') -> Cons (x, append l l')
+
+let rec length = function
+  | Nil _ -> 1
+  | Cons (_, xs) -> 1 + (length xs)
+
+let rec assoc x = function
+  | Nil (y,t)
+  | Cons ((y,t),_) when x=y -> t
+  | Nil _ -> raise Not_found
+  | Cons (_,l) -> assoc x l
+
+let rec to_list =
+ function
+    Nil x -> [x]
+  | Cons (x,l) -> x::to_list l
+
+let rec from_list =
+ function
+    [] -> raise (Failure "from_list: empty list")
+  | [x] -> Nil x
+  | x::l -> Cons(x,from_list l)
+
+let rec split_nth n l =
+ match n,l with
+    0,_ -> []
+ | 1,Nil x -> [x]
+ | n,Cons (hd,tl) -> hd::split_nth (n-1) tl
+ | _,_ -> raise (Failure "split_nth: not enough args")
+
+let rec max =
+  function
+  | Nil x -> x
+  | Cons (x, l) -> Pervasives.max x (max l)
+
+let rec last =
+  function
+  | Nil x -> x
+  | Cons (_, l) -> last l
+(*
+let rec nth i l = match l, i with
+ | Cons (x, _), 1  -> x
+ | _, n when n <= 0 -> raise (Invalid_argument "Listx.nth")
+ | Cons (_, xs), n -> nth (n-1) xs
+ | Nil x, 1        -> x
+ | Nil _, _        -> raise (Invalid_argument "Listx.nth")
+;;
+*)