在序言中的特定元素之前和之后拆分列表(不使用"split"谓词?) [英] Splitting a list before and after a particular element in prolog (without using "split" predicate?)

问题描述

我正在尝试将列表拆分为特定元素(特别是单词"stop")之前的项目以及该元素之后的项目.我知道您可以使用split来执行此操作，但是我是prolog的新手，所以我正尝试在不使用这些功能的情况下操纵事物，所以我真的很想知道这是否可行吗? (也许还有一些指向正确方向的指针)

I'm trying to split a list into the items before a specific element (specifically the word "stop") as well as the items after this element. I know you can use split to do this, but I'm new to prolog and so I'm trying to manipulate things without using these functions currently, and so I'd really like to know if this is possible? (and maybe some pointers in the right direction)

即与列表；

L = [tea,coffee,sugar,cake,stop,meat,fish,eggs,flour]

理想情况下，我希望在停止"时拆分列表，让我离开，

I'd ideally want to split the list at 'stop' leaving me with,

L2 = [tea, coffee, sugar, cake] // and
L3 = [meat, fish, eggs, flour]

推荐答案

使用 seq//1 :

list_splitonstop(Xs, As, Bs) :-
   phrase( ( seq(As), [stop], seq(Bs) ), Xs).

此版本符合您的预期:

?- L = [tea,coffee,sugar,cake,stop,meat,fish,eggs,flour],
       list_splitonstop(L, L1, L2).
   L = [tea, coffee, sugar, cake, stop, meat, fish, eggs, flour],
   L1 = [tea, coffee, sugar, cake],
   L2 = [meat, fish, eggs, flour]
;  false.

但是，这真的是最好的解决方案吗?最后的; false可能表明不是.但是我们不能肯定地说.我们将不得不找出另一种情况，该解决方案无法按预期工作.在其他编程语言中，您也面临着类似的问题，因为人们不得不非常依赖程序员的想象力才能发现边界情况之类的东西.

But, is it really the best solution? This ; false at the end may be an indication that it is not. But we cannot say this for sure. We would have to figure out another case where this solution does not work as expected. You are faced with similar problems also in other programming languages were one has to rely a lot on the imagination of the programmer to find out border cases and the like.

幸运的是，我们在这里使用Prolog，它可以帮助我们了解我们实际定义的内容.

Fortunately, we are here using Prolog which helps us to understand what we are actually defining.

一个非常简单的开始是询问最普遍的查询.就是这样:

A very simple first start is to ask the most general query. Just like that:

| ?- list_splitonstop(L, L1, L2).
   L = [stop], L1 = [], L2 = []
;  L = [stop,_A], L1 = [], L2 = [_A]
;  L = [stop,_A,_B], L1 = [], L2 = [_A,_B]
;  L = [stop,_A,_B,_C], L1 = [], L2 = [_A,_B,_C]
...

看看每个答案！让我们以第三个为例. L = [stop,_A,_B]表示此答案包括具有三个元素的 all 列表，第一个元素为stop.因此，我们在这里看到一个无限解决方案，这些解决方案都用几个字符进行了紧凑的描述！甚至bzip2 -99都不能做到这一点！

Look at each answer! Let's take the third as an example. L = [stop,_A,_B] means that this answer includes all lists with three elements where the first is stop. So we are looking here at an infinity of solutions that have been all compactly described with a couple of characters! Not even bzip2 -99 can do that!

这些是唯一包含三个元素的列表吗?我们不能仅凭单个查询就这么说，因为Prolog可能以不公平的方式枚举答案.想象一下，您要求某人告诉您所有自然数，但是该人以0、2、4，...开始.显然，枚举对奇数非常不公平.同样，某些答案可能会丢失...

Are these the only lists with three elements? We cannot say this from this single query alone, for Prolog might enumerate answers in an unfair manner. Imagine you ask someone to tell you all the natural numbers, but that person starts 0, 2, 4, ... Evidently, that enumeration is very unfair to the odd numbers. Similarly some answers might be missing ...

在Prolog中，我们可以坚持只查看长度为3的列表:

In Prolog we can insist on looking at lists of length 3 only:

| ?- L = [_,_,_], list_splitonstop(L, L1, L2).
   L = [stop,_A,_B], L1 = [], L2 = [_A,_B]
;  L = [_A,stop,_B], L1 = [_A], L2 = [_B]
;  L = [_A,_B,stop], L1 = [_A,_B], L2 = []
;  false.

因此，我们可以在单个查询中询问长度为3的所有相关情况.请注意，这些_A和_B变量代表任何术语！请花一点时间，欣赏一下您所查看的内容:所有情况都是长度为3的列表.没有其他情况可以考虑了！

