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!
