Пролог списки и рекурсия

Question

У меня проблемы с пониманием надуманной рекурсии в Прологе.

Некоторые предикаты-помощники, которые просто добавляются в начало и конец соответственно:

add_number(Numbers, N, NewNumbers).
add_letter(Letters, L, NewLetters).

Моя цель - взять список букв и цифр и вернуть два списка: список чисел в порядке появления, увеличенный на 1; и список букв в обратном порядке появления. Вот мои рассуждения:

foo([], [], [], [], []).

foo([X|Xs], Nums, NewNums, Letters, Letters) :-
    number(X),
    X1 is X+1,
    add_number(Nums, X1, NewNums),
    foo(Xs, ???, ???, Letters, Letters).

foo([X|Xs], Nums, Nums, Letters, NewLetters) :-
    letter(X),
    add_letter(Letters, X, NewLetters),
    foo(Xs, Nums, Nums, ???, ???).

Второй и четвертый аргументы являются аккумуляторами.

Тогда это должно называться так:

realfoo(Xs, Nums, Letters) :- foo(Xs, [], Nums, [], Letters).

Как мне написать этот код?

Answer 1

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

foo([], NumsR, Nums, Letters, Letters) :-
    reverse(NumsR, Nums).
foo([X|Xs], NumsR, Nums, LettersR, Letters) :-
    % the following is the Prolog syntax for if-then-else;
    % you could also do this with two recursive clauses,
    % but this option is faster because of first-argument indexing
    (number(X) ->
        X1 is X+1,
        foo(Xs, [X1|NumsR], Nums, LettersR, Letters)
    ;
        foo(Xs, NumsR, Nums, [X|LettersR], Letters)
    ).

Answer 2

Я бы сделал это примерно так:

foo( List , Numbers , Letters ) :-
  worker( List , [] , Numbers , [] , Letters ).

worker( []     , Numbers           , Numbers , Letters           , Letters ).
worker( [X|Xs] , NumberAccumulator , Numbers , LetterAccumulator , Letters ) :-
  digit(X),
  X1 is X+1 ,
  append( NumberAccumulator , [X1] , NumberAccumulator1 ) ,
  worker( Xs , NumberAccumulator1 , Numbers , LetterAccumulator , Letters ).
worker( [X|Xs] , NumberAccumulator , Numbers , LetterAccumulator , Letters ) :-
  letter(X) ,
  worker( Xs , NumberAccumulator , Numbers , [X|LetterAccumulator] , Letters ).
worker( [X|Xs] , NumberAccumulator , Numbers , LetterAccumulator , Letters ) :-
  not letter(X) ,
  not digit(X)  ,
  worker( Xs , NumberAccumulator , Numbers , LetterAccumulator , Letters ).

letter( a ). letter( b ). letter( c ). ... letter( z ).
letter('A'). letter('B'). letter('C'). ... letter('Z').

digit('0'). digit('1'). digit('2'). ... digit('9').

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

Answer 3

foo ([], Nums, Nums, Letters, Letters).

foo ([X | Xs], Nums_1, Nums, Letters_1, Letters): - число (Х), Х1 есть Х + 1, add_number (Nums_1, X1, Nums_2), foo (Xs, Nums_2, Nums, Letters_1, Letters).

foo ([X | Xs], Nums_1, Nums, Letters_1, Letters): - буква (X), add_letter (Letters_1, X, Letters_2), foo (Xs, Nums_1, Nums, Letters_2, Letters).

add_number (Nums_1, X, Nums_2): - добавление (Numbs_1, [X], nums_2).

add_letter (Letters_1, X, Letters_2): - добавление (Letters_1, [X], Letters_2).