Почему этот предикат оставляет точку выбора?

Я написал следующий предикат:

list_withoutlast([_Last], []). % forget the last element
list_withoutlast([First, Second|List], [First|WithoutLast]) :-
  list_withoutlast([Second|List], WithoutLast).

Запросы типа list_withoutlast(X, [1, 2]). успешны детерминистически, но запросы типа list_withoutlast([1, 2, 3], X) оставляют после себя точку выбора, даже если есть только один ответ.

Когда я отслеживаю, кажется, что SWI пытается сопоставить list_withoutlast([3], Var) с обоими предложениями, хотя определенно только первое из них будет когда-либо совпадать!

Есть ли что-то еще, что я могу сделать, чтобы сообщить SWI, что мне нужен список с более чем одним элементом? Или, если я хочу воспользоваться индексацией по первому аргументу, есть ли у меня единственные варианты «список нулевой длины» и «список ненулевой длины»?

Обрабатывают ли другие Прологи эту ситуацию по-другому?


indexing prolog termination
person num1    schedule 11.07.2018    source источник
comment
@Paulo Почему вы удалили тег SWI-Prolog?   -  person num1    schedule 11.07.2018
comment
Вопрос общий. Таким образом, используя общий тег Prolog, мы сообщаем другим, что та же проблема и решения применимы к другим реализациям Prolog.   -  person Paulo Moura    schedule 11.07.2018

Ответы (1)


arrow_upward
3
arrow_downward

Вы можете переписать свой предикат, чтобы избежать ложной точки выбора:

list_withoutlast([Head| Tail], List) :-
    list_withoutlast(Tail, Head, List).

list_withoutlast([], _, []).
list_withoutlast([Head| Tail], Previous, [Previous| List]) :-
    list_withoutlast(Tail, Head, List).

В этом определении используется индексация по первому аргументу, которая позволяет отличить в предикате list_withoutlast /3 первое предложение, в котором есть атом (пустой список) в первом аргументе, от второго предложения, в котором есть (непустой) список в первый аргумент.

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

Обратите внимание, что большинство систем Prolog не применяют глубокое индексирование терминов. В частности, для составных терминов при индексировании обычно учитываются только имя и арность, но не учитываются аргументы составного термина (список с одним элементом и список с двумя или более элементами используют один и тот же функтор).

person Paulo Moura    schedule 11.07.2018