Travesty_containers.Zipper
Zipper
implements the 'list zipper' data structure.
A list zipper contains two lists: a 'right list', which represents a sequence of data to be processed; and a 'left list', which collects the sequence of data already processed in reverse order. At any point, the first element in the right list---the 'cursor'---represents the item currently being processed.
The usual use case of a zipper is to 'slide' across the right list, moving elements onto the left list one by one, and then 'rewind' the left list back onto the right for further processing.
These versions of the list zipper contains a few extensions. First, many operations can be parametrised by a monad---this will usually be an error monad like Or_error
, but can be anything else (like a state transformer).
Second, items in zippers constructed using Make_marked
can be mark
ed, attaching a tag to them; later on, if the item still exists in the zipper, the zipper can be rewound back to the mark using recall
.
For input and output signatures for this module's functors, see Zipper_types
.
module Plain : Zipper_types.S
Plain
is a basic list zipper, without specialised functionality.
module Make_marked
(Mark : Zipper_types.Basic_mark) :
Zipper_types.S_marked with type mark := Mark.t
Make_marked
makes a marked zipper from a Basic_mark
.
module Int_mark_zipper : Zipper_types.S_marked with type mark := Base.int
Int_mark_zipper
is a marked zipper whose marks are integers.