And so, to Haskell!

Wrapping up Clojure

I really enjoyed what i learned about Clojure last week. I notice an interesting thing: if i don’t do the exercises, i feel as if i don’t like the language. But when i actually try them out and solve a few problems for myself, i find i like it.

I like Clojure but i think that’s really because i like Lisp. For me, Clojure just seemed to add a bunch more keywords that i had to remember. Do i really need defprotocol and defrecord, just because they map to Java interfaces and types? I’d rather do without them. And the lack of support for automatic tail-optimised recursion disappointed me. Sure, you can do it explicitly … and that introduces another two Clojure keywords.

I want to get back to the day 3 exercises at some point, but Seven Languages in Seven Weeks is fast-paced and before i know it we’re into the last language!

And now, Haskell

I somehow feel that the whole book has been leading to this. We’ve seen functional elements in most of the languages, but now we get to a language with no excuses, no exceptions. It is uncompromisingly functional. And i love it.

I like strong typing, i like immutability, and i like the power of functions. Haskell is bringing them all together for me, as if it was my perfect dream language, created just for me! Well, i’m only just starting, so we’ll see if this perception continues :)

Just looking at the examples, and trying them out, i get an overall feeling of beauty in simplicity. Haskell is wonderful.

For example

Filtering a list to just the even numbers in the list. The book gives an example using recursion:

allEven :: [Integer] -> [Integer]
allEven [] = []
allEven (h:t) = if even h then h:allEven t else allEven t

The pattern match says that when you get to an empty list you return the empty list.

The tail-optimised recursion checks whether the head of the list is even, and if so includes it in the result, along with the even numbers of the rest of the list. Otherwise, it doesn’t.

We can also solve it with list comprehension. I first tried this:

allEven :: [Integer] -> [Integer]
allEven list = [if even x then x else 0 | x <- list]

I was putting the check into the expression and actually replacing odd numbers with zeros. Not a great solution. Then i remembered we can put a filter on the input side to ensure that only even numbers go in. Suddenly it becomes beautifully simple:

allEven :: [Integer] -> [Integer]
allEven list = [x | x <- list, even x]

Where Clojure felt cluttered with syntax, Haskell feels very minimal and concise.

Reversing a list

Well, this is too easy, so i expect they want me to do something more than just use the built in reverse keyword:

reverseList :: [Integer] -> [Integer]
reverseList list = reverse list

I think recursion is going to be the way to go with this. Split the head and tail and stick them back in the other order. Now then, what’s wrong with this?

reverseList :: [Integer] -> [Integer]
reverseList [] = []
reverseList (h:t) = reverseList(t):h

It gives a compile error:

Couldn't match expected type `Integer' with actual type `[Integer]'
In the return type of a call of `reverseList'
In the first argument of `(:)', namely `reverseList (t)'
In the expression: reverseList (t) : h

It must have something to do with type checking when constructing a list. I wondered whether it needed a few more guards:

reverseList :: [Integer] -> [Integer]
reverseList [] = []
reverseList [x] = [x]
reverseList [x,y] = [y,x]
reverseList (h:t) = reverseList(t):h

No. I think the problem is you can’t use this h:t style list construction with the way i’m imagining you can.

Whilst you can do this:

1:[2,3]

You cannot do this:

[2,3]:1

Basically, the head has to be an element, and the tail has to be a list.

However, we can use addition to join lists:

[2,3] ++ [1]

So the answer is:

reverseList :: [Integer] -> [Integer]
reverseList [] = []
reverseList (h:t) = reverseList(t) ++ [h]

Enough for now

This is taking a long time and it’s probably getting boring for my readers!

I will try to do a bit more on Haskell and publish it to my github: sermoa/7languages7weeks/week7-haskell

Week 6 Day 2 – Clojure macros and protocols

Clojure uses macros to delay execution. We are using this feature to define an unless function.

Here’s an example of an unless that does not work because it is defined with defn:

(defn unless [test body]
  (if (not test) body))

Whatever i give this function, whether the test evaluates to true or false, the body is also evaluated and placed on the stack ready to be returned. This is not what we want, so we use a macro instead.

(defmacro unless [test body]
  (list 'if (list 'not test) body))

We have to use a kind of ugly syntax, explicitly declaring a list and using the apostrophe to delay execution. Clojure uses macroexpand at the right time to evaluate the right bit of code.

We can add an else portion to the function like this:

