Add two more occurrences using prolog

Question

I have a list [a, b, a, a, a, c, c] and I need to add two more occurrences of each element.

The end result should look like this:

[a, a, a, b, b, b, a, a, a, a, a, c, c, c, c]

If I have an item on the list that is the same as the next item, then it keeps going until there is a new item, when it finds the new item, it adds two occurrences of the previous item then moves on.

This is my code so far, but I can't figure out how to add two...

dbl([], []).
dbl([X], [X,X]).
dbl([H|T], [H,H|T], [H,H|R]) :- dbl(T, R).

Answer 1

Your code looks a bit strange because the last rule takes three parameters. You only call the binary version, so no recursion will ever try to derive it.

You already had a good idea to look at the parts of the list, where elements change. So there are 4 cases:

1) Your list is empty. 2) You have exactly one element. 3) Your list starts with two equal elements. 4) Your list starts with two different elements.

Case 1 is not specified, so you might need to find a sensible choice for that. Case 2 is somehow similar to case 4, since the end of the list can be seen as a change in elements, where you need to append two copies, but then you are done. Case 3 is quite simple, we can just keep the element and recurse on the rest. Case 4 is where you need to insert the two copies again.

This means your code will look something like this:

% Case 1
dbl([],[]).
% Case 2
dbl([X],[X,X,X]).
% Case 3
dbl([X,X|Xs], [X|Ys]) :-
   % [...] recursion skipping the leading X
% Case 4
dbl([X,Y|Xs], [X,X,X|Ys]) :-
   dif(X,Y),
   % [...] we inserted the copies, so recursion on [Y|Xs] and Ys

Case 3 should be easy to finish, we just drop the first X from both lists and recurse on dbl([X|Xs],Ys). Note that we implicitly made the first two elements equal (i.e. we unified them) by writing the same variable twice.

If you look at the head of case 4, you can directly imitate the pattern you described: supposed the list starts with X, then Y and they are different (dif(X,Y)), the X is repeated 3 times instead of just copied and we then continue with the recursion on the rest starting with Y: dbl([Y|Xs],Ys).

So let's try out the predicate:

?- dbl([a,b,a,a,a,c,c],[a,a,a,b,b,b,a,a,a,a,a,c,c,c,c]).
true ;
false.

Our test case is accepted (true) and we don't find more than one solution (false). Let's see if we find a wrong solution:

?- dif(Xs,[a,a,a,b,b,b,a,a,a,a,a,c,c,c,c]), dbl([a,b,a,a,a,c,c],Xs).
false.

No, that's also good. What happens, if we have variables in our list?

?- dbl([a,X,a],Ys).
X = a,
Ys = [a, a, a, a, a] ;
Ys = [a, a, a, X, X, X, a, a, a],
dif(X, a),
dif(X, a) ;
false.

Either X = a, then Ys is single run of 5 as; or X is not equal to a, then we need to append the copies in all three runs. Looks also fine. (*)

Now lets see, what happens if we only specify the solution:

?- dbl(X,[a,a,a,b,b]).
false.

Right, a list with a run of only two bs can not be a result of our specification. So lets try to add one:

?- dbl(X,[a,a,a,b,b,b]).
X = [a, b] ;
false.

Hooray, it worked! So lets as a last test look what happens, if we just call our predicate with two variables:

?- dbl(Xs,Ys).
Xs = Ys, Ys = [] ;
Xs = [_G15],
Ys = [_G15, _G15, _G15] ;
Xs = [_G15, _G15],
Ys = [_G15, _G15, _G15, _G15] ;
Xs = [_G15, _G15, _G15],
Ys = [_G15, _G15, _G15, _G15, _G15] ;
Xs = [_G15, _G15, _G15, _G15],
Ys = [_G15, _G15, _G15, _G15, _G15, _G15] ;
[...]

It seems we get the correct answers, but we see only cases for a single run. This is a result of prolog's search strategy(which i will not explain in here). But if we look at shorter lists before we generate longer ones, we can see all the solutions:

 ?- length(Xs,_), dbl(Xs,Ys).
Xs = Ys, Ys = [] ;
Xs = [_G16],
Ys = [_G16, _G16, _G16] ;
Xs = [_G16, _G16],
Ys = [_G16, _G16, _G16, _G16] ;
Xs = [_G86, _G89],
Ys = [_G86, _G86, _G86, _G89, _G89, _G89],
dif(_G86, _G89) ;
Xs = [_G16, _G16, _G16],
Ys = [_G16, _G16, _G16, _G16, _G16] ;
Xs = [_G188, _G188, _G194],
Ys = [_G188, _G188, _G188, _G188, _G194, _G194, _G194],
dif(_G188, _G194) ;
[...]

So it seems we have a working predicate (**), supposed you filled in the missing goals from the text :)

(*) A remark here: this case only works because we are using dif. The first predicates with equality, one usually encounters are =, == and their respective negations \= and \==. The = stands for unifyability (substituting variables in the arguments s.t. they become equal) and the == stands for syntactic equality (terms being exactly equal). E.g.:

?- f(X) = f(a).
X = a.

?- f(X) \= f(a).
false.

?- f(X) == f(a).
false.

?- f(X) \== f(a).
true.

This means, we can make f(X) equal to f(a), if we substitute X by a. This means if we ask if they can not be made equal (\=), we get the answer false. On the other hand, the two terms are not equal, so == returns false, and its negation \== answers true.

What this also means is that X \== Y is always true, so we can not use \== in our code. In contrast to that, dif waits until it can decide wether its arguments are equal or not. If this is still undecided after finding an answer, the "dif(X,a)" statements are printed.

(**) One last remark here: There is also a solution with the if-then-else construct (test -> goals_if_true; goals_if_false, which merges cases 3 and 4. Since i prefer this solution, you might need to look into the other version yourself.