Week 3 Day 2 (continued) – Prolog finding the smallest element in a list

Finding the smallest in a list has a fairly similar solution to reversing a list. It’s a recursive rule with a join to get the answer. In this case, the join is not an append but a ‘smaller’ rule that i wrote especially to find the smaller of two numbers.

But let me not get too far ahead. The first thing i did was handle the case of a list with only one item.

smallest([Head|[]], Head).

That’s a fact. The smallest element in the list [9] is 9. This is also a termination case for the recursive rule.

So next i turned my attention to the smaller rule. I wrote it like this:

smaller(X, Y, What) :-
  (X < Y), What is X.

smaller(X, Y, What) :-
  (Y < X), What is Y.

In the meantime, Tom Crayford has shown me a beautifully elegant way to rewrite these rules:

smaller(X, Y, X) :-
  (X < Y).

smaller(X, Y, Y) :-
  (Y < X).

My brain b0rked a little when i saw that, but then i figured it out:

The smaller of X and Y is X if you can prove that X is less than Y.

I know, Tautology Club, right?!

I must also cater for “Which is the smaller of 3 and 3?” In this case, it doesn’t matter whether we respond with X or Y, they are the same anyway, so we come to this:

smaller(X, Y, X) :-
  (X =< Y).

smaller(X, Y, Y) :-
  (Y < X).

Finally, my rule to find the smallest. To find the smallest element of a list, you take the smaller of the first element or the smallest of the rest of the list.

smallest([Head|Tail], Answer) :-
  smallest(Tail, What),
  smaller(What, Head, Answer).

I pretended to be Prolog and ran this all by hand. It seemed to work. But back to everybody’s favourite Prolog error message: Prolog says no.

It turned out that i had written these facts and rules in the order i thought of them. I had a fact for smallest, two rules for smaller, and then a rule for smallest. And Pedantic Prolog doesn’t like that. I guess you have to put all the facts and rules together by name.

My final solution looks like this:

smaller(X, Y, X) :-
  (X =< Y).

smaller(X, Y, Y) :-
  (Y < X).

smallest([Head|[]], Head).

smallest([Head|Tail], Answer) :-
  smallest(Tail, What),
  smaller(What, Head, Answer).

I’m going to skip Day 2’s final exercise because i’ve seen Alberto’s solution and frankly it just scares me! If i don’t move on now i’ll never get to the Sudoku and i’ve been really looking forward to that!

Advertisements

6 comments on “Week 3 Day 2 (continued) – Prolog finding the smallest element in a list

  1. You can write [Head|[]] as [Head], so you can say: smallest([X], X). smaller/3 can be written shorter as smaller(X, Y, Z) :- Z is min(X, Y).

    • Oh, that’s good to know, thank you. I think the book might not have told us that, possibly so as not to confuse us.

  2. Just thought I’d share my solution to the sorted list.

    I modified smallest function thingy, to also return the list without the smallest element.

    smallest_and_rest_of_list([Value],Value,[]).
    smallest_and_rest_of_list([Head|Tail],Value,RestOfList) :- smallest_and_rest_of_list(Tail,Val,PrevList), Value is min(Val,Head), NewHead is max(Val,Head), append([NewHead],PrevList,RestOfList).

    Looks ugly but makes the sort a bit easier

    my_sort([Value],[Value]).
    my_sort(Input,List) :- smallest_and_rest_of_list(Input,Smallest,Rest), my_sort(Rest,Sorted), append([Smallest],Sorted,List).

    I would explain but I’m such a good coder that all my code reads like literature *cough* read: too lazy and not good at explaining *cough*

    I’ve enjoyed going through your solutions. Thanks for posting!

  3. Hi ….

    My predicate for the smallest in a list, seems clearest than your.
    In Portuguese ‘menor’ means something like that smallest
    %%% O menor

    menor(_,[]) :- write(‘ your list is empty …. ‘).
    menor(A,[A]).
    menor(A,[A,B]):- A =< B.
    menor(B,[A,B]):- B =< A.
    menor(X, [A , B | C] ) :- A < B, menor(X, [A|C]).
    menor(X, [A , B | C] ) :- B =< A, menor(X, [B|C]).

    Cheers

    claudio

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s