CODEWITHSUNDEEP
prolog
URL87
URL87

Reputation: 11032

Prolog - sequence in list

We want to build a predicate that gets a list L and a number N and is true if N is the length of the longest sequence of list L. For example:

?- ls([1,2,2,4,4,4,2,3,2],3).
    true.

?- ls([1,2,3,2,3,2,1,7,8],3).
    false.

For this I built - 

head([X|S],X). % head of the list
ls([H|T],N) :- head(T,X),H=X, NN is N-1 , ls(T,NN) . % if the head equal to his following
ls(_,0) :- !. % get seq in length N
ls([H|T],N) :- head(T,X) , not(H=X) ,ls(T,N). % if the head doesn't equal to his following

The concept is simply - check if the head equal to his following , if so , continue with the tail and decrement the N .

I checked my code and it works well (ignore cases which N = 1) - 

 ls([1,2,2,4,4,4,2,3,2],3).
true ; 
false .

But the true answer isn't finite and there is more answer after that , how could I make it to return finite answer ?

Upvotes: 2

Views: 2132

Answers (3)

CapelliC
CapelliC

Reputation: 60034

Your code is checking if there is in list at least a sequence of elements of specified length. You need more arguments to keep the state of the search while visiting the list:

ls([E|Es], L) :- ls(E, 1, Es, L).

ls(X, N, [Y|Ys], L) :-
  (  X = Y
  -> M is N+1,
     ls(X, M, Ys, L)
  ;  ls(Y, 1, Ys, M),
     ( M > N -> L = M ; L = N )
  ).
ls(_, N, [], N).

Upvotes: 2

Daniel Lyons
Daniel Lyons

Reputation: 22803

Prolog-wise, you have a few problems. One is that your predicate only works when both arguments are instantiated, which is disappointing to Prolog. Another is your style—head/2 doesn't really add anything over [H|T]. I also think this algorithm is fundamentally flawed. I don't think you can be sure that no sequence of longer length exists in the tail of the list without retaining an unchanged copy of the guessed length. In other words, the second thing @Zakum points out, I don't think there will be a simple solution for it.

This is how I would have approached the problem. First a helper predicate for getting the maximum of two values:

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- Y > X.

Now most of the work sequence_length/2 does is delegated to a loop, except for the base case of the empty list:

sequence_length([], 0).
sequence_length([X|Xs], Length) :- 
    once(sequence_length_loop(X, Xs, 1, Length)).

The call to once/1 ensures we only get one answer. This will prevent the predicate from usefully generating lists with sequences while also making the predicate deterministic, which is something you desired. (It has the same effect as a nicely placed cut).

Loop's base case: copy the accumulator to the output parameter:

sequence_length_loop(_, [], Length, Length).

Inductive case #1: we have another copy of the same value. Increment the accumulator and recur.

sequence_length_loop(X, [X|Xs], Acc, Length) :- 
    succ(Acc, Acc1), 
    sequence_length_loop(X, Xs, Acc1, Length).

Inductive case #2: we have a different value. Calculate the sequence length of the remainder of the list; if it is larger than our accumulator, use that; otherwise, use the accumulator.

sequence_length_loop(X, [Y|Xs], Acc, Length) :- 
    X \= Y,
    sequence_length([Y|Xs], LengthRemaining),
    max(Acc, LengthRemaining, Length).

This is how I would approach this problem. I don't know if it will be useful for you or not, but I hope you can glean something from it.

Upvotes: 3

Zakum
Zakum

Reputation: 2297

How about adding a break to the last rule?

head([X|S],X). % head of the list
ls([H|T],N) :- head(T,X),H=X, NN is N-1 , ls(T,NN) .    % if the head equal to his following
ls(_,0) :- !.                                           % get seq in length N
ls([H|T],N) :- head(T,X) , not(H=X) ,ls(T,N),!.         % if the head doesn't equal to his following

Works for me, though I'm no Prolog expert.

//EDIT: btw. try 

14 ?- ls([1,2,2,4,4,4,2,3,2],2).
true ;
false.

Looks false to me, there is no check whether N is the longest sequence. Or did I get the requirements wrong?

Upvotes: 2

Related Questions