How do I keep track of values in Prolog?
I am new to Prolog and am having difficulty with OOP. I need to recursively run through some characters, but remember what I went through. In OOP, I just create an array or arraylist to keep track of everything I have used. However, I cannot find a similar way to do this in Prolog. How can I check what I have already used?
The exact problem is that I want to start a character set and stop if I come across the same thing twice essentially. My thought was to add each of them to the list and check if the next one is a member of the list.
Any help is appreciated
thank
source to share
Following is the answer by @Boris; you can also savelogical-purityusing target maplist(dif(X),Seen)
instead \+ memberchk(X,Seen)
:
foo ([], _). % 1
foo ([X | Xs], Seen): -% 2
maplist (dif (X), Seen) ,% 3
foo (Xs, [X | Seen]). % 4
source to share
Most basic implementation:
foo([], _). % 1
foo([X|Xs], Seen) :- % 2
\+ memberchk(X, Seen), % 3
foo(Xs, [X|Seen]). % 4
- The predicate succeeds when the list is empty (1).
- If the list is not empty (2):
- check if the first element of the list has already been viewed (3)
- if not (
\+ X
means "succeed when X failed"), add the item to the list of visible items and check the rest of the list (4).
But that's not what you should write on, I think? Since it is not clear what your ultimate goal is, it is difficult to come up with a better solution.
Some hints:
- If you just want to see if there are duplicates in the list, you can sort and compare the lengths ;
- consider using ordset instead of a list for the second argument;
- find out what "batteries" are .
You may find this useful: List Iteration Prolog Basically, Prolog does not have iteration, but it does have recursion. You will need to go through the list to do what you are trying to do.
source to share
I think the question is how to find the suffix of the list that starts with the first repeated item. If I am correct, the implementation can be done in the following lines: find the duplicate element and use a predicate for that that returns the required suffix or fail, and if there are no duplicates, the suffix is empty. An implementation assuming the first argument is a properly closed list with no free variables could be
stop([],[]).
stop([X|R],Rr) :-
stop_at(R,X,Rr), !.
stop([_|R],Rr) :-
stop(R,Rr).
stop_at([X|R],X,[X|R]) :- !.
stop_at([_|R],X,Rr) :-
stop_at(R,X,Rr).
Examples of run:
?- stop([a,b,c],R). R = [] ? ; no ?- stop([a,b,c,d,a,e,a,e],R). R = [a,e,a,e] ? ; no ?- stop([b,c,d,c,e],R). R = [c,e] ? ; no
source to share
Adding each found character to a list and then using that list to check if you got a character twice will be linear in the size of the list of found characters. This may or may not be an acceptable wrt presentation. How many different characters do you have? Only ASCII printable characters? Full Unicode? Since only some Prolog systems provide arrays, your best bet for better performance than lists would be a binary search tree, which will give you O (log (n)) on average. But you can do better. As you tagged your questionswi-prolog
, you can use this system to read-black tree library (inherited from YAP). This should give you O (log (n)) worst case too. Using this library (as an alternative to using lists as in other answers), you can write something line by line:
:- use_module(library(rbtrees)).
foo(List) :-
rb_new(Seen),
foo(List, Seen).
foo([], _).
foo([Head| Tail], Seen) :-
( rb_lookup(Head, _, Seen) ->
true
; rb_insert(Seen, Head, _, Seen2),
foo(Tail, Seen2)
).
Is this a decent (performance-wise) alternative to using a list? You are not giving enough detail to answer this. It is best to do some tests. Also worth noting is that the insert in the list of O (1) (when you Head
+ List
→ [Head| List]
), but insert in the red-black tree - O (log (n)) .
source to share