Поиск длины списка в прологе

Question

Я запускаю Пролог и пытаюсь написать небольшую функцию, возвращающую длину списка:

len([],0).
len([XS], Y) :-
    len([X|XS], M),
    Y is M+1.

Моя логика заключается в том, что рекурсивный вызов должен включать конец списка (XS) и увеличивать 1 до предыдущей длины (Y - M+1.)

Это всегда возвращает ложь.

Какие-нибудь мысли?

Answer 1

Вот общая методология отладки и тестирования предикатов Prolog:

Начните с самого общего запроса!

Подумайте об этом: в Прологе вам не нужно составлять некоторые тестовые данные. Вам даже не нужно вообще понимать предикат: просто сдайте свободные переменные! Это всегда профессиональный шаг!

Так что в вашем случае это

?- len(L,N).
L = [],
N = 0 ;
*LOOPS**

Ваше определение не так уж плохо, как вы утверждаете: по крайней мере, оно верно для пустого списка.

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

Warning: user://1:11:
        Singleton variables: [X]

Далее прочитайте рекурсивное правило в направлении стрелки :- то есть справа налево:

Предоставлена len([X|Xs], M) это правда и Y is M+1 верно, при условии, что все это правда, мы можем сделать вывод, что

len([XS], Y) также верно. Таким образом, вы всегда заключаете что-то о списке длины 1 ([Xs]).

Вы должны переформулировать это, чтобы len([X|Xs], M) :- len(Xs, N), Y is M+1,

И вот еще одна стратегия:

Обобщите вашу программу

Удаляя цели, мы можем обобщить программу ¹. Вот мой любимый способ сделать это. Добавляя предикат (*)/1 вот так:

:- op(950,fy, *).

*_.

Теперь давайте удалим все цели из вашей программы:

 Len ([], 0).
len ([XS], Y): -
    * len ([X | XS], M),
    * Y - М + 1. 

Теперь у нас есть обобщение. Еще раз рассмотрим ответы на самый общий запрос:

?- len(L, N).
L = [],
N = 0 ;
L = [_].

Какие? len/2 верно только для списков длиной 0 и 1. Это означает, что даже len([1,2], N) терпит неудачу! Итак, теперь мы точно знаем: что-то в видимой оставшейся части программы должно быть исправлено. По факту, [XS] просто описывает списки длины 1. Так что это должно быть удалено...

---

Хорошая печать:

_{1 Существуют определенные ограничения. По сути, ваша программа должна быть чистой, монотонной.}