Data & computation · Lesson 24 of 43

Algorithms on other data types

Database tables, binary and n-ary trees, bidirectional lists and lazily expanding lists.

DB-like structures

File db-tables.pl. The case of DB table operations: a table of a DB is simply modelled as a list of compound terms. select, insert and update are managed as expected (though of course performance can be an issue).

% get_ids(+Table, -List)
% gets the List of ids from the Table
get_ids([], []).
get_ids([user(ID, _, _) | T], [ID | L]) :- get_ids(T, L).

% query(+Table, +Id, -Tuple)
% gets the Tuple with Id from the Table
query([user(ID, N, C) | _], ID, user(ID, N, C)).
query([_ | T], ID, Tuple) :- query(T, ID, Tuple).

% update(+Table, +Id, +NewTuple, -NewTable)
% updates the tuple with Id to NewTuple
update([user(ID, _, _) | T], ID, Tuple, [Tuple | T]).
update([H | T], ID, Tuple, [H | Table]) :-
    update(T, ID, Tuple, Table).

?- get_ids([user(100, a, b), user(101, c, d)], Ids)

?- query([user(100, a, b), user(101, c, d)], 101, T)

?- update([user(100, a, b), user(101, c, d)], 101, user(101, c, e), DB)

Binary trees: searching elements

File bintree-search.pl. Again a natural modelling: the functors tree/3 and nil/0, and (relational) operations to find elements. search(+Tree, +Elem) relates a tree with any of its elements.

% search(+Tree, +Elem)
% relates a tree with any of its elements
search(tree(_, E, _), E).
search(tree(L, _, _), E) :- search(L, E).
search(tree(_, _, R), E) :- search(R, E).

?- search(tree(tree(nil, 10, nil), 20, tree(tree(nil, 30, nil), 40, nil)), E)

The tree of the goal is:

              20
            /    \
          10      40
         /  \    /  \
       nil  nil 30   nil
               /  \
             nil  nil

The answers come in pre-order: the node, then the left subtree, then the right one.

Binary trees: other operations

File bintree-ops.pl:

% leaves(+Tree, -ListLeaves), returns the list of leaves
leaves(nil, []).                     % handling empty tree
leaves(tree(nil, E, nil), [E]) :- !. % handling a leaf
leaves(tree(L, _, R), O) :-          % general case
    leaves(L, OL),                   % OL are leaves on left
    leaves(R, OR),                   % OR are leaves on right
    append(OL, OR, O).               % O appends the two

% leftlist(+Tree, -List)
% returns the left-most branch as a list
leftlist(nil, []).
leftlist(tree(nil, E, _), [E]) :- !.
leftlist(tree(T, E, _), [E | L]) :- leftlist(T, L).

?- leaves(tree(tree(nil, 10, nil), 20, tree(tree(nil, 30, nil), 40, nil)), L)

?- leftlist(tree(tree(nil, 10, nil), 20, tree(tree(nil, 30, nil), 40, nil)), L)

N-ary trees with lists

File nary-lists.pl. Again a natural modelling: the functor tree/2, with the node in the first argument and the list of children in the second.

% searchN(+Tree, ?Elem), search Elem in Tree
searchN(tree(E, _), E).
searchN(tree(_, L), E) :- member(T, L), searchN(T, E).

?- searchN(tree(20, [tree(10, []), tree(40, [tree(30, [])])]), E)

N-ary trees with variable arguments

File nary-univ.pl. A different modelling: the functors tree/1, tree/2, tree/3, ... with the node in the first argument and the others as children. The key is =.., which lets one predicate treat any arity.

% searchV(+Tree, ?Elem), search Elem in Tree
searchV(T, E) :- T =.. [tree, E | _].
searchV(T, E) :-
    T =.. [tree, _ | L], member(T2, L), searchV(T2, E).

?- searchV(tree(20, tree(10), tree(40, tree(30))), E)

Bidirectional lists

The design sketch: constant time to move next/previous on the list. The idea: the list (1, 2, 3, 4, 5, 6) is modelled by the term bilist([1], [2,3,4,5,6]), that is two lists, one from the pointer to the left, one from the pointer to the right.

operation	result
start	`bilist([1], [2,3,4,5,6])`
move right	`bilist([2,1], [3,4,5,6])`
move left	`bilist([1], [2,3,4,5,6])`
addleft(0)	`bilist([0], [1,2,3,4,5,6])`
addright(10)	`bilist([0], [10,1,2,3,4,5,6])`

Here is one possible implementation of the four operations:

% the pointer is at the head of the left list
move_right(bilist([X|L], [Y|R]), bilist([Y, X|L], R)).
move_left(bilist([X, Y|L], R), bilist([Y|L], [X|R])).
addleft(E, bilist([X|L], R), bilist([E|L], [X|R])).
addright(E, bilist(L, R), bilist(L, [E|R])).

?- move_right(bilist([1], [2, 3, 4, 5, 6]), B)

?- move_left(bilist([2, 1], [3, 4, 5, 6]), B)

?- addleft(0, bilist([1], [2, 3, 4, 5, 6]), B)

?- addleft(0, bilist([1], [2, 3, 4, 5, 6]), B), addright(10, B, B2)

Dynamically expanding lists

Lazy structures in Prolog: non-ground compound terms can be seen as data structures partially completed. For example [1,2,3|_] is a list starting with 1, 2, 3, and which can be completed in several ways. As a concept, could it be used to model lazy lists?

An example application: an expanding cache for factorials. factorial(+N, -Out, ?Cache): the cache is a partial list of known factorials "up to a point", e.g. [1,1,2,6,24|_]. Each call might expand the cache, which is both input and output. File factorial-cache.pl:

% factorial(+N, -Out, ?Cache)
% cache is a partial list of factorials [1,1,2,6,24|_]
factorial(N, Out, Cache) :- factorial(N, Out, Cache, 0).
factorial(N, Res, [Res|_], N) :- !, nonvar(Res).
factorial(N, Out, [H, V | T], I) :-
    var(V), !, I2 is I + 1, V is H * I2,
    factorial(N, Out, [V | T], I2).
factorial(N, Out, [_, V | T], I) :-
    I2 is I + 1, factorial(N, Out, [V | T], I2).

?- C = [1, 1, 2, 6|_], factorial(5, Res, C)

The goal finds Res = 120 and, in the same step, extends the cache from [1,1,2,6|_] to [1,1,2,6,24,120|_]: the open tail was filled in by unification.

Exercise: Depth of a binary tree

Using the tree(Left, Elem, Right) / nil representation, write depth(Tree, D): the depth of the tree, where nil has depth 0 and a node has depth 1 plus the larger depth of its subtrees.