разрезание списка на меньший список

В настоящее время я работаю над списком 99 проблем Prolog http://www.ic.unicamp.br/%7Emeidanis/courses/mc336/2009s2/prolog/problemas/ и я отвечаю на вопрос 18. В нем говорится:

Учитывая два индекса, I и K, срез - это список, содержащий элементы между I и K элементом исходного списка (включая оба ограничения). Начните считать элементы с 1.

Пример запроса: ?- slice([a,b,c,d,e,f,g,h,i,k],3,7,L).
Ожидаемый результат: L = [c,d,e,f,g]

Я просмотрел данное решение, но мой вопрос заключался в том, сможет ли кто-нибудь выяснить, почему мое решение было неправильным? Это мой код:

chop([H|_],_,End,End,[H]).
chop([_|L],Start,End,Count,Out) :-
    (Count < Start),
    N is Count + 1,
    chop(L,Start,End,N,Out).
chop([H|L],Start,End,Count,[H|Out]) :-
    (Count >= Start; Count < End),
    N is Count + 1,
    chop(L,Start,End,N,Out).

slice(L,Start,End,Out) :-
    (Start =< End),
    Count is 1,
    chop(L,Start,End,Count,Out).

Ход моих мыслей был таков: если элемент на итерации «Счетчик» находится между двумя заданными пределами, добавьте его в список, если нет, то двигайтесь дальше. В качестве примера вывода для вызова:

?- slice([a,b,c,d,e],2,3,X).

Получаю вывод:

X = [b,c] ? ;
X = [b,c] ? ;
X = [a,b,c] ? ;
X = [a,b,c] ? ;

И для звонка:

?- slice([a,b,c,d,e],3,3,X).
X = [c] ? ;
X = [b,c] ? ;
X = [a,c] ? ;
X = [a,b,c] ? ;

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


list recursion prolog sublist
person user3023621    schedule 30.12.2013    source источник

Ответы (2)


arrow_upward
0
arrow_downward

проблема в том, что ваши правила не исключают друг друга все, что соответствует вашему второму правилу

chop([_|L],Start,End,Count,Out) :-

также будет соответствовать вашему третьему правилу

chop([H|L],Start,End,Count,[H|Out]) :-

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

вы можете решить эту проблему, добавив разрез в конце второго правила

chop([_|L],Start,End,Count,Out) :-
  (Count < Start),
  N is Count + 1,
  chop(L,Start,End,N,Out),
  !.
person Enermis    schedule 30.12.2013
comment
Ах, фантастика, спасибо! Как только вы указали, что они не исключают друг друга, я понял, что это должно было быть: (Count ›= Start, Count‹ End), а не: (Count ›= Start; Count‹ End). Ваше здоровье! - person user3023621; 30.12.2013
comment
Вы можете объяснить, почему это плохой совет? Я знаю, что это красный разрез, а не зеленый разрез. Но я не уверен, почему это плохая практика. - person Enermis; 30.04.2015

arrow_upward
2
arrow_downward

Мы определяем slice/4 на основе append/3 и length/2, как это определено в Прологе Пролога :

slice(AsBsCs,P,Q,Bs) :-
   append(AsBs,_Cs,AsBsCs),
   append(As  , Bs,AsBs  ),
   length([_|As],P),
   length( AsBs ,Q).

Пример запроса, предоставленный OP:

?- slice([a,b,c,d,e,f,g,h,i,k],3,7,Xs).
Xs = [c,d,e,f,g] ;
false.

Давайте обобщим вышеуказанный запрос следующим образом:

?- slice([a,b,c,d,e,f,g,h,i,k],P,7,Xs).
  P = 1, Xs = [a,b,c,d,e,f,g]
; P = 2, Xs =   [b,c,d,e,f,g]
; P = 3, Xs =     [c,d,e,f,g]
; P = 4, Xs =       [d,e,f,g]
; P = 5, Xs =         [e,f,g]
; P = 6, Xs =           [f,g]
; P = 7, Xs =             [g]
; P = 8, Xs =              [] 
; false.

Как насчет обобщения по-другому?

?- slice([a,b,c,d,e,f,g,h,i,k],3,Q,Xs).
; Q =  2, Xs = []
; Q =  3, Xs = [c]
; Q =  4, Xs = [c,d]
; Q =  5, Xs = [c,d,e]
; Q =  6, Xs = [c,d,e,f]
; Q =  7, Xs = [c,d,e,f,g]
; Q =  8, Xs = [c,d,e,f,g,h]
; Q =  9, Xs = [c,d,e,f,g,h,i]
; Q = 10, Xs = [c,d,e,f,g,h,i,k]
; false.

