OCaml zipper and holidays
This blog will be in holidays until the 15th of August. This is a little something to keep you busy while waiting for my holiday pictures : a light and nifty implementation of list zippers.
Basically a zipper is a list which has a cursor, thus reading and moving through is non destructive.
type 'a t = 'a list * 'a list
exception Out_of_bound
exception End_of_zip
val empty : 'a Zip.t
val next : 'a Zip.t -> 'a Zip.t
val previous : 'a Zip.t -> 'a Zip.t
val first : 'a Zip.t -> 'a Zip.t
val last : 'a Zip.t -> 'a Zip.t
val get : 'a Zip.t -> 'a
val insert : 'a -> 'a Zip.t -> 'a Zip.t
val delete : 'a Zip.t -> 'a Zip.t
val replace : 'a -> 'a Zip.t -> 'a Zip.t
val rev : 'a Zip.t -> 'a Zip.t
val append : 'a Zip.t -> 'a Zip.t -> 'a Zip.t
val iter : ('a -> unit) -> 'a Zip.t -> unit
val chop : 'a Zip.t -> 'a Zip.t
val from_list : 'a list -> 'a Zip.t
val to_list : 'a Zip.t -> 'a list
end
A simple example :
let _ =
let print = function
b, [] -> List.iter (printf " %d") (List.rev b); printf ".\n"
| b, c::a -> List.iter (printf " %d") (List.rev b); printf ".%d" c; List.iter (printf " %d") a; printf "\n"
in
let z = Zip.empty in
let z = Zip.insert 5 z in
print z;
let z2 = Zip.from_list [1;2;3;4] in
print z2;
let z = Zip.append z2 z in
print z;
let z = Zip.next z in
print z;
let z = Zip.next z in
print z;
let z = Zip.next z in
print z;
let z = Zip.previous z in
print z;
let z = Zip.last z in
print z;
let z = Zip.previous z in
print z;
let z = Zip.previous z in
print z;
let z = Zip.previous z in
print z;
let z = Zip.insert 7 z in
print z;
let z = Zip.replace 9 z in
print z;
let z = Zip.delete z in
print z
Its result :
.1 2 3 4
.1 2 3 4 5
1.2 3 4 5
1 2.3 4 5
1 2 3.4 5
1 2.3 4 5
1 2 3 4 5.
1 2 3 4.5
1 2 3.4 5
1 2.3 4 5
1 2.7 3 4 5
1 2.9 3 4 5
1 2.3 4 5
Leave a Reply