Lists can be represented with two function symbols – cons and nil where cons is

Question

Lists can be represented with two function symbols – cons and nil where cons is binary and nil is nullary. The empty list is represented by the term nil and the list with head element H and tail list L is represented by the term cons(H,L).

The following two clauses define the predicate concat such that concat(Xs, Ys, Zs) is true if and only if list Zs is the concatenation of list Xs and list Ys.

concat(nil, Xs, Xs).
concat(cons(H,Xs), Ys, cons(H,Zs)) :- concat(Xs, Ys, Zs).

The query ?- concat(Xs, Ys, cons(a,cons(b,nil))) has four successful SLD derivations.

Draw the SLD tree for the above query. Annotate the edges with the most general unifiers.

Explanation / Answer

The SLD Derivations are given below:

¬Xs,¬Ys,false

- concat(Xs, ¬Ys, Zs)

-concat(nil, ¬Xs, ¬Xs)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.