расширение списка списков одним элементом

Question

Я пытаюсь решить следующий вопрос в ProLog. Я новичок.

Определите предикат extend так, чтобы, если Xss и Yss были списками списки, то extend(X, Xss, Yss) выполняется, если Yss можно получить, добавив элемент X до конца каждого элемента в Xss, например,

?- extend(g, [[e], [b, c, f], [k, h]], Yss).

Yss = [[e, g], [b, c, f, g], [k, h, g]]

Я попытался сделать следующее, но есть сообщение об ошибке:

extend(X, [], []).

extend(X, [[Firstxss,_] | Restxss], Yss) :-
    Firstxss is [Firstxss,_|X],
    Yss is  [Yss | [Firstxss,_]],        
    Xss is Restxss,
    extend(X, Xss, Yss).

Я ввел следующее:

?- extend(g, [[e], [b, c, f], [k, h]], Yss).

и возвращается:

false.

Я думаю, что у меня есть правильный ввод, и я не понимаю, почему он возвращается как false.

Answer 1

Поскольку вы хотите сделать то же самое с каждым элементом внешнего списка, это довольно красивая задача для maplist/3. Вы можете использовать append/3 для расширения списка дополнительным элементом, например:

?- append([1,2],[element],Z).
Z = [1, 2, element].

Однако вы захотите иметь append/3 с двумя недостающими аргументами в maplist/3, поэтому было бы целесообразно добавить первый аргумент ко второму аргументу. Чтобы понять это, вы можете написать вспомогательный предикат, который вызывает append/3 с перевернутыми первыми двумя аргументами, например:

flippedappend(X,Y,Z) :-
   append(Y,X,Z).

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

x_lists_extended(X,Xss,Yss) :-
   maplist(flippedappend([X]),Xss,Yss).

Ваш пример запроса дает желаемый результат:

?- x_lists_extended(g, [[e], [b, c, f], [k, h]], Yss).
Yss = [[e, g], [b, c, f, g], [k, h, g]].

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

?- x_lists_extended(X, Xss, [[e, g], [b, c, f, g], [k, h, g]]).
X = g,
Xss = [[e], [b, c, f], [k, h]] ;
false.

Answer 2

Во-первых, у вас есть одноэлементная переменная X здесь:

extend(X, [], []).

Было бы лучше сказать extend(_, [], []), потому что вы никогда больше не обращаетесь к X. Важно понять, почему это так. В Прологе все действие происходит из-за отношений, в которых находятся переменные. Если переменная появляется только в одном месте, она не участвует ни в каких отношениях, поэтому ее следует заменить на _. (Если вы делаете такое изменение, а код кажется бессмысленным, остановитесь и изучите его, потому что это всегда означает, что вы что-то неправильно поняли.)

Во-вторых, is/2 для оценки арифметических выражений. В этом нет математики: Firstxss is [Firstxss,_|X], поэтому вы перепутали это с =. Это действительно двойной удар, потому что = действительно не означает присвоение в Прологе, это означает унификация . Так что в Прологе нет реальной ситуации, когда у вас будет X = X+1 или что-то подобное, что именно то, что вы делаете здесь, пытаясь повторно использовать переменную для различных целей.

Что означает Firstxss в этом пункте? Похоже, что это первый элемент во вложенном списке во втором аргументе в заголовке: другими словами, если вы вызвали extend(g, [[e], [b, c, f], [k, h]], Yss), то Firstxss = e. Значение Firstxss никогда не может измениться . Это может быть восстановлено только в рекурсивном вызове. Поэтому, когда вы сразу говорите Firstxss is [Firstxss,_|X], то, что видит Пролог b = [b,_|<another var>]. Это не объединяет, и ваш предикат терпит неудачу в этой точке. Скажи это как-то продвинуто. Вы делаете ту же ошибку в следующей строке с Yss.

Это помогло бы подумать о вашей проблеме в отношениях. У вас тоже неверный базовый вариант. Каков ваш базовый случай? Это тот случай, когда вы достигли конца списка, и что вам делать? Добавить X. Итак, это ваш базовый случай:

extend(X, [], [X]).

Теперь подумайте, что вы хотите сделать в других случаях: у вас есть голова и хвост. Как вы продлите? Вы расширяете хвост, и ваш результат - голова, прикрепленная к удлиненному хвосту. Попробуйте сами написать это предложение, это не так сложно!

Как только вы это сделаете, механизм расширения вложенных списков прост: вы проверяете голову, чтобы убедиться, что это список. Если это так, вернитесь на голову и хвост! Вот так:

extend(X, [Y|Ys], Result) :-
  (is_list(Y) -> extend(X, Y, Y1) ; Y1 = Y),
  ... % use Y1 as Y in building the result