CODEWITHSUNDEEP
prolog
Liam Neeson
Liam Neeson

Reputation: 21

Can anyone explain to me what this Prolog code is doing?

So I have a question I need to answer commenting on how this code is executed and what it is doing and I am not sure what is going on in it. I think it is something to do with if the values appear in the list? No idea however any help is appreciated!! I also need to explain what the output of this query is regarding the code below p([5,3,6,3,7],L,4,7).

p([],[],_).
p([H|T],[H|R],N,M) :-H >= N, H =< M, p(T,R,N,M).
p([H|T],R,N,M) :- H < N, p(T,R,N,M).
p([H|T],R,N,M) :- H > M, p(T,R,N,M).

Upvotes: 0

Views: 53

Answers (1)

TessellatingHeckler
TessellatingHeckler

Reputation: 29048

(Let's assume the first line has a typo and should have two _ in it rather than one).

Instead of trying to unpick the variables and follow them through, step back and look at the shape, and the general patterns; first note the pattern of how the predicates are all p/4 and start like this:

p([],
p([H|T],
p([H|T],
p([H|T],

It's common to put lists in the first position, as Prolog systems tend do more optimisation on the first position, and this is a common pattern for a recursive list walk down to the empty-list end of a list.

Then note that the last two lines have the same header and the same recursive call:

p([H|T],R,N,M) :-      , p(T,R,N,M).
p([H|T],R,N,M) :-      , p(T,R,N,M).

And the recursive call changes [H|T] into T, so yes, recursive list walk looks likely. Bit suspicious that they have the same call at the end in both cases. What's different about them, and why does it matter?

                  H < N,
                  H > M,

It is common to write if/else like this, as two separate rules, one rule for each case, e.g. a cutoff value, one for being above it and another for beign below it. This is not that because both rules describe the same behaviour; H is being compared with N in one rule and M in the other. H is outside either end of a boundary, do nothing?

What's the second line?

p([H|T],[H|R],N,M) :- H >= N, H =< M, p(T,R,N,M).

It has the same recursive call but it has a different header where H merges into the second parameter, and the conditions are H >= N, H =< M; that's H being inside the boundary.

So, it's a filter; in p([5,3,6,3,7],L,4,7) the list elemetns between N and M (inclusive) get merged into L, the rest are ignored. It's very similar to:

?- include(between(4, 7), [5,3,6,3,7], L).

Upvotes: 2

Related Questions