Поддерживает ли какая-либо версия Prolog абстракцию аккумуляторов более высокого порядка?

Question

Поддерживает ли какая-либо версия Prolog абстракцию аккумуляторов более высокого порядка?

Мне было интересно о Прологе, который может включать встроенный вызов, как это:

accum(generator, filter, accumulator)
Calculates all solutions to generator.
For each one, if filter can be proved, accumulator is proved.
Backtracks to find all solutions to filter and generator.
Accumulator may backtrack internally, but multiple proofs of accumulator are 
  conjoined, not backtracked.

Так, например, для суммирования списка без использования рекурсии вы можете написать:

X is 0, accum(member(Val,List), True, X is X + Val).

Есть ли пролог с этой конструкцией или эквивалент? Имейте в виду, что я немного новичок в Прологе и, возможно, упускаю что-то очевидное.

6

prolog mercury

Источник

user2890451 17 окт '13 в 12:40

3 ответа

Другие вопросы по тегам prolog mercury

user874024 17 окт '13 в 13:55 2013-10-17 13:55 · Answer 1 · 2013-10-17 13:55

Библиотека SWI-Prolog (агрегат) имеет мощный интерфейс, например

aggregate_all(sum(Val), member(Val,List), Sum)

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

В SWI-Prolog вы можете сделать ?- edit(library(aggregate)). изучать внутренности...

библиотека (агрегат) относительно неэффективна, но в сочетании со структурами данных SWI-Prolog nb_ (не подлежащими возврату) должна хорошо выполнять свою работу...

О не подлежащих возврату структурах данных: вот пример моего " собранного " аккумулятора, реализованного с помощью nb_setarg / 3.

user634629 17 окт '13 в 13:40 2013-10-17 13:40 · Answer 2 · 2013-10-17 13:40

Я полагаю, вы имеете в виду без явной рекурсии? Если это так, вы можете использовать реализацию списка старших предикатов высшего порядка, свернутого влево, вместе с лямбда-выражением, чтобы избежать необходимости во вспомогательном предикате. Используя Logtalk в качестве примера, вы можете написать:

?- Sum0 is 0, meta::fold_left([X,Y,Z]>>(Z is Y+X), Sum0, [1,2,3], Sum).
Sum0 = 0,
Sum = 6.

Logtalk может использовать в качестве бэкэнд-компилятора большинство реализаций Prolog ( http://logtalk.org/). Вы также можете использовать Ульриха lambda библиотека ( http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord.html) с поддерживаемым компилятором Prolog вместе с библиотекой Prolog, предоставляющей предикат сгиба влево для того же результата. Используя сейчас YAP в качестве примера:

$ yap
...
 ?- use_module(library(lambda)).
...
 ?- use_module(library(maplist)).
...
 ?- Sum0 is 0, foldl(\X^Y^Z^(Z is Y+X), [1,2,3], Sum0, Sum).
Sum = 6,
Sum0 = 0.

Вкратце, предикат сгиба влево перебирает список, рекурсивно применяя замыкание в своем первом аргументе к элементу списка и к аккумулятору, возвращая конечное значение аккумулятора.

user4110163 05 окт '14 в 12:03 2014-10-05 12:03 · Answer 3 · 2014-10-05 12:03

В стандартной библиотеке Mercury модуль "Решения" обеспечивает такую функциональность.

Обратите внимание, что X is X + Val не присваивает новое значение X. Это утверждение, которое истинно, если Val равен нулю, и ложно, если это любое другое число, что, вероятно, не то, что вы имеете в виду. Аккумуляторы, подобные этому, обычно выражаются как отношение между начальным и конечным значением.

В Меркурии ваш пример можно записать так:

:- import_module solutions.
...
sumlist(List, Sum) :-
    Generator = (pred(Val::out) is nondet :- member(Val, List), true),
    Accumulator = (pred(X::in, Y::in, Z::out) is det :- Z = X + Y),
    aggregate(Generator, Accumulator, 0, Sum).

Нет необходимости в отдельном аргументе фильтра, так как он может быть включен как часть генератора.