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.

a. Depict two of these four successful SLD derivations. For each derivation step, show the renamed clause and the most general unifier.

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.