如何在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.

我是Prolog的新手,我遇到了一些来自OOP的困难。我需要递归地运行一些角色,但要记住我经历过的事情。在OOP中,我只想创建一个数组或arraylist来跟踪我使用过的任何内容。但是,我似乎无法在Prolog中找到类似的方法。我如何检查我已经使用过的东西。

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

5 个解决方案

#1

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

以下是基于@鲍里斯的回答;您还可以使用目标地图列表(dif(X),Seen)而不是\ + memberchk(X,Seen)来保持逻辑纯度:

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

#2

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

当列表为空时,谓词成功(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).

如果列表不为空(2):检查是否已经看到列表的第一个元素(3)如果不是(\ + X代表“当X失败时成功”),将元素添加到看到的元素列表中并检查列表的其余部分(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:

if you just want to see if there are duplicates in a list, you can sort and compare lengths;

如果你只想查看列表中是否有重复项,可以对长度进行排序和比较;

consider using an ordset instead of a list for the second argument;

考虑使用ordset代替第二个参数的列表;

figure out what "accumulators" are.

找出“累加器”是什么。

#3

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.

您可能会发现这很有用:Prolog迭代列表基本上,Prolog没有迭代,但它确实有递归。您需要通过列表递归来完成您要执行的操作。

#4

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

#5

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:

将每个找到的字符添加到列表中,然后使用此列表检查是否有两次字符将与找到的字符列表的大小成线性关系。这可能是也可能是不可接受的w.r.t.性能。你有多少个不同的角色?只有ASCII可打印字符?完整的Unicode?由于只有一些Prolog系统提供了数组,因此您获得比列表更好的性能的最佳选择是二叉搜索树,它将在平均情况下为您提供O(log(n))。但你可以做得更好。在标记问题swi-prolog时,您可以使用此系统读取黑树库(继承自YAP)。在最坏的情况下,这也应该为您提供O(log(n))。使用这个库(作为在其他答案中使用列表的替代方法),你可以写一些东西:

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

这是使用列表的一个有价值的(性能方面)替代方案吗?您没有提供足够的详细信息来回答这个问题。最好运行一些测试。另外值得注意的是,列表中的插入是O(1)(当你执行Head + List - > [Head | List]时),但是在红黑树中的插入是O(log(n))。

#1