Extract Facts as Matrix in Prolog

Question

Suppose we have the following:

edge(a, 1, 10).
edge(b, 2, 20).
edge(c, 3, 30).
edge(d, 4, 40).

I want to extract a matrix representation (M) of these facts, such that

M = [[a,b,c,d],[1,2,3,4],[10,20,30,40]]

Here's a no-brainer solution:

edgeMatrix(M) :-
  findall(A, edge(A, _, _), As),
  findall(B, edge(_, B, _), Bs),
  findall(C, edge(_, _, C), Cs),
  M = [As, Bs, Cs].

There are some problems to this approach, however, viz:

we traverse the database n times, where n is the number of arguments; and
this doesn't generalize very well to an arbitrary n.

So the question is: what is the most idiomatic way to achieve this in Prolog?

score 5 · Accepted Answer · edited May 23 '17 at 12:01

5

What about:

edgeMatrix(M) :-
    findall([A,B,C],edge(A,B,C),Trans),
    transpose(Trans,M).

Now you can simply import the transpose/2 matrix from clpfd module, or implement one yourself like in this answer (yeah I know that's quite lazy, but what is the point of reinventing the wheel?).

If I run this in swipl, I get:

?- edgeMatrix(M).
M = [[a, b, c, d], [1, 2, 3, 4], [10, 20, 30, 40]].

which looks exactly like you want.

You can of course say that there is still some computational overhead to calculate the transpose/2, but the collecting phase is done only once (and if these are not simply facts, but answers from clauses as well) which can be expensive as well, and furthermore I think a module will implement clauses probably very efficiently anyway.

edited May 23 '17 at 12:01

Community

1
1

answered Jan 05 '17 at 21:04

Willem Van Onsem

443,496
30
428
555

That was very ingenious... I like it ;-) Although it might have the same performance issue I mentioned due to `transpose/2`. – Hugo Sereno Ferreira Jan 05 '17 at 21:12
@HugoSerenoFerreira You can look at the definition of `transpose/2` but I think it is about as efficient as it can be with a list-of-lists as a matrix representation. Altogether, there is no straight-forward, general way to deal with matrices in pure Prolog (as far as I know). You could maybe avoid using a list-of-lists to start with, but your question doesn't give enough detail. – Jan 06 '17 at 04:15

Isabelle Newbie · Answer 2 · 2017-01-06T12:47:18.567

I don't think you'll find a solution that is both completely general and maximally efficient. Here's a simple solution for N = 3:

edges(Edges) :-
    Goal = edge(_A, _B, _C),
    findall(Goal, Goal, Edges).

edges_abcs_([], [], [], []).
edges_abcs_([edge(A,B,C)|Edges], [A|As], [B|Bs], [C|Cs]) :-
    edges_abcs_(Edges, As, Bs, Cs).

edges_abcs([As, Bs, Cs]) :-
    edges(Edges),
    edges_abcs_(Edges, As, Bs, Cs).

After adding 100,000 additional edge/3 facts, this performs as follows:

?- time(edges_abcs(M)).
% 200,021 inferences, 0.063 CPU in 0.065 seconds (97% CPU, 3176913 Lips)
M = [[a, b, c, d, 1, 2, 3, 4|...], [1, 2, 3, 4, 1, 2, 3|...], [10, 20, 30, 40, 1, 2|...]].

For comparison, here is the measurement for the implementation from the question:

?- time(edgeMatrix_orig(M)).
% 300,043 inferences, 0.061 CPU in 0.061 seconds (100% CPU, 4896149 Lips)
M = [[a, b, c, d, 1, 2, 3, 4|...], [1, 2, 3, 4, 1, 2, 3|...], [10, 20, 30, 40, 1, 2|...]].

And here is the more general solution based on transpose/2 by Willem:

?- time(edgeMatrix_transpose(M)).
% 700,051 inferences, 0.098 CPU in 0.098 seconds (100% CPU, 7142196 Lips)
M = [[a, b, c, d, 1, 2, 3, 4|...], [1, 2, 3, 4, 1, 2, 3|...], [10, 20, 30, 40, 1, 2|...]].

So my solution seems best in terms of number of inferences: 100,000 inferences for the findall/3 and 100,000 inferences for traversing the list. The solution from the question has 100,000 inferences for each findall/3, but nothing more. It is, however, slightly faster because it's more memory efficient: Everything that is allocated ends up in the final solution, whereas my program allocates a list of 100,000 edge/3 terms which must then be garbage collected. (In SWI-Prolog, you can see the garbage collections if you turn on the profiler and/or GC tracing.)

If I really needed this to be as fast as possible and to be generalizable to many different values of N, I'd write a macro that expands to something like the solution in the question.

Edit: If the "idiomatic" requirement is lifted, I would resort to storing the edge database as a list in an SWI-Prolog global variable. In that case, my single-pass implementation would work without the findall/3 overhead and without producing intermediate garbage.

Extract Facts as Matrix in Prolog

2 Answers2