Prolog IntList definition

Question

hill(+IntList) succeeds if IntList consists of monotonically increasing >integers followed by monotonically decreasing integers. For example, >[1,2,5,8,11,6,3,-1] is a hill, but [1,2,5,8,11,6,9,3,-1] and [1,2,3,4,5,6] are >not hills. You may assume that IntList contains only integers.

This is what I have done so far:

hill(List) :-
    increasing(List), decreasing(List).

increasing([H|Tail]) :-
    sm(H,Tail),
    increasing(Tail).
increasing([]).


decreasing([H|Tail]) :-
    gr(H,Tail),
    decreasing(Tail).

decreasing([]).

hill([]).

gr(X,[H|Tail]) :- X>H.
gr(X,[]).

sm(X,[H|Tail]) :- X<H.  
sm(X,[]).  

But this doesn't work. The logic is: A list of numbers is hill IF it is increasing and then decreasing. How do I say that? This code does increasing and decreasing, but no list can be both increasing and decreasing.

Any ideas?

Answer 1

I don't want to give a complete, working solution to a homework problem, but I'll describe in words how I would proceed from the code you've got right now. Right now your increasing and decreasing predicates test the entire list. By your definition, though, a hill is neither entirely increasing nor entirely decreasing. I would modify these predicates to have two arguments instead of one. The additional argument would be bound to the tail of the list which is not does not satisfy the increasing/decreasing criteria. Then, I'd modify hill slightly to use the new argument of increasing to test decreasingness not of the entire list, but of the portion after the initial increasing subsequence. Finally, I would use the new argument of decreasing to verify that there are no non-decreasing elements after the decreasing subsequence.

If you need better hints, or if I seem to be talking nonsense (quite possible as I'm not that good with Prolog), just let me know and I'll try to clarify more.

Edit based on OP's comments: Alright, let's try something else. L is a hill if and only if L is a list of at least two monotone increasing elements ending with some element M, followed by a list of at least one monotone decreasing element starting with some element N, where N < M. Can you translate that description to Prolog clauses?

Edit take two (SPOILER WARNING):

---

In your revised code, drop these three predicates: increasing([])., hill([])., and hill(List) :- decreasing(List).. This will almost give you a solution, but it will still fail, e.g. on [3, 2, 1]. Fixing this should be fairly easy, though.

Answer 2

Use clpfd!

:- use_module(library(clpfd)).

We don't need to worry about getting recursion right if we use append/3 and chain/2 like this:

hill(Zs) :-
   Ascending0 =   [_|_],
   Descending = [M,_|_],
   append(Ascending0,Descending,Zs),
   append(Ascending0,[M],Ascending),
   chain(Ascending ,#<),
   chain(Descending,#>).

Let's run the queries the OP gave!

?- hill([1,2,5,8,11,6,3,-1]).
  true                               % as expected
; false.

?- hill([1,2,5,8,11,6,9,3,-1]).
false.                               % as expected

?- hill([1,2,3,4,5,6]).
false.                               % as expected 

Answer 3

hill(L1) :- concatenate(L2,L3,L1), inc(L2), dec(L3).
dec([X|[Y|[]]]) :- X > Y.
dec([X|[Y|L]]) :- X > Y, dec([Y|L]).
inc([X|[Y|[]]]) :- Y > X.
inc([X|[Y|L]]) :- Y > X, inc([Y|L]).
concatenate([],L2,L2).
concatenate([X|L1],L2,[X|L3]) :- concatenate(L1,L2,L3).

This works :)