Вот немного другой взгляд на ленивые списки, в которых используются приостановки. Он написан на ECLiPSe, но вы должны быть в состоянии повторить его в других вариантах Prolog.
Он использует атрибутивную переменную для записи текущей длины отложенного списка и создает новые члены списка, когда поднимается нижняя граница домена переменной.
Я предполагаю, что предикат, который выполняется для построения членов списка, имеет арность 3, и три аргумента: in-state, out-state и result. Однако этот пример легко адаптировать к общим целям.
Я также использовал «хранилище», которое является нелогичным хеш-хранилищем, чтобы быстро извлечь n-й элемент списка, избегая итерации по списку. Использование магазина не является обязательным, но повторение длинного списка снова и снова может быть дорогим.
Вот предикат, который составляет ленивый список:
:- lib(ic). % load IC library (constraints over intervals)
% make new lazy list
% lazy_list(-,-,-,++,++)
lazy_list(List, Store, E, Pred, InitState) :-
store_create(Store),
E #>= 0,
suspend(generate_nth_el(E, 0, List, Store, Pred, InitState), 3, E->ic:min).
List - это новый список, Store - дескриптор хранилища, Pred - функтор предиката, который генерирует элементы списка, InitState начальное состояние и E переменная, которая является используется для запуска создания списка.
Новые члены списка создаются при поднятии нижней границы E. В этом случае generate_nth_el/6 просыпается:
generate_nth_el(E, Last, List, Store, Pred, LastState) :-
This is Last+1,
List = [NextVal|Tail],
Goal =.. [Pred, LastState, NextState, NextVal],
call(Goal), % create next element
store_set(Store, This, NextVal), % add next element to store
get_min(E, MinE),
(
This == MinE
->
% when reached the lower bound, suspend again
suspend(generate_nth_el(E, This, Tail, Store, Pred, NextState), 3, E->ic:min)
;
% else continue with extending the list
generate_nth_el(E, This, Tail, Store, Pred, NextState)
).
Предикат generate_nth_el/6 предназначен исключительно для внутреннего использования и не должен вызываться пользователем.
Наконец, вот предикат для получения n-го элемента:
% nth_el(++,+,++,-)
nth_el(N, E, Store, V) :-
N > 0,
E #>= N, % force creation of new elements
store_get(Store, N, V). % get nth element from store.
Это добавляет ограничение, которое E должно быть не меньше N. Если это увеличивает нижнюю границу, список расширяется. Затем n-й элемент извлекается из хранилища.
В качестве примера приведем версию предиката числа Фибоначчи с входными и выходными состояниями, использованного в приведенном выше коде:
fib((0,0), (0,1), 0) :- !.
fib(StateIn, StateOut, B) :-
StateIn = (A, B),
StateOut = (B, C),
C is A+B.
А вот как это работает:
?- lazy_list(List, Store, E, fib, (0,0)),
nth_el(5, E, Store, F5),
nth_el(3, E, Store, F3),
nth_el(10, E, Store, F10).
List = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34|_1179]
Store = 'STORE'(16'8ee279a0)
E = E{10 .. 1.0Inf}
F5 = 3
F3 = 1
F10 = 34
There is 1 delayed goal.
Yes (0.00s cpu)
Обратите внимание, что ленивые списки часто используются на других языках для достижения поведения, которое в Prolog может быть реализовано с помощью простого возврата.