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!

### Like this:

Like Loading...

*Related*

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.

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!

Thanks for this! I solved it exactly the same way but was struggling with the syntax for the subgoals. Seeing your solution cleared it up.

Hi Mike, glad it helped! :)

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