Prolog Insert the number in the list by the tail

Question

How can I build a predicate in prolog that receives a number and a list, I must insert the number in the list by the tail

I tried inserting the number in the list by the head: insert(H,[P|Q],[H,P|Q]). and it works, but how can I do it by the tail?

Answer 1

Inserting at the tail can be done with a two-part recursive rule:

• When the list is empty, unify the result to a single-element list with the item being inserted
• When the list is not empty, unify the result to a head followed by the result of inserting into the tail of a tail.

English description is much longer than its Prolog equivalent:

ins_tail([], N, [N]).
ins_tail([H|T], N, [H|R]) :- ins_tail(T, N, R).

Demo.

Answer 2

Simply use append/3 like this:

?- append([a,b,c,d],[x],List).
List = [a,b,c,d,x].

Answer 3

Nobody talked about difference lists yet.

Difference lists

Difference lists are denoted L-E, which is just a convenient notation for a couple made of a list L whose last cons-cell has E for its tail:

L = [ V1, ..., Vn | E]

The empty difference list is E-E, with E a variable. You unify E whenever you want to refine the list. For example, if you want to add an element X, you can unify as follows:

E = [X|F]

And then, L-F is the new list. Likewise, you can append lists in constant time. If you unify F with a "normal" list, in particular [], you close your open-ended list. During all operations, you retain a reference to the whole list through L. Of course, you can still add elements in front of L with the ususal [W1, ..., Wm |L]-E notation.

Whether or not you need difference lists is another question. They are intereseting if adding an element at the end is effectively a common operation for you and if you are manipulating large lists.

Definite clause grammars

DCG are a convenient way of writing grammar rules in Prolog. They are typically implemented as reader macros, translating --> forms into actual predicates. Since the purpose of grammars is to build structures during parsing (a.k.a. productions), the translation to actual predicates involves difference lists. So, even though both concepts are theoretically unrelated, difference lists are generally the building material for DCGs.

The example on wikipedia starts with:

 sentence --> noun_phrase, verb_phrase.

... which gets translated as:

 sentence(S1,S3) :- noun_phrase(S1,S2), verb_phrase(S2,S3).

A lot of "plumbing" is provided by the syntax (a little like monads). The object being "built" by sentence/2 is S1, which is built from different parts joined together by the predicates. S1 is passed down to noun_phrase, which builds/extends it as necessary and "returns" S2, which can be seen as "whatever extends S1". This value is passed to verb_phrase which updates it and gives S3, a.k.a. whatever extends S2. S3 is an argument of sentence, because it is also "whatever extends S1", given the rule we have. But, this is Prolog, so S1, S2 and S3 are not necessarly inputs or outputs, they are unified during the whole process, during which backtracking takes place too (you can parse ambiguous grammars). They are eventually unified with lists.

Difference lists come to play when we encounter lists on the right-hand side of the arrow:

det --> [the].

The above rule is translated as:

det([the|X], X).

That means that det/2 unifies its first argument with an open-ended list which tail is X; other rules will unify X. Generally, you find epsilon rules which are associated with [].

All the above is done with macros, and a typical error is to try to call an auxiliary predicate on your data, which fails because the transformation add two arguments (a call to helper(X) is in fact a call to helper(X,V,W)). You must enclose actual bodies between braces { ... } to avoid treating prediates as rules.

Answer 4

Here is an another option.

insert(N,[],[N]).
insert(N,[H|T],[H|Q]) :- conc([H|T],[N],[H|Q]).
conc([],L,L).
conc([H|T],L,[H|Q]) :- conc(T,L,Q).