So we can ask for all relevant cases of length 3 in a single query. Note that these _A and _B variables represent any term! Please take a moment and appreciate what you are looking at: All cases for lists of length 3. There are no other cases to consider!

当您查看此类答案时，可能会出现一些问题.像:这三个答案是重叠的，还是真的不相交? Prolog知道答案.只需重复实际目标并计算得出的答案即可:

When you look at such answers some questions may arise. Like: Do these three answers overlap, or are they truly disjoint? Prolog knows the answer. Simply repeat the actual goal and count the resulting answers:

| ?- L = [_,_,_], list_splitonstop(L, L1, L2), list_splitonstop(L, L1, L2).
(answers same as above)

所以我们得到完全相同的答案.没有固有的冗余.

So we get exactly the same answers. There is no inherent redundancy.

另一个问题可能是:L是否总是精确地存在一个可能的拆分? (换句话说:是否存在功能上的依赖关系?)

Another question might be: Does L has always precisely one possible split? (In other words: Does there exist a functional dependency?)

我们可以通过询问具有不同L1和L2的L:

We can get to this by asking for L that have a different L1 and L2:

| ?- L = [_,_,_], dif(L1-L2,L1x-L2x),
     list_splitonstop(L, L1, L2), list_splitonstop(L, L1x, L2x).
   L = [stop,stop,_A], L1 = [], L2 = [stop,_A], L1x = [stop], L2x = [_A]
;  L = [stop,_A,stop], L1 = [], L2 = [_A,stop], L1x = [stop,_A], L2x = []
;  L = [stop,stop,_A], L1 = [stop], L2 = [_A], L1x = [], L2x = [stop,_A]
;  L = [_A,stop,stop], L1 = [_A], L2 = [stop], L1x = [_A,stop], L2x = []
;  L = [stop,_A,stop], L1 = [stop,_A], L2 = [], L1x = [], L2x = [_A,stop]
;  L = [_A,stop,stop], L1 = [_A,stop], L2 = [], L1x = [_A], L2x = [stop]
;  false.

所以，我现在想问你:你想要上述情况吗? stop是否多次出现?显然，您没有指定此项，我们需要您提供更多信息. Prolog至少有助于识别此类情况.

So, I may ask you now: Do you want above cases? If there are several occurrences of stop? Clearly, you did not specify this and we need some more information from you. Prolog was at least helpful to identify such cases.

在上述情况下，我们观察到没有多余的答案.但是当它们出现时它们如何出现?这是一个示例:member/2是内置的，可以生成(有时)多余的答案，而 memberd/2 不会.有这种冗余.实际的问题是:

In the case above we observed that there are no redundant answers. But how do they show up when they show up? Here is such an example: member/2 which is built-in and produces (sometimes) redundant answers and memberd/2 which does not have this redundancy. The actual question is:

以e作为元素/成员的二元素列表看起来如何?

How does a two-element list look like that has e as an element/member?

?- Xs = [_,_], member(e, Xs).
   Xs = [e, _A]
;  Xs = [_A, e].

?- Xs = [_,_], member(e, Xs), member(e, Xs).
   Xs = [e, _A]
;  Xs = [e, e]                %  <--- redundant
;  Xs = [e, e]                %  <--- redundant
;  Xs = [_A, e].

?- Xs = [_,_], memberd(e, Xs).
   Xs = [e, _A]
;  Xs = [_A, e], dif(_A, e)
;  false.

?- Xs = [_,_], memberd(e, Xs), memberd(e, Xs).
   Xs = [e, _A]
;  Xs = [_A, e], dif(_A, e)
;  false.

如果您只想查看允许重复的答案，则可以代替:

If you are only interested in seeing those answers that permit redundancies, you can say in stead:

?- Xs = [_,_], member(e, Xs), \+ \+ call_nth(member(e, Xs), 2).
   Xs = [e, _A]
;  Xs = [_A, e].

换句话说，member/2的所有所有答案都允许这种冗余.请注意，member/2并不总是易于冗余.特别是，如果列表包含不同(不可统一)的元素，则根本没有冗余.这是一个经常使用的案例.

In other words, all answers of member/2 permit such redundancies. Note that member/2 is not always prone to redundancy. In particular, if the list contains different (nonunifiable) elements, there are no redundancies at all. And this is a frequent use case.

?- Xs = [a,b], member(X, Xs), \+ \+call_nth(member(X, Xs),2).
false.

实际上，在这种情况下，即查询X时，member/2可能比memberd/2更有效.

In fact, in this very case, that is when querying for X, member/2 is probably more efficient than memberd/2.

这篇关于在序言中的特定元素之前和之后拆分列表(不使用"split"谓词?)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！