Learning Prolog: Lab #10

We are in double figures! Welcome to my solutions for the tenth and final lab session for this semester. This lab lets you in easy, and then hits you with a really nasty problem right at the end.

The first problem asked for a rule that returned the length of a list. I found this one easy:

listlength([], 0).
listlength([ _ | Tail ], Length) :-
    length(Tail, RecursiveLength),
    Length is RecursiveLength + 1.

?- listlength([ hurricane, typhoon, cyclone ], Length).
Length = 3.

I simply recurse over the list in question and add one to a counter variable on the way out. The next one is a bit harder, but still very easy - A rule that returns the nth element in a list.

nthelement(0, [ Head | _ ], Head).
nthelement(N, [ _ | Tail ], Result) :-
    N > 0,
    NRecurse is N - 1,
    nthelement(NRecurse, Tail, Result).

?- nthelement(2, [sequoia, baobab, redwood], Item).
Item = redwood .

My solution works very similary to my listlength/2 solution, but instead counts down from the number you give it until it reaches zero ,at which point it climbs back out of the recursion again and returns the item that it got up to.

The last problem was a really tough one. It demands flattened list containing all the elements in a given list of lists of arbitrary depth (exceptempty lists). It took me a while (and some help) in order to figure this one out:

squash([[]], []).
squash([], []).
squash([ [ HeadHead | HeadTail ] | Tail ], Result) :-
    squash([ HeadHead | HeadTail ], HeadResult),
    squash(Tail, TailResult),
    append(HeadResult, TailResult, Result).
squash([ Head | Tail ], Result) :-
    squash(Tail, TailResult),
    append([Head], TailResult, Result).

Cracking particular problem requires a new brain-breaking type of recursion, called Top-and-Tail recursion. It's specific to Prolog (as far as I know), and means that instead of just recursing over the tail of the list in order to iterate over it, you iterate over the head of the list as well.

Since Prolog lets us break arguments down to any depth we like, I break the incoming list down into its head and tail, and then I break the head down into its component head and tail in order to ensure that it is actually a list.

I then recurse over the head of the list ad the tail of the list separately, and concatenate the result of the two recursive calls at the end.

If the head isn't a list, then I only recurse over the tail, and append the head to the flattened tail on the way out.

I also declare that both an empty list and an empty lsit inside an empty list should return a single empty list. This allows us to avoid any rogue empty lists that might happen to be floating around from finding their way into the solution by mistake. Here's an example:

?- squash([[[a],b],[c],[d,[e],[]]], Result).
Result = [a, b, c, d, e] .

That concludes all the AI labs for semester 1, although I have another AI lab scheduled for the coming Monday. If it turns out that there's another lab, I'll post about it here. Otherwise, I'll resume this series in sesmeter 2.