Memo-functions with lists

next up previous contents
Next: How Prolog works
Up: Introduction to Prolog for Mathematicians
Previous: Memo-functions

Memo-functions with lists

However, asserting new clauses is rather slow in some Prolog systems. So instead, we can pass the newly-generated results around in a list:

fib( N, F ) :-
    fib( N, F, [ done(0,1), done(1,1) ], _ ).

fib( N, F, L, L ) :-
    member( done(N,F), L ).

fib( N, F, L, [ done(N,F) | L2 ] ) :-
    N1 is N - 1,
    N2 is N - 2,
    fib( N1, F1, L, L1 ),
    fib( N2, F2, L1, L2 ),
    F is F1 + F2.

Read fib(N,F,L,L1) as the following relation between , , , and :

This technique is often used in processing graphs, where we need to record the points we have already processed, in order to avoid processing them again.

There are more efficient ways to represent sets than as unordered lists. Other possibilities: ordered lists, binary trees. See books on data structures in the computing science literature.

Jocelyn Ireson-Ireson-Paine
Mon Jul 17 22:27:41 BST 1995