Week 3 Day 2 – Solving the Prolog reverse list

Well, i’m finding this prolog exercise quite a challenge. I thought i’d walk through my thought process as i go.

First of all i tried something completely useless, i don’t even remember what, but i was very surprised when it seemed to work straight away! I had called the rule ‘reverse’ and i think there must already be a ‘reverse’ rule built in!

So then i tried this simple fact:

rev([], []).

And yay! It works! It successfully reverses an empty list!

| ?- rev([], What).

What = []

Now, a list with one item needs no reversing. So next i did this:

rev([Head|[]], [Head]).

We know that the list has one item because when we split it into head|tail the tail is empty.

| ?- rev([1], What).

What = [1]

Hooray! Next i tried this, trying to reverse two items:

rev([Head|[Head2|[]]], [Head2|Head]).

Trying it out:

| ?- rev([1,2], What).

What = [2|1]

Oooh, close! I just don’t need the line between them. I guess a comma should work.

rev([Head|[Head2|[]]], [Head2,Head]).

Moment of truth:

| ?- rev([1,2], What).

What = [2,1]

Okay! Shall we go one step further?

rev([Head|[Head2|[Head3|[]]]], [Head3,Head2,Head]).

Here goes:

| ?- rev([1,2,3], What).

What = [3,2,1]

Right, now can we generalize this for any size list?

First attempt:

rev([Head|Tail], [What|Head]) :-
  rev(Tail, What).

Try it out:

| ?- rev([1,2,3], What).

What = [[[[]|3]|2]|1]

Oooh! Well the numbers came out in the right order! We just have way too many lists going on there! Let’s try this:

rev([Head|Tail], What) :-
  rev(Tail, What).

Hmm, no, this is no good. It can’t store the result as it goes along:

| ?- rev([1,2,3], What).

What = []

Let me think logically. What i really want to do is this: If the list has more than two items, put the first one to the back and run the reverse with all but the first. Sort of like this:

rev([Head|Tail], append(rev(Tail, []), Head)).

But you can’t do that. That’s trying to be a fact, but i need it to be a rule.

I ran it through by hand, trying to extract the rules. Here’s what i came up with:

rev([Head|Tail], Answer) :-
  rev(Tail, What),
  append(What, Head, Answer).

But here’s the problem i had:

| ?- rev([1,2,3], What).

no

It’s this all-or-nothing thing about Prolog. If it can’t find a solution it just says no. There is no hint as to where i might have gone wrong.

This got me frustrated for a long time, but in the end i discovered the problem was with the Head parameter. Once you’ve split an array into Head and Tail, the Head is a single element, and append only works with arrays. So here is the final solution, both the facts and the rule.

rev([], []).
rev([Head|[]], [Head]).
rev([Head|Tail], Answer) :-
  rev(Tail, What),
  append(What, [Head], Answer).

And, what do you know, it works!

| ?- rev([], What).

What = []

| ?- rev([1], What).

What = [1]

| ?- rev([1,2], What).

What = [2,1]

| ?- rev([1,2,3,4,5], What).

What = [5,4,3,2,1]

What did i learn from this?

I learned that Prolog is very pedantic! It doesn’t give any clues if you don’t get your syntax right. It’s just “I tried to do what you asked, and it didn’t work!”

But i also learned a technique for solving these recursive problems. It’s called: “Write down the rule as you’d like to use it, put circles around the parts that need to be extracted, put them on the line below and replace with a variable”. It sort of makes sense to me but i don’t think i’d like to try and teach it to anyone else!

Whew, well the reverse list took me 3 days! Now i can get on with the next exercise! :)