(defmacro unless [test body other]
  (list 'if (list 'not test) body other))

Protocols

I don’t know enough about Java for this to be deeply meaningful, but i understand the principle of a java interface being something of a contract that a class has to meet.

Clojure, being a JVM language, also has a way of implementing interfaces. It calls them protocols.

I had a really hard time thinking of an example to use for the exercise. It simply said, “Write a type using defrecord that implements a protocol”. Not much to go on. But, looking ahead to day 3, i see we’re going to need bank accounts so i’m going to try that.

I’d like my protocol to look like this:

(defprotocol Account
  (total [c])
  (credit [amount])
  (debit [amount]))

An account has three functions: a total for reporting the amount in the account, and a credit and debit function for putting money in and out.

Now to implement it:

(defrecord BankAccount [opening-balance]
  Account
  (total [c] opening-balance)
  (credit [amount] (BankAccount. (+ opening-balance amount)))
  (debit [amount] (BankAccount. (- opening-balance amount))))

Notice that when i credit or debit a bank account i’m actually getting back a brand new one. Although Clojure doesn’t really enforce immutability, it’s easier to use it than not.

Now let me try to open a bank acccount with £100.

(def account (BankAccount. 100.00))
#'user/account
account
#:user.BankAccount{:opening-balance 100.0}

WOOHOO! That looks better than i expected!

Then i made a proper noob error:

(account total)
java.lang.ClassCastException: user.BankAccount cannot be cast to clojure.lang.IFn (NO_SOURCE_FILE:0)

Of course, reverse notation! It’s a list, so i have to call the function first:

(total account)
100.0

Brilliant. Shall we try withdrawing some money?

(debit account 20.0)
java.lang.IllegalArgumentException: No single method: debit of interface: user.Account found for function: debit of protocol: Account (NO_SOURCE_FILE:43)

I’ve got a feeling this is to do with the number of arguments. The first argument to the function is always the instance, the ‘self’. So the protocol needs to understand that:

(defprotocol Account
  (total [instance])
  (credit [instance amount])
  (debit [instance amount]))

The implementation in this case doesn’t care about the instance, so it just uses an underscore:

(defrecord BankAccount [opening-balance]
  Account
  (total [_] opening-balance)
  (credit [_ amount] (BankAccount. (+ opening-balance amount)))
  (debit [_ amount] (BankAccount. (- opening-balance amount))))

Now to try it out:

(debit account 20.0)
#:user.BankAccount{:opening-balance 80.0}

YAAAAYY!! And of course, i can call the total on that new bank account that was returned:

(total (debit account 20.0))
80.0

I can also take that bank account containing £80 and credit it with £60:

(total (credit (debit account 20.0) 60.0))
140.0

Jolly good show.

Week 6 Day 1 – Feeling my way in Clojure

So i am starting to learn a bit of Clojure. It’s not completely alien to me because i’ve done a little bit of SICP with Scheme, another variant of Lisp. The syntax seems quite logical to me, and i like its simplicity.

At the moment we seem to be running everything within the console rather than writing to a file. So i’ll just paste what i’m learning in here.

Lists, Maps, Sets and Vectors

This is quite a lot to take on board. Let me see if i can distill it.

Lists and vectors are ordered. Sets and maps are unordered but can be sorted with the sort and sort-map functions, respectively.

Use lists for code and vectors for data. Vectors are optimized for random access. Maps are key-value pairs. Sets and maps are magically also functions, which to me seems really bizarre but powerful!

Functions

We define data with def and a functions with defn. I didn’t know that you can add an optional string for documentation of a function. That’s nice. Parameters go as a vector, and then it’s the body of the function.

There is a cool trick with destructuring the parameters: if you’re passed more than you actually need, you can pull out just the bits that you want to work with. I see similarities from Scala and Erlang pattern matching.

First exercise

Implement a function called (big st n) that returns true if a string st is longer than n characters.

(defn big [st n] (> (count st) n))

defn defines a function, the name is ‘big’, there are two parameters and we check whether the length of the first is greater than the second.

Second exercise

Write a function called (collection-type col) that returns :list, :map, or :vector based on the type of collection col.

First i tried this just to see what would happen:

(defn collection-type [col] (type col))

Actually something quite interesting happens:

