tndalpaul@yahoo.com

Posted by Daniel Lyons Sun, 03 Aug 2008 22:21:00 GMT

Leave an email address that works so I can reply to you. Your yahoo one bounces.

Tags  | no comments

List Zippers in Haskell and Prolog

Posted by Daniel Lyons Tue, 07 Aug 2007 05:33:00 GMT

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!

Tags ,  | 1 comment

Pattern Matching and Unification

Posted by Daniel Lyons Sat, 19 May 2007 03:58:00 GMT

For fun during my meeting with Baird the other day at the Flying Star on Central, I gave him a toy problem I read somewhere on the internet.

Problem: In Prolog, write a predicate len_three/1 which succeeds when its parameter is a list of three items.

A crummy answer looks like this:

len_three(X) :-
   length(X, Len),
   Len = 3.

Of course there are always many crummy answers. Here’s another crummy one:

len_three(X) :-
   length(X, 3).

The best answer is to let the unification algorithm do the work:

len_three([_,_,_]).

Erlang isn’t a far cry from Prolog syntactically, so it’s no surprise that this is valid Erlang:

len_three([_,_,_]) -> true.

To illustrate using the remainder of a list, I showed him how to write head and tail in various languages:

 -- Haskell
head (x:_) = x
tail (_:xs) = xs

(* OCaml *)
let head (x::_) = x  
let tail (_::xs) = xs

% Prolog
head([X|_], X).
tail([_|T], T).

% Erlang
head([X|_]) -> X.
tail([_|T]) -> T.

So you see these are all pretty analogous to each other, thanks to the pattern matching or unification functionality of the various languages.

So then Baird wanted to see an example of peeling some items off a list but also using the remainder. So I proposed pairs/1, which takes a list as a parameter and returns a list of lists, each sublist containing two items. Implementations:

-- Haskell
two (x:y:xs) = [x,y] : two xs
two [] = []

(* OCaml *)
let rec two = function
  | (x::y::xs) -> [x;y] :: two xs
  | []         -> []
;;

% Prolog
two([X, Y | Xs], [[X,Y] | Result]) :- two(Xs, Result).
two([], []).

% Erlang
two([X, Y | Xs]) -> [[X, Y] | two(Xs)];
two([]) -> [].

Some observations:

  1. Notice how much more obfuscation there is going on in the OCaml version than the Haskell version. Taste that sugary sweetness of Haskell’s syntax.
  2. In theory, the Prolog version should be reversible—in other words, you should be able to unify by calling two(X, [[1,2],[3,4]]) and getting X = [1,2,3,4] back. In practice, I have some trouble writing predicates that have that property, and I’m not sure what I’m doing wrong. I should study Prolog more carefully.
  3. Notice the Erlang version is shorter than the Prolog version. Shorter and perhaps slightly more readable. I have omitted the module and export declarations, however.
  4. The Erlang implementation does something funny if you give it 1-10: 
    2> two:two([1,2,3,4,5,6,7,8,9,10]).
[[1,2],[3,4],[5,6],[7,8],"\t\n"]

Tags , , , , , , ,  | 2 comments