Ленивые списки в Prolog?

Вот немного другой взгляд на ленивые списки, в которых используются приостановки. Он написан на 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)

Тем не менее, обратите внимание, что ленивые списки часто используются в других языках для достижения поведения, которое в Прологе может быть реализовано с помощью простого возврата.