Easily replicate an element in Prolog :)

Question

I am working on a longer problem that has me duplicate an element N times in list form, and I believe that using append is the right way to go for this. The tiny predicate should theoretically act like this:

?- repl(x,5,L).
L = [x, x, x, x, x] ;
false.

I cannot seem to find any tips for this online, the replication of a single element, but I believe we need to use append, but no recursive solution. I come from more of a Haskell background, where this problem would be much easier to perform. Can someone help get me started on this? :)

Mine so far:

repl(E, N, R) :-
    N > 0, append([E], [], R), writeln(R), repl(E, N-1, R), fail.

Which gives me:

?- repl(x,5,L).
[x]
[x]
[x]
[x]
[x]
false.

Close but not quite!

Answer 1

A recursive approach would be straight-forward and would work. I recommend figuring that one out. But here's a fun alternative:

repl(X, N, L) :-
    length(L, N),
    maplist(=(X), L).

If N is instantiated, then length(L, N) will generate a list of length N of just "blanks" (don't care terms). Then maplist(=(X), L) will unify each element of L with the variable X.

This gives a nice, relational approach and yields sensible results in the general case:

| ?- repl(X, N, L).

L = []
N = 0 ? ;

L = [X]
N = 1 ? ;

L = [X,X]
N = 2 ? ;
| ?- repl(X, N, [x,x,x]).

N = 3
X = x

yes
...

To figure out a recursive case, think about what your base case looks like (it would be repl with a count of 0 - what does the list look like then?). In the recursive case, think in terms of:

repl(X, N, [X|T]) :- ...

Meaning: The list [X|T] is the element X repeated N times if.... Figure out if what? If your base case is length 0, then your recursion is probably going to describe the repl of a list of length N in terms of the repl of a list of length N-1. Don't forget in this recursive rule to ensure N > 0 to avoid infinite recursion on backtracking. If you don't need the predicate to be purely relational and assume N is instantiated, then it can be fairly simple.

If you make a simple recursive version, you can "wrap" it in this predicate to make it work with variable N:

repl(X, N, L) :-
    length(L, N),
    simple_recursive_repl(X, N, L).

...

Because length/2 is relational, it is much more useful than just providing the length o a given list. When N and L are not instantiated, it becomes a generator of variable lists, starting at length 0. Type, length(L, N). at the Prolog prompt and see what happens.

Answer 2

Determinism

You give the following example of the predicate you envision:

?- repl(x,5,L).
L = [x, x, x, x, x] ;
false.

Notice that the ; is not very productive here. If you want to repeat x 5 times, then this can be done in exactly one way. I would therefore specify this predicate as deterministic not nondeterministic as you are doing.

Repeating list

Your code is actually quite far off a working solution, despite the output looking quite close in spirit to the envisioned result. You try to define the base case and the recursive case at the same time, which will not work.

Here is a simple (but less fun than @lurker gave :-)) implementation of the base and recursive case:

repeating_list(_, 0, []):- !.
repeating_list(H, Reps1, [H|T]):-
  Reps2 is Reps1 - 1,
  repeating_list(H, Reps2, T).

In a sense @lurker's implementation is simpler, and it is surely shorter.

Some extensions

In real-world/production code you would like to catch type errors and treat different instantiations with the same predicate. The second clause checks whether a given list consists of repeating elements (and if so, which one and how many occurrences there are).

%! repeating_list(+Term:term, +Repeats:integer, -List:list(term)) is det.
%! repeating_list(?Term:term, ?Repeats:integer, +List:list(term)) is det.

repeating_list(_, 0, []):- !.
% The term and number of repetitions are known given the list.
repeating_list(H, Reps, L):-
  nonvar(L), !,
  L = [H|T],
  forall(
    member(X, T),
    % ==/2, since `[a,X]` does not contain 2 repetitions of `a`.
    X == H
  ),
  length([H|T], Reps).
% Repetitions is given, then we generate the list.
repeating_list(H, Reps1, [H|T]):-
  must_be(nonneg, Reps1), !,
  Reps2 is Reps1 - 1,
  repeating_list(H, Reps2, T).
% Repetitions is not `nonneg`.
repeating_list(_, Reps, _):-
  domain_error(nonneg, Reps).

Notice that I throw a domain error in case the number of repetitions is negative. This uses library error in SWI-Prolog. If your Prolog does not support this feature, then you may leave the last clause out.

PS: Comparison to Haskell

The combination of your statement that you do not know how to solve this problem in Prolog and your statement that this problem can be solved much easier in Haskell seems a little strange to me. I think you can only compare the difficulty of two implementations once you know how both of them look like.

Answer 3

I do prefer findall/3 to build lists, and between/3 to work with ranges:

repl(E, N, L) :- findall(E, between(1, N, _), L).