From 055c743c55bde27f4475d3434c26d8383c0c3ea1 Mon Sep 17 00:00:00 2001 From: Federico Igne Date: Thu, 11 Jan 2024 19:31:31 +0100 Subject: bulk: add PoC of vim-like modular editor --- lib/zipper.mli | 258 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 258 insertions(+) create mode 100644 lib/zipper.mli (limited to 'lib/zipper.mli') 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]. *) -- cgit v1.2.3