List Zippers in Haskell and Prolog

Posted by Daniel Lyons on August 6, 2007

Earlier today I thought I’d solidify my understanding of zippers, at least with lists. I’m pretty eluded by the concept for other data structures for right now but I’m liking the idea of it for lists (though not exactly seeing the whole point of it yet).

So I wrote up a quick implementation in Haskell included here:

module Listzip where
        
        import List
        
        data Zipper a = Zipper [a] a [a]
             deriving (Show, Eq)
        
        at n l = Zipper prefix item postfix where
            (prefix,item,postfix) = doBreak n l []
            doBreak 0 (x:xs) acc = (List.reverse acc, x, xs)
            doBreak n (x:xs) acc = doBreak (n-1) xs (x:acc)
        
        next (Zipper pre i (x:xs)) = Zipper (pre ++ [i]) x xs
        
        prev (Zipper pre i post) = Zipper (init pre) (last pre) (i:post)

I realized it might be handy to have that be a functor so I can fmap it, so I added a couple more lines:

instance Functor Zipper where
              fmap f (Zipper pre i post) = Zipper (fmap f pre) (f i) (fmap f post)
             
        toList (Zipper pre i post) = pre ++ [i] ++ post

That’s cool, because now I can do things like this:

*Listzip> fmap (**2) $ at 4 [1..10]
        Zipper [1.0,4.0,9.0,16.0] 25.0 [36.0,49.0,64.0,81.0,100.0]

Baird and I got to talking about things to do with hardware. Knowing what I know about the Warren Abstract Machine, it should be not particularly hard to make Prolog run on a pretty simple piece of hardware. All you need that’s weird is some kind of searchable “database” and a couple of stacks. So then I found myself coding up my zipper again in Prolog:

%% a general list zipper for prolog
        
        zip_at(0, [H|T], Acc, zipper(RAcc, H, T)) :- !, reverse(Acc, RAcc).
        zip_at(N, [H|T], Acc, Result) :-
                N0 is N - 1,
                zip_at(N0, T, [H|Acc], Result).
        
        next(zipper(Left, Item, [H|Right]), zipper(Result, H, Right)) :-
                append(Left, [Item], Result).
        prev(zipper(Left, Item, Right), zipper(NewLeft, NewItem, [Item|Right])) :-
                append(NewLeft, [NewItem], Left).

I think that’s pretty neat. When I was testing it I noticed something else though:

?- zip_at(1, [1,2,3,4,5], [], X), next(X, Y), prev(Y, X).
        
        X = zipper([1], 2, [3, 4, 5]),
        Y = zipper([1, 2], 3, [4, 5]) ;
        
        No
        ?- zip_at(1, [1,2,3,4,5], [], X), prev(Y, X).
        
        X = zipper([1], 2, [3, 4, 5]),
        Y = zipper([1, 2], 3, [4, 5]) ;
        
        No
        ?- zip_at(1, [1,2,3,4,5], [], X), prev(X, Y).
        
        X = zipper([1], 2, [3, 4, 5]),
        Y = zipper([], 1, [2, 3, 4, 5]) ;

This is the first time I’ve ever managed to successfully make Prolog code that can be instantiated on either variable! As you can see, if I reverse the variable order on prev, it gives me @next@’s behavior. Which means prev can be shortened to:

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

I thought those predicates looked pretty similar!

When Prolog works, it’s so cool!