Глубокий Реверс в PROLOG - Списки

Эй, я пытаюсь создать предикат для генерации глубокого реверса во вложенных списках в PROLOG.

В настоящее время я получил этот предикат

reverse(L,A) :- rev(L,[], A).
rev([],A,A).
rev([H|L],R,A) :- rev(L,[H|R],A).

Результат выглядит так:

reverse([1,2,3],A).
A = [3, 2, 1].

reverse([[0,1],2,3],A).
A = [3, 2, [0, 1]].

Проблема в том, что внутренний список не перевернут. Это должно выглядеть так:

reverse([[0,1],2,3],A).
A = [3, 2, [1, 0]].

reverse([1,2,[3,4,5,[6,7],8],[9,10],11,12],A).
A = [12,11,[10,9],[8,[7,6],5,4,3],2,1].

Спасибо за любую помощь.

Источник

3 ответа

Решение

Чтобы все было как можно проще, мы могли бы добавить тест, если текущий проверяемый элемент является списком или нет. Если это действительно список, то его элементы также должны быть обращены. Итак, в коде:

my_reverse(L,R) :- rev(L,[],R).

rev([],A,A).
rev([H|T],A,R) :-
    ( is_list(H) ->        % If H is a list
      rev(H,[],X),         %   then reverse H as well
      rev(T,[X|A],R)
    ;
      rev(T,[H|A],R)
    ).

Кроме того, это не так важно, просто чтобы попытаться избежать путаницы, обратите внимание, как я использовал A а также R для соответственно Accumulator а также Result, В вашем коде они в настоящее время поменяны местами, что, лично для меня, может немного запутать, особенно когда предикаты становятся длиннее и сложнее.

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

?- my_reverse([[0,1],2,3],R).
R = [3, 2, [1, 0]].

?- my_reverse([1,2,[3,4,5,[6,7],8],[9,10],11,12],R).
R = [12, 11, [10, 9], [8, [7, 6], 5, 4, 3], 2, 1].

И некоторые общие вопросы:

?- my_reverse(L,R).
L = R, R = [] ;
L = R, R = [_G2437] ;
L = [_G2437, _G2443],
R = [_G2443, _G2437] ;
L = [_G2437, _G2443, _G2449],
R = [_G2449, _G2443, _G2437] ;
L = [_G2437, _G2443, _G2449, _G2455],
R = [_G2455, _G2449, _G2443, _G2437] 
...

?- my_reverse([[X,Y]|T],R), member(a,T), length(X,2).
X = [_G2588, _G2591],
T = [a],
R = [a, [Y, [_G2588, _G2591]]]
;
X = [_G2594, _G2597],
T = [a, _G2588],
R = [_G2588, a, [Y, [_G2594, _G2597]]]
;
X = [_G2594, _G2597],
T = [_G2582, a],
R = [a, _G2582, [Y, [_G2594, _G2597]]]
...

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

?- my_reverse(X,[X]).
X = [X] ;
...

Но так как это не было требованием / требованием в вопросе ОП, я предположил, что все в порядке.

РЕДАКТИРОВАТЬ:

Пожалуйста, прочитайте ответ @mat как продолжение этой проблемы.

Источник

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

  • это список? → что-то держит
  • в противном случае → что-то еще имеет место.

Такое представление является богатым источником неприятностей. Рассмотрим для примера my_reverse/2 из другого ответа. Основная проблема заключается в том, что он преждевременно и неправильно фиксирует один из случаев, хотя оба случая все еще возможны:

? - my_reverse ([X], Ls).
Ls = [X].

Но этот ответ справедлив только для случая, когда X это не список! Эта проблема приводит к следующему странному поведению предиката:

? - my_reverse ([X], Ls), X = [1,2,3].
Ls = [[1, 2, 3]],
Х = [1, 2, 3].

Это означает, что даже если X список, его элементы не обращены!

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

Например, что бы вы сказали о следующем способе представления ваших данных:

  • list(Ls) представляет список Ls
  • n(N) представляет число N,

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

Источник

Дополнительное решение для вашей проблемы - использовать cut и встроенный предикат "is_list/1", чтобы проверить, относитесь ли вы к простому термину или списку в текущем вызове. вот код:

deepReverse(List,R):-deepReverseTail(List,[],R).

deepReverseTail([],Acc,Acc).

deepReverseTail([H|T],Acc,R):-             % when H is a list
     is_list(H),                           % check if it's a list.
     !,                                    % cut the process if not. 
     deepReverseTail(H,[],Hrev),           % reverse this current list
     deepReverseTail(T,[Hrev|Acc],R).      % continue the general recursion

deepReverseTail([H|T],Acc,R):- deepReverseTail(T,[H|Acc],R). % when H is a simple term

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

пример вывода:

7 ?- deepReverse([a,[d,f],[],[[k],g]],R)
R = [[g, [k]], [], [f, d], a].
Источник
Другие вопросы по тегам