listprologdeclarativedcgprolog-dif

Prolog List Plateau


Just got introduced to prolog, trying to get through some simple exercises, but I've been getting kind of stuck on this one. I'm trying to write a program that outputs all the sublists of the input list, where each sublist has length > 1 and it cannot be extended to a larger sublist. It will also output the starting position in the list of the sublist. So a sample output would 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'm still pretty confused by the whole declarative thing, and having a lot of trouble switching out of imperative mode. I'm thinking 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 isn't working, from what I can tell for a couple reasons. I don't reset 'count', so its totaling up the values of all the sublists together maybe? Is there some way to work around for this? My base case might also not be what I want - I'm just not sure what it should be really? I'm probably missing other things too...any help is greatly appreciated! :) Thanks!


Solution

  • There are quite a lot of complicated answers here. Consider this one which doesn't use DCGs or many built-ins (perhaps simpler for a beginner):

    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(_, I-L-_, I, L) :-
        L > 1.
    
    plateau([X|Xs], I0-L0-_, I, L) :-
        NI is I0 + L0,
        plateau(Xs, NI-1-X, I, L).
    

    The first clause sets up the call which accumulates the (index)-(length)-(sublist element) tuple, as a term.

    The next clause increments the length if the next list element is the same (note the index isn't altered).

    The third clause is called only if the second clause failed when testing if the sublist element run was broken (because of the cut !), and returns a solution iff the length of the run was > 1.

    The last clause enables Prolog to backtrack and re-start the search from the last run.

    EDIT: gusbro's solution is actually very close to this one... +1.