Ленивые списки в Прологе?

Question

Возможно ли иметь ленивые списки в Прологе? Что-то вроде следующего:

ones([1 | Y]) :- ones(Y).

Хотя это явно не работает, как написано.

Answer 1

Маркус Триска разместил здесь в открытом доступе некоторый код, который стоит изучить:

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Prolog stream/lazy list demonstration

   Written 2005 by Markus Triska ([e-mail])
   Public domain code.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

Название документа ( прост, для потоков Пролога) может затруднить поиск документа, но имеет смысл. Цитирую из вышесказанного:

Здесь "поток" используется в смысле "последовательность", "отложенный список", "отложенный список" и т. Д., Как в структуре и интерпретации компьютерных программ, а не в смысле потока ввода-вывода Prolog.

Answer 2

Вот ленивый список чисел Хэмминга в Прологе с использованием "генератора идиомы".

Чем больше я думаю об этом, тем больше мне кажется, что ленивые списки на Haskell - это просто открытые (иначе говоря, "разница") списки Prolog, а corecursion - просто причудливое имя для построения нисходящего списка построения хвостовой рекурсии по модулю cons, Кроме того, Haskell неявно устанавливается один раз в языке, в то время как (не возвращая назад подмножество) Prolog устанавливается явно один раз.

Техника "связывания узлов", работающая с мозгами, на самом деле является не более чем неловко реализованной реализацией поздних переменных. И все это является генератором в Haskell, с запоминающим хранилищем универсальным посредником доступа. Но в любом случае,

Следующее реализует потоки с принудительным заголовком (из разновидности SICP), где, если элемент принудительно, все элементы, предшествующие ему в списке, также уже принудительно.

:- dynamic( next/3 ).

%// collect N elements produced by a generator in a row: 
take( 0, Next, Z-Z, Next):- !.
take( N, Next, [A|B]-Z, NextZ):- N>0, !, next( Next, A, Next1),
  N1 is N-1,
  take( N1, Next1, B-Z, NextZ).

%// a "generator" provides specific `next/3` implementation 
next( hamm( A2,B,C3,D,E5,F,[H|G] ), H, hamm(X,U,Y,V,Z,W,G) ):- 
  H is min(A2, min(C3,E5)),
  (   A2 =:= H -> B=[N2|U], X is N2*2 ; (X,U)=(A2,B) ),
  (   C3 =:= H -> D=[N3|V], Y is N3*3 ; (Y,V)=(C3,D) ),
  (   E5 =:= H -> F=[N5|W], Z is N5*5 ; (Z,W)=(E5,F) ).

%// Hamming numbers generator's init state:
mkHamm( hamm(1,X,1,X,1,X,X) ).       

%// A calling example: main( +Number)
main(N) :- 
    mkHamm(G), take(20,G,A-[],_),          write(A), nl,  
    take(N-1,G,_,G2), take(2,G2,B-[],_),   write(B), nl.

Просто, а? За ones мы просто определяем

next( ones, 1, ones).

поскольку там нет (изменение) состояния, а затем назовите его как, например,

take(N, ones, A-[], _), writeln(A).

Для целочисленных перечислений, подобных Хаскеллу, мы определяем

next( fromBy(F,B), F, fromBy(F2,B)):- F2 is F+B.

и позвонить take(8, fromBy(3,2), A-[], _) получить A = [3, 5, 7, 9, 11, 13, 15, 17]. Последовательность Фибоначчи просто

next( fib(A,B), A, fib(B,C)):- C is A+B.

С take(20, fib(0,1), FS-[], _), список из 20 элементов FS чисел Фибоначчи определяется.

Памятная последовательность Фибоначчи

mkFibs( fibs([0|L], L) ):- L=[1|_].
next( fibs([A|L], L), A, fibs(L, L2) ):- 
    L=[B|L2], L2=[C|_], (var(C)-> C is A+B ; true).

Теперь перезапуск с ранее использованного генератора не будет пересчитывать числа, но вместо этого будет повторно извлекать ранее вычисленные элементы последовательности, где это возможно. Это внутреннее общее открытое хранилище хрупко для неправильного использования, то есть неправильного создания экземпляра (правка: его еще не установлена ​​переменная последнего хвостового указателя). Это причина take строит новое хранилище для своего ответа, вместо того, чтобы выставлять внутреннее.

Answer 3

Да, в Прологе можно создавать ленивые списки. Вот бесконечный, ленивый список тех, кто использует freeze/2,

ones(L) :-
  freeze(L, (L=[1|T],ones(T)) ).

Использование его на верхнем уровне выглядит так:

?- ones(Ones), [A,B,C|_] = Ones.
A = B = C = 1.

Вам также может понравиться пакет list_util (для SWI-Prolog), который содержит несколько ленивых предикатов списка.

Answer 4

Ну, вы можете определить бесконечный список из них (или что-нибудь еще) как:

H = [1|H].

использовать:

4 ?- H=[1|H], [A1|T1] = H, [A2|T2] = T1, T1=T2.
H = [1|**],
A1 = 1,
T1 = [1|**],
A2 = 1,
T2 = [1|**].

Конечно, это не сработает, если вы хотите список простых чисел / Фибоначчи / что-нибудь не так тривиально.

Вы могли бы написать некоторые предикаты, которые будут эмулировать поведение ленивого списка, но я не думаю, что есть какие-либо библиотеки / стандартизированный способ сделать это (по крайней мере, в swi-прологе) (:(ленивый список haskell - такая хорошая функция),

Answer 5

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

Answer 6

% A simple generic solution using SWI-Prolog 

% Returns a prefix of a lazy sequence

prefix(Prefix,PrefixLength,LazySequenceName) :-
    apply(LazySequenceName,[LazySequence]),
    length(Prefix,PrefixLength),
    append(Prefix,_,LazySequence).

% Lazy sequence of natural numbers

nat(LazySequence) :- 
    nat(0,LazySequence).
nat(Item,LazySequence) :-
    freeze(LazySequence,
      (LazySequence=[Item|Rest], Next is Item+1, nat(Next,Rest)) ).

% Lazy sequence of Fibonacci numbers

fib(LazySequence) :- 
    fib(1,0,LazySequence).
fib(A,B,LazySequence) :-
    freeze(LazySequence,
       (LazySequence=[C|Rest], C is A+B, fib(B,C,Rest))).

% Examples

test :-
    prefix(N,10,nat), format('Ten first natural numbers: ~w~n',[N]),
    prefix(F,10,fib), format('Ten first Fibonacci numbers: ~w~n',[F]),
    fib(S), nth1(100,S,X), format('The hundredth Fibonacci number: ~w~n',[X]).