1 files changed, 258 insertions, 0 deletions

diff --git a/lib/zipper.mli b/lib/zipper.mli
new file mode 100644
index 0000000..c3c79a6
--- /dev/null
+++ b/lib/zipper.mli
@@ -0,0 +1,258 @@
+open Base
+
+(** Linear zippers.
+
+    A zipper represents {b a paused traversal} of a certain data
+    structure. A linear zipper of type ['a zipper] represents a zipper
+    over a sequence of ['a] elements.
+
+    One can access the {b focused element} of the zipper with [focus].
+    The focus of a zipper is also known as the the {b cursor} of the
+    zipper, and can be moved back and forth with [left] and [right].
+
+    Elements can be added or removed at the cursor's position with
+    [push] and [pop] operations. Variants are available, e.g., to act
+    before the cursor, with suffix [_before], or after the cursor, with
+    suffix [_after]. *)
+
+type !+'a zipper
+(** A zipper is represented as a {b pair} of sequences of type ['a]. The
+    focus of the zipper is the element at the head of the second
+    sequence, if any.
+
+    Note that the first sequence is reversed. Given a sequence
+    [[1; 2; 3; 4; {5}; 6; 7]], where we represent the cursor using
+    curly braces [{_}], its representation as a zipper is
+    [([4; 3; 2; 1], [5; 6; 7])]. *)
+
+type !+'a t = 'a zipper
+(** An alias for the ['a zipper] type. *)
+
+val empty : 'a zipper
+(** Return an empty zipper *)
+
+val before : 'a zipper -> 'a Sequence.t
+(** Return the sequence before the cursor *)
+
+val after : 'a zipper -> 'a Sequence.t
+(** Return the sequence after the cursor *)
+
+val focus : 'a zipper -> 'a option
+(** Return the focus of the zipper, if any. *)
+
+val focus_or : 'a zipper -> default:'a -> 'a
+(** Return the focus of the zipper, or a user-provided default, otherwise. *)
+
+val history : 'a zipper -> 'a Sequence.t
+(** Returns the sequence of elements [pop]ped so far from the zipper. *)
+
+val is_far_left : 'a zipper -> bool
+(** Return whether the cursor is at the beginning of the zipper. *)
+
+val is_far_right : 'a zipper -> bool
+(** Return whether the cursor is at the end of the zipper. *)
+
+val is_empty : 'a zipper -> bool
+(** Return whether the zipper is empty. *)
+
+val left_length : 'a zipper -> int
+(** Return the number of elements before the cursor. *)
+
+val right_length : 'a zipper -> int
+(** Return the number of elements  after the cursor. *)
+
+val length : 'a zipper -> int
+(** Return the length of the zipper. *)
+
+(** {1 Moving the cursor} *)
+
+val left : 'a zipper -> 'a zipper
+(** Move the cursor one step to the left, if possible.
+    Calling [left z],
+
+        - if [z] is [([3; 2; 1], [4; 5])], the result is [([2; 1], [3; 4; 5])], 
+        - if [z] is [([], [1; 2; 3])], the result is [([], [1; 2; 3])].
+    *)
+
+val left_while : ('a -> bool) -> 'a zipper -> 'a zipper
+(** [left_while f z] moves the cursor in [z] to the left as long as the
+    predicate [f] is [true] when applied to the focus, or the left end
+    of the zipper is reached. *)
+
+val far_left : 'a zipper -> 'a zipper
+(** Move the cursor to the left, as much as possible. *)
+
+val right : 'a zipper -> 'a zipper
+(** Move the cursor one step to the right, if possible.
+    Calling [right z],
+
+        - if [z] is [([3; 2; 1], [4; 5])], the result is [([4; 3; 2; 1], [5])], 
+        - if [z] is [([1; 2; 3], [])], the result is [([1; 2; 3], [])].
+    *)
+
+val right_while : ('a -> bool) -> 'a zipper -> 'a zipper
+(** [right_while f z] moves the cursor in [z] to the right as long as
+    the predicate [f] is [true] when applied to the focus, or the right
+    end of the zipper is reached. *)
+
+val far_right : 'a zipper -> 'a zipper
+(** Move the cursor to the right, as much as possible. *)
+
+val goto : int -> 'a zipper -> 'a zipper
+(** Move the cursor to a specific (absolute) position in the zipper.
+    Depending on the current position, it either moves the cursor
+    forward or backwards, without crossing the zipper boundaries. *)
+
+(** {1 Changes at the cursor} *)
+
+(** Zippers provide [O(1)] operations performed at the cursor position.
+    This involve [push]ing and [pop]ping elements before and after the
+    cursor. *)
+
+val pop_after : 'a zipper -> 'a zipper
+(** Remove the element at the cursor position, if any, and return the
+    modified zipper. Calling [pop_after z],
+
+        - if [z] is [([3; 2; 1], [4; 5])], the result is [([3; 2; 1], [5])], 
+        - if [z] is [([1; 2; 3], [])], the result is [([1; 2; 3], [])].
+    *)
+
+val pop_before : 'a zipper -> 'a zipper
+(** Remove the element before the cursor, if any, and return the
+    modified zipper. Calling [pop_before z],
+
+        - if [z] is [([3; 2; 1], [4; 5])], the result is [([2; 1], [4, 5])], 
+        - if [z] is [([], [1; 2; 3])], the result is [([], [1; 2; 3])].
+    *)
+
+val pop : 'a zipper -> 'a zipper
+(** [pop] is an alias for [pop_before]. *)
+
+val push_after : 'a -> 'a zipper -> 'a zipper
+(** Insert an element after the cursor.
+    Calling [push_after 0 z], if [z] is [([3; 2; 1], [4; 5])],
+    the result is [([3; 2; 1], [0; 4, 5]))], *)
+
+val push_before : 'a -> 'a zipper -> 'a zipper
+(** Insert an element before the cursor. Return the modified zipper.
+    Calling [push_before 0 z], if [z] is [([3; 2; 1], [4; 5])],
+    the result is [([0; 3; 2; 1], [4, 5]))]. *)
+
+val push : 'a -> 'a zipper -> 'a zipper
+(** [push] is an alias for [push_before]. *)
+
+val split : 'a zipper -> 'a zipper * 'a zipper
+(** [split z] splits the zipper in two. [([3; 2; 1], [4; 5])] becomes
+    [([3; 2; 1], []), ([], [4; 5])]. *)
+
+(** {1 Consuming zippers} *)
+
+(** Since zippers are based on sequences, iterating over zippers
+    terminates only when both sequences are finite.
+    Unless otherwise stated, these functions will iterate on the
+    elements before the cursor, first. *)
+
+val iter_before : ('a -> unit) -> 'a zipper -> unit
+(** [iter_before f z] will call [f x] for all [x], elements before the
+    cursor in [z].*)
+
+val iter_after : ('a -> unit) -> 'a zipper -> unit
+(** [iter_after f z] will call [f x] for all [x], elements after the
+    cursor in [z].*)
+
+val iter : ('a -> unit) -> 'a zipper -> unit
+(** [iter f z] is equivalent to [iter_before f z; iter_after f z] *)
+
+val for_all : ('a -> bool) -> 'a zipper -> bool
+(** [for_all p z] tests whether a predicate [p] is [true] for all
+    elements in a zipper. *)
+
+val exists : ('a -> bool) -> 'a zipper -> bool
+(** [exists p z] tests whether at least one element in the zipper is
+    [true] according to the predicate [p]. *)
+
+val find_before : ('a -> bool) -> 'a zipper -> 'a option
+(** [find_before p z] will return the first element before the cursor in
+    [z] satisfying the predicate [p], if any. *)
+
+val find_after : ('a -> bool) -> 'a zipper -> 'a option
+(** [find_after p z] will return the first element after the cursor in
+    [z] satisfying the predicate [p], if any. *)
+
+(** {1 Transforming zippers} *)
+
+(** Since zippers are based on sequences, the functions in this section
+    are lazy; i.e., resulting elements of the zipper are computed only
+    when demanded. *)
+
+val map_before : ('a -> 'a) -> 'a zipper -> 'a zipper
+(** Map a function over all elements before the cursor. *)
+
+val map_after : ('a -> 'a) -> 'a zipper -> 'a zipper
+(** Map a function over all elements after the cursor. *)
+
+val map_focus : ('a -> 'a) -> 'a zipper -> 'a zipper
+(** Map a function over the element focused by the cursor, if any. *)
+
+val map : ('a -> 'a) -> 'a zipper -> 'a zipper
+(** Map a function over all elements of a zipper. *)
+
+val mapi_before : (int -> 'a -> 'a) -> 'a zipper -> 'a zipper
+(** [mapi_before] is analogous to {!Zipper.map_before}, but the function
+    takes an index and an element.
+    The index indicates the distance of an element from the cursor. *)
+
+val mapi_after : (int -> 'a -> 'a) -> 'a zipper -> 'a zipper
+(** [mapi_after] is analogous to {!Zipper.map_after}, but the function
+    takes an index and an element.
+    The index indicates the distance of an element from the cursor. *)
+
+val mapi : (int -> 'a -> 'a) -> 'a zipper -> 'a zipper
+(** [mapi] is analogous to {!Zipper.map}, but the function takes an
+    index and an element.
+    The index indicates the distance of an element from the cursor. *)
+
+val filter_before : ('a -> bool) -> 'a zipper -> 'a zipper
+(** [filter_before p z] filters the elements before the cursor in a
+    zipper [z] according to a predicate [p], i.e., keeping the elements
+    that satisfy the predicate. *)
+
+val filter_after : ('a -> bool) -> 'a zipper -> 'a zipper
+(** [filter_after p z] filters the elements after the cursor in a
+    zipper [z] according to a predicate [p], i.e., keeping the elements
+    that satisfy the predicate. *)
+
+val filter : ('a -> bool) -> 'a zipper -> 'a zipper
+(** [filter p z] filters the elements of the zipper [z] according to a
+    predicate [p], i.e., keeping the elements that satisfy the
+    predicate. *)
+
+val context_before : int -> 'a zipper -> 'a zipper
+(** [context_before n z] will limit the zipper [z] to [n] elements before
+    the cursor. *)
+
+val context_after : int -> 'a zipper -> 'a zipper
+(** [context_after n z] will limit the zipper [z] to [n] elements after
+    the cursor. *)
+
+val context : b:int -> ?a:int -> 'a zipper -> 'a zipper
+(** [context ~b ~a z] will limit the zipper [z] to [b] elements before
+    the cursor and [a] elements after the cursor. When [a] is not
+    provided, it defaults to [b]. *)
+
+val clear_history : 'a zipper -> 'a zipper
+(** Clear the history of the zipper. See {!Zipper.history}. *)
+
+(** {1 Zippers and sequences} *)
+
+val of_seq : 'a Sequence.t -> 'a zipper
+(** Turn a sequence into a zipper with the cursor at the beginning. *)
+
+val to_seq : 'a zipper -> 'a Sequence.t
+(** Return the zipper as a sequence.
+    Calling [to_seq z], with [z] being [([3; 2; 1], [4; 5])], results in
+    [[1; 2; 3; 4; 5]]. *)
+
+val window : from:int -> len:int -> 'a zipper -> 'a Sequence.t
+(** [windows from len z] returns a sequence containing [len] elements
+    starting from [from]. *)