Даже размерный список в Prolog

Question

Я пытаюсь написать предикат, который будет оценивать размер списка, чтобы быть четным или нет, и это нужно сделать, не вычисляя длину списка или любые арифметические операции. Это, наверное, проще, чем вычисление длины, но у меня возникают проблемы с мыслью о том, как это сделать без этого. Я предполагаю какую-то рекурсивную технику, но если кто-то сможет помочь, это будет здорово.

Answer 1

Я знаю, что это слишком поздно, чтобы ответить на ваш вопрос, но, надеюсь, это поможет:

Чтобы найти список имеет нечетную длину:

oddlength([X]). 
oddlength([X,Y,Z]). 
oddlength([X,Y|R]) :- oddlength(R),!. 

Чтобы найти список имеет четную длину:

evenlength([]). 
evenlength([X,Y|R]) :- evenlength(R),!. 

Answer 2

Да, вы хотите рекурсию. Базовые случаи были бы наименьшими нечетными/четными списками, которые вы можете иметь, и тогда вам нужно всего лишь выяснить, как построить рекурсивный вызов, чтобы он сводился к основному случаю. Вы можете начать с представления списка длины 3, который должен возвращать true для «oddList». Если это не основной случай, каков следующий логический шаг? Как нечетный список отличается от одного?

Answer 3

Preserve logical-purity! Просто действуйте следующим образом:

evenlength([]).    % smallest list with even length is [] (length=0) 
evenlength([_|Xs]) :- 
    oddlength(Xs). 

oddlength([_|Xs]) :-  % smallest list with odd length is [_] (length=1) 
    evenlength(Xs). 

Некоторые простые наземные запросы для evenlength/1 и oddlength/1:

?- evenlength([]). 
true. 
?- oddlength([]). 
false. 

?- evenlength([1]). 
false. 
?- oddlength([1]). 
true. 

?- evenlength([1,2]). 
true.  
?- oddlength([1,2]). 
false. 

?- evenlength([1,2,3]). 
false.  
?- oddlength([1,2,3]). 
true. 

Обратите внимание, что эти предикаты могут не только тестовые списки кандидатов, но и генерировать их:

?- evenlength(Xs). 
    Xs = [] 
; Xs = [_A,_B] 
; Xs = [_A,_B,_C,_D] 
; Xs = [_A,_B,_C,_D,_E,_F] 
... 

?- oddlength(Xs). 
    Xs = [_A] 
; Xs = [_A,_B,_C] 
; Xs = [_A,_B,_C,_D,_E] 
; Xs = [_A,_B,_C,_D,_E,_F,_G] 
... 

Answer 4

Использование meta-predicatefoldl/4 и Prolog lambdas все, что нам нужно сделать, это:

evenlength(Xs) :- 
    foldl(\_^E^O^(O is \E),Xs,1,1). % each item in `Xs` flips the "evenness flag" 

Пример использования:

?- evenlength([]). 
true. 

?- evenlength([_]). 
false. 

?- evenlength([_,_]). 
true. 

?- evenlength([_,_,_]). 
false. 

?- evenlength([_,_,_,_]). 
true. 

Давайте не будем забывать и о самом общем запросе!

?- evenlength(Xs). 
    Xs = [] 
; Xs = [_A,_B] 
; Xs = [_A,_B,_C,_D] 
; Xs = [_A,_B,_C,_D,_E,_F] 
...