Извлечение Факты в качестве матрицы в Прологе

Question

Предположим, мы имеем следующее:

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

Я хочу, чтобы извлечь матричное представление (M) этих фактов, так что

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

Здесь нет никакой опасности решение:

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

Есть некоторые проблемы такого подхода, однако, именно:

1. обход к базе данных п раз, где п является числом аргументов; и
2. это не очень хорошо обобщается на произвольное n.

Итак, вопрос: какой самый идиоматический способ достичь этого в Prolog?

Answer 1

насчет:

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

Теперь вы можете просто импортировать transpose/2 матрицу из clpfd модуля, или реализовать его самостоятельно, как в this answer (да, я знаю, что это довольно ленивый, но какой смысл изобретать колесо ?).

Если я запускаю это в swipl, я получаю:

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

, который выглядит точно так же, как вы хотите.

Вы можете, конечно, сказать, что для вычисления transpose/2 есть еще некоторые вычислительные накладные расходы, но фаза сбора выполняется только один раз (и если это не просто факты, но и ответы из предложений), которые могут быть дорогими, как ну и, кроме того, я думаю, что модуль будет реализовывать клаузулы, возможно, очень эффективно.

Answer 2

Я не думаю, что вы найдете решение, которое является полностью общим и максимально эффективным. Вот простое решение для 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). 

После добавления 100,000 дополнительных edge/3 фактов, это выполняет следующим образом:

?- 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|...]]. 

Для сравнения, здесь измерение для реализации от вопроса:

?- 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|...]]. 

А вот более общее решение, основанное на transpose/2 Виллем:

?- 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|...]]. 

Таким образом, мое решение кажется лучшим с точки зрения количества выводов: 100 000 выводов для findall/3 и 100 000 выводов для перемещения по списку.Решение вопроса состоит из 100 000 выводов для каждого findall/3, но не более того. Это, однако, немного быстрее, потому что это более эффективно с памятью: все, что выделяется, попадает в окончательное решение, тогда как моя программа выделяет список из 100 000 edge/3 условий, которые затем должны быть собраны в мусор. (В SWI-Prolog, вы можете увидеть коллекции мусора, если вы включите профайлер и/или отслеживание GC.)

Если я действительно нужен, чтобы это было как можно быстрее и быть обобщенными многие разные значения N, я бы написал макрос, который расширяется до чего-то вроде решения в вопросе.

Редактировать: Если «idiomatic» требование поднято, я прибегнув к хранению базы данных edge в виде списка в глобальной переменной SWI-Prolog. В этом случае моя однопроходная реализация будет работать без накладных расходов findall/3 и без промежуточного мусора.