Вставить элемент в определенном положении

Question

Я начал Пролог (только для себя), и я борюсь с рекурсией.

Я хочу «метод», который вставляет элемент в определенную позицию внутри списка. Что я пытался до сих пор:

insertAt(Element,Position,List,ResultList) 

insertAt(Element,0,L,[Element|L]). 
insertAt(Element,Pos,[E|L],ZL):- 
    Pos1 is Pos-1, 
    insertAt(Element,Pos1,L,ZL), 
    append(E,ZL1,ZL). 

Я нахожу, что довольно сложно, так как я не могу понять, как именно работает рекурсия ...

Может быть кто-то может помочь мне.

Answer 1

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

Например, чтобы понять отношение, полезно начать с самого общего запроса. Это только спрашивает: «Есть ли какое-либо решение вообще, и если да, то как выглядит решение?». В вашем конкретном примере, наиболее общий запрос выглядит следующим образом:

?- insertAt(E, Pos, Ls0, Ls). 

и это почти сразу дает instantiation error из-за не-декларативные арифметические предикаты вы используете:

?- insertAt(E, Pos, Ls0, Ls). 
Pos = 0, 
Ls = [E|Ls0] ; 
ERROR: insertAt/4: Arguments are not sufficiently instantiated 

Кроме того, вы препятствуя хорошему декларативному чтению с использованием императивного имени («insert ...»). Это делает излишне трудно создать чувство для реляционного программирования.

Поэтому я рекомендую вам: (1) Использовать более декларативное имя предиката и (2) использовать символическое представление натуральных чисел, что делает предикат более понятным и более общим.

Я буду использовать номер 0 для представления нуля, а термин s(X) - преемник номера X. См. successor-arithmetics для получения дополнительной информации об этом представлении.

С учетом этих изменений, код становится:

element_at(E, 0, [_|Ls], [E|Ls]). 
element_at(E, s(X), [L|Ls0], [L|Ls]) :- 
     element_at(E, X, Ls0, Ls). 

Чтобы понять эту программу, мы читаем его декларативно: Первый пункт является верноесли позиция 0, а голова финала список E, а хвост ... и т.д. второе предложение является истиннымеслиelement_at(E, X, Ls0, Ls) держится, и глава ... и т.д.

Ну, самый общий запрос теперь работает намного лучше:

 
?- element_at(E, Pos, Ls0, Ls). 
Pos = 0, 
Ls0 = [_G1071|_G1072], 
Ls = [E|_G1072] ; 
Pos = s(0), 
Ls0 = [_G1073, _G1079|_G1080], 
Ls = [_G1073, E|_G1080] ; 
Pos = s(s(0)), 
Ls0 = [_G1073, _G1081, _G1087|_G1088], 
Ls = [_G1073, _G1081, E|_G1088] . 

Обратите внимание, однако, что есть что-то несправедливое здесь происходит: Где ответы на остальные позиции?Для более справедливого перечисления, мы используем length/2, указав заранее длину списков, которые мы рассматриваем один за другим:

 
?- length(Ls0, _), element_at(E, Pos, Ls0, Ls). 
Ls0 = [_G1124], 
Pos = 0, 
Ls = [E] ; 
Ls0 = [_G1124, _G1127], 
Pos = 0, 
Ls = [E, _G1127] ; 
Ls0 = [_G1124, _G1127], 
Pos = s(0), 
Ls = [_G1124, E] . 

А теперь яснее, как различные аргументы взаимодействуют между собой, потому что вы уже видите различные примеры терминов, описываются вашим предикатом.

---

В самом деле, чтобы уменьшить количество аргументов и имена переменных, нам нужно следить, я часто использую DCG notation при описании списков, и я хотел бы показать вам этот альтернативный вариант тоже:

element_at(Element, 0, [_|Ls]) --> 
     [Element], 
     list(Ls). 
element_at(Element, s(X), [L|Ls]) --> 
     [L], 
     element_at(Element, X, Ls). 

list([]) --> []. 
list([L|Ls]) --> [L], list(Ls). 

 
?- length(Ls0, _), phrase(element_at(E, Pos, Ls0), Ls). 
Ls0 = [_G1148], 
Pos = 0, 
Ls = [E] ; 
Ls0 = [_G1148, _G1151], 
Pos = 0, 
Ls = [E, _G1151] ; 
Ls0 = [_G1148, _G1151], 
Pos = s(0), 
Ls = [_G1148, E] . 

После того, как вы прочитаете на ноте dcg, эта версия станет для вас понятной.

---

В конце концов, вы можете сказать: «Ну, это хорошо, но s(X) нотация все еще кажется весьма странным», и вы можете использовать более широко используется индо-арабскую нотацию для целых чисел в ваших программах.

Для этого мы можем просто взять любую из версий сверху и заменить нотацию s(X) декларативной целочисленной арифметикой с ограничениями CLP (FD). Так, например, с первой версией:

:- use_module(library(clpfd)). 

element_at(E, 0, [_|Ls], [E|Ls]). 
element_at(E, X, [L|Ls0], [L|Ls]) :- 
     X #> 0, 
     X #= X0 + 1, 
     element_at(E, X0, Ls0, Ls). 

Это также работает во всех направлениях, точно так, как мы ожидаем от хорошо декларативных и общего предиката:

 
?- length(Ls0, _), element_at(E, Pos, Ls0, Ls). 
Ls0 = [_G2095], 
Pos = 0, 
Ls = [E] ; 
Ls0 = [_G2095, _G2098], 
Pos = 0, 
Ls = [E, _G2098] ; 
Ls0 = [_G2095, _G2098], 
Pos = 1, 
Ls = [_G2095, E] . 

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

Answer 2

Функция Пролога - это соответствие шаблонов, то есть выбор правила на основе предикатных аргументов. Такая особенность является ключом к нотации Prolog, позволяющей компактное описание отношения, особенно для рекурсивных терминов, например списков. Примечание. Списки - это только «синтаксический сахар» для рекурсивных терминов, с обычным функтором (термин «имя», каждый день).

insertAt(Element,0,L,[Element|L]). % ok 
insertAt(Element,Pos,[E|L],[E|ZL]):- % you forgot to cons back E 
    Pos1 is Pos-1, 
    insertAt(Element,Pos1,L,ZL). % done, append is useless 
    %append(E,ZL1,ZL). 

SWI-Prolog имеет nth1/4 и nth0/4, который может выполнить вставку:

?- nth0(1,L,x,[1,2,3]). 
L = [1, x, 2, 3]. 

Answer 3

Пусть same_length/2, append/3 и length/2 заботиться о рекурсии!

insertAt(E,N,Xs,Ys) :- 
    same_length ([E|Xs],Ys), 
    append (Before,Xs0,Xs), 
    length (Before,N), 
    append(Before,[E|Xs0],Ys). 

Пример запроса:

 
?- insertAt(X, N, [a,b,c,d,e], Ys). 
( N = 0, Ys = [X,a,b,c,d,e] 
; N = 1, Ys = [a,X,b,c,d,e] 
; N = 2, Ys = [a,b,X,c,d,e] 
; N = 3, Ys = [a,b,c,X,d,e] 
; N = 4, Ys = [a,b,c,d,X,e] 
; N = 5, Ys = [a,b,c,d,e,X] 
; false 
).