user=> (collection-type '(:r2d2 :c3po))
clojure.lang.PersistentList

user=> (collection-type [:hutt :wookie :ewok])
clojure.lang.PersistentVector

user=> (collection-type {:darth-vader "obi wan", :luke "yoda"})
clojure.lang.PersistentArrayMap

I thought about doing a grep for the last word starting with a capital letter, lowercasing it, prefixing it with a colon … that would have been neat but it would also require clojure-contrib (community created extensions) which i couldn’t find out how to include.

So i’m not going to do that.

Fortunately there are shortcut functions we can use:

(defn collection-type [col] (vector? col))

This will return true if the collection given is a vector. There are similar functions for list? and map? so we can use some kind of test to see what we get.

I wanted some kind of if function that could take multiple options followed by results. The Clojure answer to that is a cond function.

And here it is (updated to close all the parentheses on one line as suggested by Tom):

(defn collection-type [col]
  (cond
    (list? col) :list
    (vector? col) :vector
    (map? col) :map))

I can learn to love parentheses! :)

End of Erlang; start of Clojure

Although i didn’t do much Erlang, Alberto did! :) Looking at this blog post allows me to appreciate Erlang through Alberto’s eyes: Erlang Day Three

Seriously impressive concurrency and fault tolerance. It’s just a simple example, but it shows us something that cannot be killed no matter what you try to do to it. You can easily see how this scales up to huge fault-tolerant telecommunications systems.

Thank you to Alberto for leading the group discussion today, that was great.

Now over to Clojure

And so we start Week 6! Clojure is a version of Lisp that runs on the Java Virtual Machine. So we have lists (obviously!), functions, dynamic typing, immutable state … ahh, well, no. As we now know, for concurrency it is best to write functions without side effects. However, Clojure includes a few tricks to help us out with mutable variables, such as transactional memory and encapsulated access via agents. I’m a little disappointed actually, i was growing rather fond of immutability.

Installing Clojure

I think i probably installed more than was necessary. I’m on Mac OS X with homebrew. I suggest you simply try:

brew install leiningen

Leiningen is a simple build tool that makes it easier to work with Clojure.

Having done that you can start a new project like so:

lein new day1

It sets up an environment for you to use and a few .clj files to get you started (including one to help you write tests!)

Now in the day1 directory you can do:

lein repl

It downloads a couple more files and starts up Java with the Clojure libraries, putting you into a Clojure console.

If that doesn’t work for you, i also did:

brew install clojure
brew install repl

But i think leiningen was all i really needed.

7languages7weeks – what’s happened?!

Hello!

Ummm, so i’ve been a complete failure at week 5, the Erlang week.

I finished the Scala week and was really impressed by the concurrency and actor support, as well as the ability to parse XML as a top-level concept. I think i am actually a Scala convert: it’s one that i definitely want to look into more.

I have read the Erlang text but not done the exercises. I’ve been working away from home a lot recently, in Edinburgh. I wasn’t sleeping very well, and i found i’d become very lonely. This last week it was more important for me to spend time with new friends Will, Alistair, Kate, David, Adrian, Joe and Ryan. I’ve been juggling and slacklining, finding geocaches and going out for meals. I needed to do that for my own sanity, which turned out to be more important than studying Seven Languages in Seven Weeks. Thank you to everyone who has been a friend to me the last fortnight. Scottish people are nice! :D

Alberto has kindly agreed to lead tomorrow’s discussion. I’ll be there but i don’t feel able to direct the conversation because i didn’t do the Erlang exercises.

I am now back home for a fortnight and looking forward to getting back into studying for the last two weeks of Clojure and Haskell.

Week 4 Day 2 – Scala reveals its functional side

I’m a little behind this week, but i’m happy to be back into a bit more Scala. Today we learned about Scala’s functions, higher order functions (functions that take anonymous functions as parameters), currying functions (functions with multiple parameters that get transformed into other functions), and more about Lists, Maps and HashMaps.

On day 1 Scala reminded me strongly of Java. On day 2 it’s suddenly a lot more like Ruby. And then there are weird things that remind me of nothing i’ve ever seen before, such as “Everything inherits from ‘Any’, and ‘Nothing’ inherits from everything.” SRSLY, WUT?!

The foldLeft function

I find foldLeft very much like Ruby’s inject (or reduce). The book said this version would be harder to understand, but to me this looks just like Ruby. Here i am counting the number of letters in a list of words:

words.foldLeft(0) ((sum, word) => sum + word.length)

But Scala also has a weird version!

(0 /: words) {(sum, word) => sum + word.length }

I think /: is a very weird operator.

Replacing swear words

