Prolog intersection of list elements

0
votes

I have a list of 8 elements:

[[a], [a], [a, b], [b, c], [c, d, e], [d, f], [f], [f]]

The goal is to have a list with intersection of adjacent elements:

[[a], [a], [b], [c], [d], [f], [f]]

What's the best way to do that in Prolog?

1
listprologintersection
What did you try, what is not working with it? - Willem Van Onsem
I tried to do it with intersection and maplist function, but I failed. I cannot get used to this kind of programming. - Yakimget

1 Answers

1
votes

Recall that Prolog allows you to use pattern matching on lists: [X|XS] matches a non-empty list, with first element X and XS being the remaining list. You can extend that to [X,Y|ZS], which matches lists with at least two elements X and Y, and ZS being the remaining list.

The standard library offers intersection/3 to get the intersection of two lists.

merge_adj([],[]).
merge_adj([_],[]) :- !.
merge_adj([X,Y|ZS], [M|MS]) :- intersection(X,Y,M), merge_adj([Y|ZS], MS).

?- merge_adj([[a], [a], [a, b], [b, c], [c, d, e], [d, f], [f], [f]], Z).
Z = [[a], [a], [b], [c], [d], [f], [f]].

The cut ! in the second rule isn't strictly needed, but prevents Prolog from trying (and failing) to apply the third rule after the second rule for lists with exactly one element. This way, no further solution will be sought for after the finding the unique solution.