Как уже упоминалось, ваша проблема заключается в том, что вы выполняете проверку длины после рекурсивного вызова, что означает, что рекурсия неограничена. К сожалению, как раз двигая проверку длины выше рекурсивного вызова, как это ...
members([X], L):-
member(X, L).
members([X|Xs], L):-
length(Xs, M),
top(N), M < N,
member(X, L),
members(Xs, L).
... не так хорошо, как мы получим это:
L = [3, 1, 2, 3, 3] ;
L = [3, 2, 2, 3, 3] ;
L = [3, 3, 2, 3, 3] ;
L = [3, 1, 3, 3, 3] ;
L = [3, 2, 3, 3, 3] ;
L = [3, 3, 3, 3, 3] ;
ERROR: Out of global stack
В то время как это получает нас ответ, это не так полезно, поскольку он не может быть помещен внутрь большего предиката, так как он ломается. Это ломается, потому что мы только продвинули проблему дальше. Вот почему:
Проблема в том, что вы создаете список сверху вниз. Другими словами, мы определяем список следующим образом: List = [Head|Tail], где мы оговариваем некоторые ограничения на Head и state, что Tail состоит из списка элементов, определяемых теми же ограничениями и ограниченных базовым случаем. Это означает, что, хотя мы находимся в середине рекурсивного вызова, у нас есть только доступ к Head - мы не можем получить доступ к содержимому Tail, поскольку он строится только после того, как интерпретатор прошел весь путь вниз и достиг основного футляра (т.е. members([X], L) :-), а затем последовательно добавляет каждый хвост к своей голове, пока не будет создан окончательный список.
Это может выглядеть, как мы имеем доступ к длине, так как length/2 вызов сидит там в середине рекурсивного предиката, однако, так как переменная передается в length/2 для списка на данном этапе не связан ни к чему, Prolog ждет, пока он не закончит рекурсивные вызовы ниже этой точки перед вычислением длины. Проблема, конечно, в том, что проверка длины - это то, что ограничивает рекурсию, поэтому она будет продолжаться до тех пор, пока не закончится память.
Хотя рекурсия сверху вниз имеет тенденцию к построению предикатов Prolog по умолчанию, как показывает этот пример, иногда нам нужен доступ к структуре данных, которую мы создаем. Решение заключается в использовании восходящей рекурсии. Это реализовано в Prolog с помощью предиката аккумулятора, который начинается с пустого списка и продолжает строить список до один за другим, передавая список аккумуляторов (который является полностью наземным списком) через рекурсивный предикат.Вот как я бы написать аккумуляторный предикат для этой задачи:
members(I,L) :-
members_accumulator([],I,L).
members_accumulator(Tail,I,L) :-
length(Tail, M),
top(N),
M < N,
member(X, L),
members_accumulator([X|Tail],I,L).
members_accumulator(I,I,_).
Нам нужны два предиката, как первая обертка вокруг аккумулятора, который проходит пустой список в аккумуляторе предикат. Основной случай больше не имеет ничего общего с пустым списком - все, что ему нужно сделать, это указать, что окончательный список аккумуляторов фактически является окончательным списком, который нам нужен (который был пронизан через предикат аккумулятора только для этой цели) , Кроме того, в этом случае предикаты накопителя должны быть в этом порядке, иначе будет одна точка выбора, которая оценивается как ложная справа в конце.
Получение головок вокруг рекурсии в Прологе, и когда вам нужно использовать восходящую рекурсию, а не сверху вниз, это нетривиальный подвиг. На самом деле у меня не было полного понимания, пока я не прочитал The Art of Prolog. Также должно быть много информации о аккумуляторах онлайн.
Комментарий не дал никакого решения. –