This was a hugely fun exercise! I chose Tim Minchin’s Fuck the Pope song which is the sweariest song i know! ;)

I used a Map for the swear words and their replacements. I found that a Map is unordered, so i converted it to a Sequence so that i could sort by length of swear word. (It helps to convert the longest words first, otherwise it would match partial words within longer words.)

The cleanVersion function went into a Censor trait that could be included into a RudeSong. It’s very much like a Ruby mixin, but i found that i needed a superclass Song to extend from, in order to mix in the Censor trait. I wish i could just do this:

class Song(val lyrics: String) with Censor

But that didn’t work. It had to be this:

class RudeSong(override val lyrics: String)
  extends Song(lyrics) with Censor

I found a way to read the song lyrics from a text file:

val lyrics = scala.io.Source.fromFile("lyrics.txt").mkString

You can find the full program at week4-scala/day2/curseWords.scala – please let me know if i can improve the style of the code at all, as i’m not at all familiar with Scala.

Here is a clean version of the last verse of Tim Minchin’s song!

So fornicate the mother lover, and fornicate you mother lover
If you’re still a mother loving papist.
If he covered for a single mother lover whos a kiddy-fornicator,
Fornicate the mother lover, he’s as evil as the rapist.
And if you look into your mother loving heart and tell me true
If this mother loving stupid freaking song offended you,
With its filthy freaking language and its freaking disrespect,
If it made you feel angry, go ahead and write a letter,
But if you find me more offensive than the freaking possibility
The pope protected priests when they were getting freaking fiddly
Then listen to me mother lover – this here is a fact,
You are just as morally misguided as that mother loving,
Power-hungry, self-aggrandized bigot in the stupid freaking hat.

And just because it’s a fun song, here’s the original!

Week 4 Day 1 – Scala time!

Now i come to another language that i know very little about. Here’s what i do know:

Scala is a sort of bridge between object oriented and functional paradigms. Much like C++ was a bridge between procedural and object oriented. These bridge languages allow two paradigms to coexist, providing a comfortable switch over for the programmer. In this stage of Seven Languages in Seven Weeks, we’re also getting a comfortable shift into the pure functional languages to come later.

Installing Scala

I know that Scala runs on the Java virtual machine, so i was expecting a hard time installing. Not so at all.

$ brew install scala

Homebrew downloaded it, probably added a symlink somewhere and that was it! Good to go!

Scala first impressions

No semicolons! woohoo!

This res1, res2 etc is interesting. i didn’t think on it too much until i got to assigning a variable:

scala> 5 != 2
res16: Boolean = true

scala> val a = 1
a: Int = 1

scala> 1 + 1
res17: Int = 2

scala> res17
res18: Int = 2

I noticed that we got ‘a’ instead of res17. Then i tried something else and there was res17. Then i figured out that res17 is a variable. I guess that’s useful to be able to look back and use a previous result.

There is a nice early hint at the way the object oriented and functional paradigms exist happily side-by-side: var is mutable, and val is immutable. Perfect!

I see that Scala takes a while to get started. I suppose it is compiling as it goes.

The book shows us how to define classes and instantiate objects. After our adventures into Io and Prolog, this feels a bit old-school. I’m looking forward to seeing Scala’s functional side.

My initial reaction is that i like Scala, and i certainly much prefer it to Java.

Exercise: tic-tac-toe

Or as i like to call it, zeros and crosses. What do tictacs and toes have to do with this game?!

Immediately on encountering this, i remember the Prolog sudoku solver and think, “Surely this problem would be better solved with Prolog?!” :)

Okay, so i have to take in a board and check whether somebody has won. I suppose i need an array of nine elements representing the squares on the board. In Scala, an array is called a List. Let’s start with the easiest case: an empty board and nobody has won.

class Tictactoe(val board: List[java.lang.String]) {
  def winner {
    println("Nobody won")
  }
}

val newGame = new Tictactoe(List("", "", "", "", "", "", "", "", ""))
newGame.winner

And to check that it runs:

$ scala tictactoe.scala
Nobody won

Okay, now we need to put a different message if somebody has won. So imagine the board

X | X | X
- - - - -
  | 0 |
- - - - -
  | 0 | 0

I am not known for my ascii art, by the way ;)

So a crude way to solve this is to check the first three elements, if they’re all the same, and they’re not empty, then that person won.

