CODEWITHSUNDEEP
listprolog
Jon
Jon

Reputation: 278

How do I keep track of values in Prolog?

I am new to Prolog and am having some difficulties coming from OOP. I need to recursively run through some characters, but remember what I have gone through. In OOP I would just create an array or arraylist to keep track of anything I have used. However, I can't seem to find a similar way to do this in Prolog. How would I check to see what I've used already.

The exact problem is I want to run through a set of characters and stop if I come to the same one twice essentially. My thought was to add each one to a list and check to see if the next one is a member of the list.

Any help is appreciated

Thank you

Upvotes: 3

Views: 977

Answers (5)

Paulo Moura
Paulo Moura

Reputation: 18663

Adding each found character to a list and then using this list to check if you got a character twice will be linear on the size of the list of of found characters. This may or may not be acceptable w.r.t. performance. How many different characters you have? Only ASCII printable characters? Full Unicode? As only some Prolog systems provide arrays, your next best bet for better performance than lists would be a binary search tree, which will give you O(log(n)) in the average case. But you can do better. As you tagged your question swi-prolog, you can use this system read-black tree library (inherited from YAP). This should provide you also with O(log(n)) in the worst case. Using this library (as an alternative to using lists as in the other answers), you could write something along the lines:

:- 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 worthy (performance-wise) alternative to using a list? You don't provide enough details to answer that. Best to run some tests. Also worth noting that insertion in a list is O(1) (when you do Head + List -> [Head| List]) but insertion in a red-black tree is O(log(n)).

Upvotes: 0

migfilg
migfilg

Reputation: 542

I think the question is how to find the suffix of the list that starts with the first repeated element. If I am right, the implementation can be along the following lines: find an element that is repeated and use for that a predicate that returns the required suffix or fails, and if there are no duplicates the suffix is empty. An implementation that assumes the first argument to be a properly closed list with no free variables can 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).

Sample runs:

?- 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

Upvotes: 0

repeat
repeat

Reputation: 18726

The following is based on @Boris's answer; you could also preserve by using the goal maplist(dif(X),Seen) instead of \+ memberchk(X,Seen):

foo([],_).                   % 1
foo([X|Xs],Seen) :-          % 2
    maplist(dif(X),Seen),    % 3
    foo(Xs,[X|Seen]).        % 4

Upvotes: 2

user1812457
user1812457

Reputation:

The 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 seen (3)
    • if not (\+ X stands for "succeed when X fails"), add the element to the list of seen elements and check the rest of the list (4).

But this is not something you should actually write I think? Since it is not clear what your final goal is, it is difficult to suggest a better solution.

Some hints:

Upvotes: 1

David Hoelzer
David Hoelzer

Reputation: 16351

You may find this useful: Prolog iterating over list Essentially, Prolog does not have iteration, but it does have recursion. You will need to recurse through the list to do what you are trying to do.

Upvotes: 0

Related Questions