Plateau Prologue List

Question

I just got acquainted with the prologue, trying to get through some simple exercises, but I was still stuck with this. I am trying to write a program that displays all the sublists of the input list, where each sub-list has a length> 1, and it cannot be expanded to a larger subnet. It also displays the starting position in the list of subscriptions. So the sample will be

| ?- plateau([a,a,b,2,2,2,a+1,a+1,s(1,2)], I, Len). I = 1, Len = 2 ? ; I = 4, Len = 3 ? ; I = 7, Len = 2 ? ; no 

I am still rather confused by the whole declarative thing, and I have many problems with the transition from the imperative regime. I think I want my program to do something like

 program([H|T],I,L):- T = [H1|T1] %split the tail ([H] = [H1] -> Count is Count+1, program(T,I,Count) %if First element = second element, recurse with new values ; length(T,Spot), %get the spot where you are in the list, so we know where sublist starts program(T,Spot,L) %run again, from tail, since sublist didn't have another element? program([],I,L). %terminate when entire list has been run through? 

So this does not work, from what I can say for several reasons. I am not resetting 'count', so maybe it sums up the values ​​of all the subscriptions? Is there any way around this? My basic business may also not be what I want - I'm just not sure what it should really be? Perhaps I also miss other things ... any help is greatly appreciated! :) Thank you!

Answer 1

There are quite a few complex answers here. Think of this, which does not use DCG or many built-in modules (perhaps for beginners):

 plateau([X|Xs], I, L) :- plateau(Xs, 1-1-X, I, L). plateau([X1|Xs], I0-L0-X0, I, L) :- X0 == X1, !, NL0 is L0 + 1, plateau(Xs, I0-NL0-X0, I, L). plateau(_, IL-_, I, L) :- L > 1. plateau([X|Xs], I0-L0-_, I, L) :- NI is I0 + L0, plateau(Xs, NI-1-X, I, L). 

The first sentence sets up a call that accumulates the (index) - (length) - (sublist element) tuple as a term.

The following sentence increases length if the next element list is the same (note that the index does not change).

The third sentence is called only if the second sentence was not executed during testing, if a subnet element was launched (due to reduction ! ), And returns a solution if the path length > 1 .

The last sentence allows Prolog to back off and restart the search from the last run.

EDIT: The gusbro solution is actually very close to that ... +1.

Answer 2

Your program combines many different problems into one predicate. Try to separate them a little. In addition, I assume that you are looking for the maximum list of two or more elements containing identical elements.

Let's start by approximating what you want: Identifying Subscriptions. Do not worry that this is too wide, and we will clarify it later. For this purpose I will use DCG. The nonterminal seq//1 describes an arbitrary sequence.

 seq([]) --> []. seq([E|Es]) --> [E], seq(Es). 

This is extremely useful not a terminal!

  ? - phrase ((seq (Prefix), seq (Sublist), seq (Postfix)),
       [a, a, b, 2,2,2, a + 1, a + 1, s (1,2)]).
 Prefix = Sublist, Sublist = [] ,
 Postfix = [a, a, b, 2,2,2, a + 1, a + 1, s (1,2)];
 Prefix = [],
 Sublist = "a" ,
 Postfix = [a, b, 2,2,2, a + 1, a + 1, s (1,2)] ...

Both responses are not expected, we only need 2 or more sublists, so we need to limit this definition a bit. Say, by requiring that a Sublist must contain at least two elements. This is Sublist = [_,_|_] .

  ? - Sublist = [_, _ | _],
    phrase ((seq (Prefix), seq (Sublist), seq (Postfix)),
       [a, a, b, 2,2,2, a + 1, a + 1, s (1,2)]).
 Sublist = "aa",
 Prefix = [],
 Postfix = [b, 2,2,2, a + 1, a + 1, s (1,2)];
 Sublist = "aab" ,
 Prefix = [],
 Postfix = [2,2,2, a + 1, a + 1, s (1,2)] ...

The first answer shows the sublist we are looking for. But the second is still incorrect: all elements of the sublist must be equal. The easiest way is to use maplist/2 :

  ? - maplist (= (_), Es).
 Es = [];
 Es = [_G221];
 Es = [_G221, _G221];
 Es = [_G221, _G221, _G221] 

There are several places where we could indicate this requirement. I put it as soon as possible:

  ? - Sublist = [_, _ | _],
         phrase ((seq (Prefix),
                  seq (Sublist), {maplist (= (_), Sublist)},
                  seq (Postfix)),
            [a, a, b, 2,2,2, a + 1, a + 1, s (1,2)]).
 Sublist = "aa",
 Prefix = [],
 Postfix = [b, 2,2,2, a + 1, a + 1, s (1,2)];
 Sublist = [2.2] ,
 Prefix = "aab",
 Postfix = [2, a + 1, a + 1, s (1,2)];
 Sublist = [2,2,2],
 Prefix = "aab",
 Postfix = [a + 1, a + 1, s (1,2)];
 Sublist = [2.2] ,
 Prefix = [a, a, b, 2],
 Postfix = [a + 1, a + 1, s (1,2)];
 Sublist = [a + 1, a + 1],
 Prefix = [a, a, b, 2,2,2],
 Postfix = [s (1,2)];
 false

So now all sublists contain the same elements. Alas, we get both [2,2] and [2,2,2] as a sublist. We need only the maximum sublist. So how can we describe what a maximum subselection is?

One way is to look in front of our sublist: there should not be one and the same element of our sublist. Thus, either there is no (epsilon) in front, or a sequence that ends with an element other than ours.

 difel(_E,[]). difel(E, Es) :- dif(E,F), phrase((seq(_), [F]), Es). 

  ? - Sublist = [_, _ | _],
    phrase ((seq (Prefix), {difel (E, Prefix)},
             seq (Sublist), {maplist (= (E), Sublist)},
             seq (Postfix)),
       [a, a, b, 2,2,2, a + 1, a + 1, s (1,2)]).
 Sublist = "aa",
 Prefix = [],
 E = a
 Postfix = [b, 2,2,2, a + 1, a + 1, s (1,2)];
 Sublist = [2.2],
 Prefix = "aab",
 E = 2,
 Postfix = [2, a + 1, a + 1, s (1,2)];
 Sublist = [2,2,2],
 Prefix = "aab",
 E = 2,
 Postfix = [a + 1, a + 1, s (1,2)];
 Sublist = [a + 1, a + 1],
 Prefix = [a, a, b, 2,2,2],
 E = a + 1,
 Postfix = [s (1,2)];
 false 

One wrong answer is less. In the end, still one is hiding.

  ? - Sublist = [_, _ | _],
    phrase ((seq (Prefix), {difel (E, Prefix)},
             seq (Sublist), {maplist (= (E), Sublist)},
             ([] | [F], {dif (E, F)}, seq (_))),
       [a, a, b, 2,2,2, a + 1, a + 1, s (1,2)]).
 Sublist = "aa",
 Prefix = [],
 E = a
 F = b;
 Sublist = [2,2,2],
 Prefix = "aab",
 E = 2,
 F = a + 1;
 Sublist = [a + 1, a + 1],
 Prefix = [a, a, b, 2,2,2],
 E = a + 1,
 F = s (1,2);
 false

This is not exactly what you wanted: you just need lengths. To do this, add length([_|Prefix],I), length(Sublist,Len) .

So here is the final definition:

  plateau (Xs, I, Len): -
    Sublist = [_, _ | _],
    phrase ((seq (Prefix), {difel (E, Prefix)},
             seq (Sublist), {maplist (= (E), Sublist)},
             ([] | [F], {dif (E, F)}, seq (_))),
       Xs)
    length ([_ | Prefix], I),
    length (Sublist, Len).

Answer 3

You can do something like this:

 plateau([Item|Tail], I, Len):- plateau(Tail, 1, Item, 1, I, Len). plateau(List, From, NItem, Len, From, Len):- (List=[Item|_] -> (Item\=NItem;var(Item)); List = []), Len > 1. plateau([Item|Tail], IFrom, Item, ILen, From, Len):- MLen is ILen + 1, plateau(Tail, IFrom, Item, MLen, From, Len). plateau([Item|Tail], IFrom, OItem, ILen, From, Len):- OItem \= Item, NFrom is IFrom + ILen, plateau(Tail, NFrom, Item, 1, From, Len). 

The first paragraph of plateau 6 refers to the termination of the subscription. The fact is that the item is different from the one you are looking for, or you have reached the end of the list. In this case, we will act only if the current length is greater than one.

The second sentence concerns the recursion stage for the case when we are still matching an element in the list. It simply adds one to the counter of the current sublist and performs the recursion.

The last sentence refers to the case of a new (other) element found in the list, and simply resets the counters and performs a recursion.

Answer 4

I tried using the built-in nth1 / 3, but had more problems to get it working ... anyway, here's a different implementation:

 plateau(L, I, Len) :- plateau(L, 1, I, Len). plateau(L, P, I, Len) :- nth1(P, L, E), skipseq(P, L, E, J), ( J > P, Len is J - P + 1, I is P ; Q is J + 1, plateau(L, Q, I, Len) ). % get the index J of last element E (after I) skipseq(I, L, E, J) :- T is I + 1, nth1(T, L, E), !, skipseq(T, L, E, J). skipseq(I, _, _, I). 

Test:

 [debug] ?- plateau([a,x,x,x,u,u,h,w],I,N). I = 2, N = 3 ; I = 5, N = 2 ; false. 

Answer 5

It is simple and simple. We count from 1; plateau - the maximum subsequence of equal elements of at least 2 lengths; we go through the list. Just write:

 plateau(L,I,N):- plateau(L,1,I,N). % count from 1 plateau([A,A|B],I1,I,N):- !, more_elts(A,B,2,K,C), % two equals, or more (I is I1, N is K ; plateau(C,I1+K,I,N)). plateau([_|B],I1,I,N):- plateau(B,I1+1,I,N). % move along the list more_elts(A,[A|B],I,K,C):- !, more_elts(A,B,I+1,K,C). more_elts(_,B,I,I,B). 

update:. All elements of the input list are nonvar/1 . The presence of non-specific variables as elements of an input data list makes the concept of “sublist” complex and uncertain. For example, what are the sublists of [a,X,b,b] ? Can [a,a] and [b,b,b] be subscriptions of the same input list? _{(it reminds me of the observed spin values, superposition of states, etc. somehow ... When the direction of spin observation is chosen, it can no longer be changed ... see all talk about “measurement” and quantum mechanics in sokuza -kanren.scm (found that link here )) sub>}