2 files changed, 78 insertions, 7 deletions

diff --git a/lib/Utilities.ml b/lib/Utilities.ml
index 52483b3..e4ee9c3 100644
--- a/lib/Utilities.ml
+++ b/lib/Utilities.ml
@@ -7,14 +7,73 @@ end
 module Result = struct
   let ( let* ) = Result.bind
   let fmap f m = Result.bind m f
+end
+
+module type SEQUENCE = sig
+  type 'a t
+
+  val empty : 'a t
+  val cons : 'a -> 'a t -> 'a t
+  val fold : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
+end
+
+module Generic (S : SEQUENCE) = struct
+  let sequence ms =
+    let open Result in
+    S.fold
+      (fun m acc ->
+        let* acc = acc in
+        let* m = m in
+        Ok (S.cons m acc))
+      ms
+      (Ok S.empty)
+end
+
+module List = struct
+  module ListSequence : SEQUENCE with type 'a t = 'a list = struct
+    type 'a t = 'a list
+
+    let empty = []
+    let cons x xs = x::xs
+    let fold = List.fold_right
+  end
+
+  include Generic (ListSequence)
+end
+
+module FingerTree = struct
+  module FingerTreeSequence : SEQUENCE with type 'a t = 'a BatFingerTree.t = struct
+    type 'a t = 'a BatFingerTree.t
+
+    let empty = BatFingerTree.empty
+    let cons x xs = BatFingerTree.cons xs x
+    let fold f xs acc = BatFingerTree.fold_right
+                          (Fun.flip f)
+                          acc
+                          xs
+  end
+
+  include Generic (FingerTreeSequence)
+
+  let map2 f xs ys =
+    let rec frob xs ys acc =
+      match BatFingerTree.front xs with
+      | None -> acc
+      | Some (xs', x) ->
+         match BatFingerTree.front ys with
+         | None -> acc
+         | Some (ys', y) ->
+            f x y
+            |> BatFingerTree.snoc acc
+            |> frob xs' ys'
+    in
+    frob xs ys BatFingerTree.empty
+
+  let zip xs ys = map2 (fun x y -> x, y) xs ys
 
-  let sequence ms = List.fold_right
-                      (fun m acc ->
-                        let* acc = acc in
-                        let* m = m in
-                        Ok (m::acc))
-                      ms
-                      (Ok [])
+  let join ss sep =
+    BatFingerTree.print ~first:"" ~last:"" ~sep:sep BatIO.nwrite
+    |> Fun.flip BatIO.to_string ss
 end
 
 module Option = struct
diff --git a/lib/Utilities.mli b/lib/Utilities.mli
index 9661796..f149889 100644
--- a/lib/Utilities.mli
+++ b/lib/Utilities.mli
@@ -7,6 +7,9 @@ end
 module Result : sig
   val ( let* ) : ('a, 'e) result -> ('a -> ('b, 'e) result) -> ('b, 'e) result
   val fmap : ('a -> ('b, 'e) result) -> ('a, 'e) result -> ('b, 'e) result
+end
+
+module List : sig
   val sequence : ('a, 'b) result list -> ('a list, 'b) result
 end
 
@@ -20,3 +23,12 @@ module Atomic : sig
   (* This is silly *)
   val mswap : 'a Atomic.t -> ('a -> ('a, 'b) result) -> ('a Atomic.t, 'b) result
 end
+
+module FingerTree : sig
+  val map2 : ('a -> 'b -> 'c) -> 'a BatFingerTree.t -> 'b BatFingerTree.t -> 'c BatFingerTree.t
+  val zip : 'a BatFingerTree.t -> 'b BatFingerTree.t -> ('a * 'b) BatFingerTree.t
+
+  val sequence : ('a, 'b) result BatFingerTree.t -> ('a BatFingerTree.t, 'b) result
+
+  val join : string BatFingerTree.t -> string -> string
+end