Add Vylist.complement for calculating difference between two lists

where one contains another (starting with the first element).

2 files changed, 12 insertions, 0 deletions

diff --git a/src/vylist.ml b/src/vylist.ml
index ec04055..f18801e 100644
--- a/src/vylist.ml
+++ b/src/vylist.ml
@@ -27,3 +27,14 @@ let rec insert_after p x xs =
     | [] -> raise Not_found
     | y :: ys -> if (p y) then y :: x :: ys
                  else y :: (insert_after p x ys)
+
+let complement xs ys =
+    let rec aux xs ys =
+        match xs, ys with
+        | [], _ -> Some ys
+        | _, [] -> assert false (* Can't happen *)
+        | p :: ps, q :: qs -> if p = q then aux ps qs
+                              else None
+    in
+    if List.length xs < List.length ys then aux xs ys
+    else aux ys xs
diff --git a/src/vylist.mli b/src/vylist.mli
index 70f0042..9a713b3 100644
--- a/src/vylist.mli
+++ b/src/vylist.mli
@@ -3,3 +3,4 @@ val remove : ('a -> bool) -> 'a list -> 'a list
 val replace : ('a -> bool) -> 'a -> 'a list -> 'a list
 val insert_before : ('a -> bool) -> 'a -> 'a list -> 'a list
 val insert_after : ('a -> bool) -> 'a -> 'a list -> 'a	list
+val complement : 'a list -> 'a list -> 'a list option