Search code examples
prolog

How to compare sizes of every consecutive element in list - Prolog

Basically, I have an assignment where i need to compare sizes of every pair of elements in a List. The tricky part is:

  • The second element has to be larger than the first one,
  • The third element has to be smaller than the second one,
  • The fourth element has to be larger than the third one,
  • And so on an so forth alternating until the end od the list.

If this all checks out, then it returns yes, otherwise returns no.

Any ideas?

I know how to compare 2 elements in a list, but i can't wrap my head around comparing each consecutive one. I'm guessing it's supposed to be a recursion where I compare the first element to the second one, then remove the Head and do the same thing until the end, while keeping some kind of flag that tells me if it should be a bigger or a smaller number than the head.

Problem is i'm really new to prolog and i have no idea how to even start writing this properly.

Solution

  • Like most recursive problems, there's one general, recursive case, and a few special cases that terminate the recursion.

    Let's start with the general case: lists of length 3 or more, [X,Y,Z|Rest] succeeds if X < Y > Z, in which case we discard the first 2 elements, X and Y, and recurse down on the remainder:

    alternating_values( [X,Y,Z|Ns] ) :- X < Y , Y > Z , alternating_values([Z|Ns]) .

    The special, non-recursive, terminating cases deal with lists of lengths < 3:

    The empty list ([]): this succeeds because there's nothing to compare:

    alternating_values( [] ) .

    Lists of length 1 ([X]): This likewise succeeds because there's nothing to which the single item can be compared, and if the original list was of length 3 or more, it was compared to item immediately preceding it in list in the previous iteration.

    alternating_values( [_] ) .

    Lists of length 2 ([X,Y]): This succeeds if X < Y.

    alternating_values( [X,Y] ) :- X < Y .

    Putting it all together, you get this, which you can fiddle with at SWI Prolog's Swish sandbox:

    alternating_values( []         ) .
alternating_values( [_]        ) .
alternating_values( [X,Y]      ) :- X < Y .
alternating_values( [X,Y,Z|Ns] ) :- X < Y , Y > Z , alternating_values([Z|Ns]) .

    Another approach might be to use a helper predicate that carries an additional bit of state. This eliminates the need to deals with lists of length 2, since we're only removing one element at a time:

    alternating_values( Xs ) :- alternating_values( Xs , lt ) .

alternating_values( []       , _  ) .
alternating_values( [_]      , _  ) .
alternating_values( [X,Y|Zs] , lt ) :- cmp(CC,X,Y,CC1), alternating_values([Y|Zs],CC1) .
alternating_values( [X,Y|Zs] , gt ) :- cmp(CC,X,Y,CC1), alternating_values([Y|Zs],CC1) .

cmp( lt , X , Y , gt ) :- X < Y .
cmp( gt , X , Y , lt ) :- X > Y .

    But I like the first approach better. It's simpler and more straightforward.