Learning Prolog: Lab #10

The new learning prolog banner!

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.

Tag Cloud

3d account algorithms announcement archives arduino artificial intelligence assembly async audio bash batch blog bookmarklet booting c sharp c++ challenge chrome os code codepen coding conundrums coding conundrums evolved command line compiling css dailyprogrammer debugging demystification distributed computing downtime embedded systems encryption es6 features event experiment external first impressions future game github github gist graphics hardware hardware meetup holiday html html5 html5 canvas interfaces internet io.js jabber javascript js bin labs learning library linux low level lua maintenance network networking node.js operating systems performance photos php pixelbot portable privacy programming problems project projects prolog protocol protocols pseudo 3d python reddit reference release releases resource review rust secrets security series list server servers software sorting source code control statistics svg technical terminal textures three thing game three.js tool tutorial tutorials twitter ubuntu university update updates upgrade version control visual web website windows windows 10 xmpp


Art by Mythdael