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 3d printing account algorithms android announcement architecture archives arduino artificial intelligence artix assembly async audio automation backups bash batch blender blog bookmarklet booting bug hunting c sharp c++ challenge chrome os cluster code codepen coding conundrums coding conundrums evolved command line compilers compiling compression containerisation css dailyprogrammer data analysis debugging demystification distributed computing dns docker documentation downtime electronics email embedded systems encryption es6 features ethics event experiment external first impressions freeside future game github github gist gitlab graphics hardware hardware meetup holiday holidays html html5 html5 canvas infrastructure interfaces internet interoperability io.js jabber jam javascript js bin labs learning library linux lora low level lua maintenance manjaro minetest network networking nibriboard node.js open source operating systems optimisation own your code pepperminty wiki performance phd photos php pixelbot portable privacy problem solving programming problems project projects prolog protocol protocols pseudo 3d python reddit redis reference releases rendering resource review rust searching secrets security series list server software sorting source code control statistics storage svg systemquery talks technical terminal textures thoughts three thing game three.js tool tutorial tutorials twitter ubuntu university update updates upgrade version control virtual reality virtualisation visual web website windows windows 10 worldeditadditions xmpp xslt


Art by Mythdael