A dictionary based on Sterling and Shapiro

[dnmfarrell]

Hey all
This is a tale of what happened yesterday that resulted in dict.pl. I'd love to hear any feedback you might have on the code, I'll probably blog about it.

Yesterday I was using scryer prolog to process a stream of data that I needed to compute statistics on. Naturally I needed a dictionary, so I started with program 15.9 from The Art of Prolog, with a couple of updates:

If the key is non-numeric, the predicates < and > must be generalized.
The Art of Prolog, Chapter 15.3

Since we have compare/3 and a pair type, I updated program 15.9 to:

lookup(Key, dict(Key-Value1, _, _), Value) :-
  !, Value = Value1.

lookup(Key, dict(Key1-_, Left, _), Value) :-
  compare(<, Key, Key1), lookup(Key, Left, Value).

lookup(Key, dict(Key1-_, _, Right), Value) :-
  compare(>, Key, Key1), lookup(Key, Right, Value).

But this leaves behind a choicepoint, so:

lookup(Key, dict(Key1-Value1, Left, Right), Value) :-
  (   Key = Key1 ->
      Value = Value1
  ;   compare(<, Key, Key1) ->
      lookup(Key, Left, Value)
  ;   lookup(Key, Right, Value)
  ).

And I was quite smitten with this.

But then I found I needed to check for the existence of a key: lookup(K, D, V), nonvar(V). so I created get/3 to do that.

And since get/3 was semantically clearer than lookup/3, I created add/3 to complement it.

And I was done!

Or so I thought, but then I needed to update a key. This stumped me as I tried and failed to use list differences to modify a pair without copying the tree. I gave in and added put/4 to update and return a copy.

put(Key, dict(Key1-Value1, Left, Right), Value, Dict1) :-
  (   Key = Key1 ->
      Dict1 = dict(Key-Value, Left, Right)
  ;   compare(<, Key, Key1) ->
      put(Key, Left, Dict2),
      Dict1 = dict(Key1-Value1, Dict2, Right)
  ;   put(Key, Right, Value, Dict2),
      Dict1 = dict(Key1-Value1, Left, Dict2)
  ).

This thing was getting dangerously useful - but did it work? I wrote to_list/2 which made writing tests and debugging easy, and to my astonishment it was un-moded so I renamed it dict_list (careful how you say that!) and I could transform a list of pairs into a dictionary or vice-versa.

And this worked great and I finished my prolog data processor. Even better, it found bugs in my previous data processor.

Then the prospect of the tree getting unbalanced and O(n) operations started to weigh heavy on me 😰
How could I live with such terrible risks?

I practically yelled with joy when I realized I could use keysort/2 to balance the tree. Eureka!

balance(D, D1) :-
  nonvar(D),
  dict_list(D, Ls),
  keysort(Ls, Ms),
  balance_(Ms, D1).

balance_([], dict(_-_,_,_)).
balance_([L|Ls], D1) :-
  Ms = [L|Ls],
  list_midpoint(Ms, Mid),
  list_split(Ms, Mid, Left, [Root|Right]),
  balance_(Left, LeftD),
  balance_(Right, RightD),
  D1 = dict(Root, LeftD, RightD).

And I got a good night's sleep.

[hurufu]

Have you seen library(assoc)?

[dnmfarrell]

I guess I missed it, damn. That looks perfect though, thanks.

[jjtolton]

Yeah it's nice. Code is fairly readable, too!