Наконец, мы запускаем запрос, который является обобщением обоих:

?- slice([a,b,c,d,e,f,g,h,i,k],P,Q,Xs).
  P =  1, Q =  0, Xs = []
; P =  1, Q =  1, Xs = [a]
; P =  2, Q =  1, Xs = []
; P =  1, Q =  2, Xs = [a,b]
; P =  2, Q =  2, Xs = [b]
; P =  3, Q =  2, Xs = []
; P =  1, Q =  3, Xs = [a,b,c]
; P =  2, Q =  3, Xs = [b,c]
; P =  3, Q =  3, Xs = [c]
; P =  4, Q =  3, Xs = []
; P =  1, Q =  4, Xs = [a,b,c,d]
; P =  2, Q =  4, Xs = [b,c,d]
; P =  3, Q =  4, Xs = [c,d]
; P =  4, Q =  4, Xs = [d]
; P =  5, Q =  4, Xs = []
; P =  1, Q =  5, Xs = [a,b,c,d,e]
; P =  2, Q =  5, Xs = [b,c,d,e]
; P =  3, Q =  5, Xs = [c,d,e]
; P =  4, Q =  5, Xs = [d,e]
; P =  5, Q =  5, Xs = [e]
; P =  6, Q =  5, Xs = []
; P =  1, Q =  6, Xs = [a,b,c,d,e,f]
; P =  2, Q =  6, Xs = [b,c,d,e,f]
; P =  3, Q =  6, Xs = [c,d,e,f]
; P =  4, Q =  6, Xs = [d,e,f]
; P =  5, Q =  6, Xs = [e,f]
; P =  6, Q =  6, Xs = [f]
; P =  7, Q =  6, Xs = []
; P =  1, Q =  7, Xs = [a,b,c,d,e,f,g]
; P =  2, Q =  7, Xs = [b,c,d,e,f,g]
; P =  3, Q =  7, Xs = [c,d,e,f,g]
; P =  4, Q =  7, Xs = [d,e,f,g]
; P =  5, Q =  7, Xs = [e,f,g]
; P =  6, Q =  7, Xs = [f,g]
; P =  7, Q =  7, Xs = [g]
; P =  8, Q =  7, Xs = []
; P =  1, Q =  8, Xs = [a,b,c,d,e,f,g,h]
; P =  2, Q =  8, Xs = [b,c,d,e,f,g,h]
; P =  3, Q =  8, Xs = [c,d,e,f,g,h]
; P =  4, Q =  8, Xs = [d,e,f,g,h]
; P =  5, Q =  8, Xs = [e,f,g,h]
; P =  6, Q =  8, Xs = [f,g,h]
; P =  7, Q =  8, Xs = [g,h]
; P =  8, Q =  8, Xs = [h]
; P =  9, Q =  8, Xs = []
; P =  1, Q =  9, Xs = [a,b,c,d,e,f,g,h,i]
; P =  2, Q =  9, Xs = [b,c,d,e,f,g,h,i]
; P =  3, Q =  9, Xs = [c,d,e,f,g,h,i]
; P =  4, Q =  9, Xs = [d,e,f,g,h,i]
; P =  5, Q =  9, Xs = [e,f,g,h,i]
; P =  6, Q =  9, Xs = [f,g,h,i]
; P =  7, Q =  9, Xs = [g,h,i]
; P =  8, Q =  9, Xs = [h,i]
; P =  9, Q =  9, Xs = [i]
; P = 10, Q =  9, Xs = []
; P =  1, Q = 10, Xs = [a,b,c,d,e,f,g,h,i,k]
; P =  2, Q = 10, Xs = [b,c,d,e,f,g,h,i,k]
; P =  3, Q = 10, Xs = [c,d,e,f,g,h,i,k]
; P =  4, Q = 10, Xs = [d,e,f,g,h,i,k]
; P =  5, Q = 10, Xs = [e,f,g,h,i,k]
; P =  6, Q = 10, Xs = [f,g,h,i,k]
; P =  7, Q = 10, Xs = [g,h,i,k]
; P =  8, Q = 10, Xs = [h,i,k]
; P =  9, Q = 10, Xs = [i,k]
; P = 10, Q = 10, Xs = [k]
; P = 11, Q = 10, Xs = []
; false.
person repeat    schedule 18.08.2015