prolog empty list error when reversing a list-CodePudding

First of all I'm very new to Prolog and just trying to understand the very basics.

I have to work a simple function that concatenes two lists and a function that reverses a list.

This implementation:

cconcat([], L, L).

cconcat([H1|T1], L2, [H1|T2]) :- cconcat(T1, L2, T2).

revv([], []).
revv(R, [H|T]) :- revv(R1, T), cconcat(R1,[H],R).

works well, but this one

cconcat([], L, L).

cconcat([H1|T1], L2, [H1|T2]) :- cconcat(T1, L2, T2).

revv(R, []) :- R is []. 
revv(R, [H|T]) :- revv(R1, T), cconcat(R1,[H],R).

gives me this error : Type error: `evaluable' expected, found `[]'.

Why is that? Aren't they equivalent?

CodePudding user response：

R is [].

is the same as this rewrite:

is(R, []).

is() was made for this kind of use:

?- is(Answer, 4   2 * 3).
Answer = 10

is() wants some math it can evaluate; that's what the error message means, it doesn't know how to evaluate an empty list. R = [] will work there, but your first version is better.

CodePudding user response：

For concatenation, you have 3 special cases:

The concatenation of two empty lists is the empty list itself:
```
concatenate_lists( [] , [] , [] ) .
```
The concatenation of the empty list and a non-empty list is the non-empty list:
```
concatenate_lists( [] , [Y|Ys] , [Y|Ys] ) .
```
The concatenation of a non-empty list and the empty list is the non-empty list:
```
concatenate_lists( [X|Xs] , [] , [X|Xs] ) .
```

And the general case of 2 non-empty lists, for which we copy elements from the left list and recurse down (until we collapse into a special case that terminates the recursion):

concatenate_lists([X|Xs], [Y|Ys] , [X|Zs] ) :- concatenate_lists(Xs,[Y|Ys],Zs).

Putting it all together you get:

concatenate_lists( []     , []     , []     ) .
concatenate_lists( [X|Xs] , []     , [X|Xs] ) .
concatenate_lists( []     , [Y|Ys] , [Y|Ys] ) .
concatenate_lists( [X|Xs] , [Y|Ys] , [X|Zs] ) :- concatenate_lists(Xs,[Y|Ys],Zs) .

Reversing a list is easier. Here, we use a helper predicate, reverse_list/3 that carries an extra argument that maintains state:

reverse_list( Xs, Ys ) :- reverse_list( Xs, [] , Ys ) .

reverse_list( []     , Zs , Zs ) .  % if the source list is exhausted, we're done
reverse_list( [X|Xs] , Ys , Zs ) :- % otherwise, prepend the head of the source list to the accumulator
  reverse_list(Xs,[X|Ys],Zs) .      % and recurse down.