How to add 3 lists to Prolog?
To add lists effectively, use Difference Lists. A list of differences is a list expressed using the term with two lists. The most common representation is used (-)/2
as a functor for this term. For example, a list [1,2,3]
can be expressed as:
[1,2,3| Tail]-Tail.
By tracking the tail of a list, that is, its open end, you can perform multiple operations efficiently. For example, you can add an element to the end of the list in O (1) by instantiating the tail:
add_to_end_of_list(List-Tail, Element, List-Tail2) :-
Tail = [Element| Tail2].
Or simply:
add_to_end_of_list(List-[Element| Tail2], Element, List-Tail2).
Try:
?- add_to_end_of_list([1,2,3| Tail]-Tail, 4, Result). Tail = [4|_G1006], Result = [1, 2, 3, 4|_G1006]-_G1006.
Now adding two lists is similar and also O (1). Instead of adding an element, we want to add a list of elements:
dappend(List1-Tail1, Tail1-Tail2, List1-Tail2).
For example:
?- dappend([1,2,3 | Tail1]-Tail1, [4,5,6| Tail2]-Tail2, Result). Tail1 = [4, 5, 6|Tail2], Result = [1, 2, 3, 4, 5, 6|Tail2]-Tail2.
I leave an exercise for you to answer your own question using delta lists. Note that going from a diff to a closed list is simply a matter of creating an open end to an empty list. For example:
?- dappend([1,2,3 | Tail1]-Tail1, [4,5,6| Tail2]-Tail2, Result-[]). Tail1 = [4, 5, 6], Tail2 = [], Result = [1, 2, 3, 4, 5, 6].
However, going from a closed list to a diff list requires you to traverse the list, which is O (n):
as_difflist([], Back-Back).
as_difflist([Head| Tail], [Head| Tail2]-Back) :-
as_difflist(Tail, Tail2-Back).
The cost of creating diffs may or may not be an issue, of course, depending on how you get the original lists and how often you add the lists in your application.
source to share
append3(Xs, Ys, Zs, XsYsZs) :-
append(Xs, YsZs, XsYsZs),
append(Ys, Zs, YsZs).
Is as effective as possible. Cost about | Xs
| + | Ys
| inferences. However, you could try to define it like this: about 2 | Xs
| + | Ys
| inferences.
append3bad(Xs, Ys, Zs, XsYsZs) :-
append(Xs, Ys, XsYs),
append(XsYs, Zs, XsYsZs).
Also, completion is much better in the first case :
append3(Xs, Ys, Zs, XsYsZs)
terminates_if b(Xs),b(Ys);b(XsYsZs)
means that either Xs
, or, Ys
or XsYsZs
must be known to make it append3/4
complete ... against
append3bad(Xs, Ys, Zs, XsYsZs)
terminates_if b(Xs),b(Ys);b(Xs),b(XsYsZs)
^^^^^
for append3bad/4
where it is XsYsZs
not enough, but also must be known Xs
.
source to share