Zipper lists in Prolog

I’m currently looking into zipper data structures. Searching the web for zippering lists for prolog, the third hit is this old blog post by Daniel Lyons (hi Daniel!):

http://old.storytotell.org/blog/2007/08/07/list-zippers-in-haskell-and-prolog.html

But I don’t liked the calls to reverse/2 and append/3 and their implied performance hits. So, I just rewrote the code to eliminate the calls (and start list index at 1; this is not C! :-)

% zipper(+Position, +List, -Zip, -Element)
%
% where Zip = zip(Before, Element, After)
%
% index starts at 1

zipper(Position, List, Zip, Element) :-
    zipper(Position, List, [], Zip, Element).

zipper(1, [Head|Tail], Acc, zip(Acc,Head,Tail), Head).
zipper(N, [Head|Tail], Acc, zip(Before,Element,After), Element) :-
    N > 1,
    M is N - 1,
    zipper(M, Tail, [Head|Acc], zip(Before,Element,After), Element).

next(zip(Before,Element,[Head|Tail]), zip([Element|Before],Head,Tail)).

previous(X, Y) :-
    next(Y, X).

Some sample queries:

?- [zipper].
% zipper compiled 0,00 sec, 5 clauses
true.

?- zipper(3, [1,2,3,4,5], Zip, X), next(Zip, Next).
Zip = zip([2, 1], 3, [4, 5]),
X = 3,
Next = zip([3, 2, 1], 4, [5]) .

?- zipper(3, [1,2,3,4,5], Zip, X), next(Zip, Next), previous(Next, Zip).
Zip = zip([2, 1], 3, [4, 5]),
X = 3,
Next = zip([3, 2, 1], 4, [5]) .

?- zipper(3, [1,2,3,4,5], Zip, X), previous(Zip, Previous).
Zip = zip([2, 1], 3, [4, 5]),
X = 3,
Previous = zip([1], 2, [3, 4, 5]) .

?- zipper(3, [1,2,3,4,5], Three, X),
   next(Three, Four), next(Four, Five), previous(Five, Four),
   previous(Four, Three), previous(Three, Two), previous(Two, One).
Three = zip([2, 1], 3, [4, 5]),
X = 3,
Four = zip([3, 2, 1], 4, [5]),
Five = zip([4, 3, 2, 1], 5, []),
Two = zip([1], 2, [3, 4, 5]),
One = zip([], 1, [2, 3, 4, 5]) .

I wonder how many curious Prolog programmers wrote a similar solution in the past. A cut can be added to the first clause of zipper/5 to eliminate a choice point. The zipper constructed is not the same (minus the index start) as in Daniel’s solution, however, as we can no longer simply concatenate Before+Element+After to get the original list. On the other hand, my solution follows the list example on the Wikipedia page:

http://en.wikipedia.org/wiki/Zipper_(data_structure)

Pros and cons of both solutions from an usage perspective? Still learning but this is fun programming :-) Eventually, I hope to add support for zipper data structures to the Logtalk library.


Comments are disabled.