Prolog lists and recursion

Question

I'm having problems understanding contrived recursion in Prolog.

Some helper predicates that are just append to beginning and end respectively:

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

My goal is to take a list of letters and numbers and return two list: a list of numbers in order of appearance, incremented by 1; and a list of letters in reverse order of appearance. Here's my reasoning:

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, ???, ???).

The second and fourth arguments are accumulators.

Then it is supposed called like this:

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

How do I write this code?

Answer 1

Use the accumulators to build up the lists in reverse order. Don't use add_number or you'll get a quadratic time algorithm, while you can solve this problem in linear time.

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([], Nums, Nums, Letters, Letters).

foo([X|Xs], Nums_1, Nums, Letters_1, Letters) :- number(X), X1 is X+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) :- letter(X), add_letter(Letters_1, X, Letters_2), foo(Xs, Nums_1, Nums, Letters_2, Letters).

add_number(Nums_1,X,Nums_2) :- append(Numbs_1,[X],nums_2).

add_letter(Letters_1,X,Letters_2) :- append(Letters_1,[X],Letters_2).

Answer 3

I'd do it something like this:

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').

Since this is a learning exercise, I'd not defer the reversal of the list: I'd do the obvious and build the list in reverse sequence, despite the performance hit. I believe the point of the exercise is that you need to learn to build lists both ways.