class Tictactoe(val board: List[java.lang.String]) {
  def winner {
    if(List(board(0), board(1), board(2)).toSet.size == 1
        && board(0) != "") {
      println(board(0) + " won!")
    } else {
      println("Nobody won")
    }
  }
}

val newGame = new Tictactoe(List("", "", "", "", "", "", "", "", ""))
newGame.winner

val xShouldWin = new Tictactoe(List("X", "X", "X", "", "0", "", "", "0", "0"))
xShouldWin.winner

I carried on like this for a little bit. I extracted a Triplet class for checking trios of square values within a board, to see if they were all the same.

I was pleased to find that, like Ruby and Io, you can return early from a method.

I’m not very proud of my code, but i’m not going to refactor too heavily tonight as i don’t yet know the Scala idioms. So here it is: week4-scala/day1/tictactoe.scala

Summary

It feels like Java but not. A good Java feel is its strong type checking. At some point i was writing a method that was to return a boolean and i’d done an if clause without an else. It caught that for me at compile time, to make sure i could guarantee a return value. That’s one of the things i like about Java.

But it feels very much easier to write than Java. I felt ready to get started straight away, with very little syntax cruft to hold me back. So i think i’m going to enjoy this Scala week!

Week 3 Day 3 – Solving a sudoku with Prolog

This is the thing i have been most looking forward to in Seven Languages in Seven Weeks! Prolog is exceptionally good at solving problems with well-defined constraints. A sudoku is perfect for Prolog.

You don’t have to write any any algorithm to tell Prolog how to solve a sudoku. You just have to give it the rules of the game:

  • A sudoku is a 9×9 grid.
  • It must only contain the numbers 1-9.
  • In each row, column and 3×3 square, every number must be different.

Amazingly enough, if you can explain to Prolog these contraints, it can solve the hardest sudoku in matter of milliseconds!

Starting small

We started with a 4×4 sudoku containing the numbers 1-4 because it’s easier to grasp. Just look how little code there is! sudoku/4×4.pl

I then moved to a 6×6 sudoku. It’s not a lot more code. The hardest thing is making sure you don’t make a typo. I got very good at selective vim find and replace in this exercise! sudoku/6×6.pl

I tried to write my own 6×6 sudoku puzzle for it to solve. I encountered something interesting: it’s not very easy to design a sudoku! I’d either get more than one possible solution:

| ?- sudoku([1,_,2,_,_,5,
             _,_,_,_,_,_,
             _,5,_,3,_,_,
             _,2,_,_,_,4,
             _,_,_,_,4,_,
             3,_,6,1,_,_], Solution).

Solution = [1,_#17(3:6),2,4,_#75(3:6),5,
            5,_#133(3:6),4,2,_#199(3:6),1,
            4,5,1,3,2,6,
            6,2,3,5,1,4,
            2,1,5,6,4,3,
            3,4,6,1,5,2]

Now i look at it again, it’s telling me, “I can either put a 3 or a 6 in these places”. Which is very cool. And not surprising that when i tried to use a 2 in one of those places i found i accidentally made an impossible puzzle:

| ?- sudoku([1,_,2,_,_,5,
             _,_,_,_,2,_,
             _,5,_,3,_,_,
             _,2,_,_,_,4,
             _,_,_,_,4,_,
             3,_,6,1,_,_], Solution).

no

Heheh. Good old “Prolog says no”! It’s really nice that Prolog can help you not only solve a sudoku, but design a valid one in the first place.

Well, in the end i came up with this. I supplied the numbers in pen, and Prolog worked out the answer that i’ve filled in with pencil.

Finally I got to the sudoku 9×9 solution: sudoku/9×9.pl

To test it, i took my sudoku puzzle book and fed it one of the “hard” puzzles. To my surprise, Prolog found two valid answers! In less than 1 millisecond!

End of the Prolog week

Prolog is very very cool for certain types of problems. It can be incredibly frustrating and unhelpful when you don’t phrase your requests just right, but when you see it crunch your data and answer complicated questions with ease, it’s very inspirational.

I am actually considering using Prolog in a project i’m working on at the moment where we need to do some analysis about similarity and relevance. If we can figure out the rules by which unrelated things may be similar to each other, Prolog may be just what we need to find the most relevant results!

In the end, just knowing a bit about some other languages means i am better placed to choose the most useful one in any given situation. That’s why i’m pleased i’m doing Seven Languages in Seven Weeks!

Week 3 Day 2 (continued) – Prolog finding the smallest element in a list

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!

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! :)