3

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

false
  • 10,264
  • 13
  • 101
  • 209
Jon
  • 278
  • 8
  • 23
  • It would really help if you showed a concrete example of a problem and how you expect your program to behave on it. Otherwise, all you will get is generic suggestions. –  May 08 '15 at 04:29

5 Answers5

2

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
repeat
  • 18,496
  • 4
  • 54
  • 166
  • 2
    For pragmatic reasons, I would delay the choice of implementation until the problem has been properly defined :) but a great answer anyway (+1) –  May 08 '15 at 08:36
1

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:

Community
  • 1
  • 1
  • @repeat Yes, might be a better way to do it, and I explicitly said in my answer that I would not actually write code like this. But for this particular _question_ I don't think that introducing both `maplist` and `dif` improves the answer. I would actually suggest you write an answer of your own, for posterity. –  May 08 '15 at 05:58
0

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.

Community
  • 1
  • 1
David Hoelzer
  • 15,862
  • 4
  • 48
  • 67
  • I realize that I have to use recursion, but how do I keep track of values as I go? I don't understand how the link helps. Is there a way to initialize a list to the empty list and add a character after every recursive call? – Jon May 08 '15 at 01:50
  • @Jon, yes that's exactly a common way of doing it in Prolog. Starting your recursion with an empty list and each recursive call can add an item to the list. For example, if you pass in the list `L` as an argument, you can add `X` to the head just by referring to `[X|L]`. – lurker May 08 '15 at 01:55
  • @lurker, How would I create an empty array? I tried to make a predicate start([]). but that just reset the list to an empty array every time I passed it. – Jon May 08 '15 at 01:58
  • 1
    @Jon Prolog doesn't have arrays. It has lists. :) You need to carry an extra argument: `start([], Result)` or something like that. Since you haven't given a specific example in your posted problem description what you're doing, I'm not sure how to be more specific than that. You should Google search "99 prolog problems". A number of them deal with lists and it gives the answers. Then you will get the hang of basic list processing. – lurker May 08 '15 at 02:13
  • Yeah, I meant list. Still thinking in other languages I guess. But thank you, at least I know I'm heading in the right direction. – Jon May 08 '15 at 02:17
0

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
migfilg
  • 542
  • 2
  • 9
0

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)).

Paulo Moura
  • 18,373
  • 3
  • 23
  • 33