# Prolog Katas

Prolog is one of my favourite programming languages. Having never used it commercially I often jump back into it and try my hand at a few problems. It is the Programming Language That Changed My Life, as it were.

It’s a beautiful language, and I can almost guarantee that if you’ve not tried it before then you’ll be surprised.

In this blog, I’m going to tackle the first 8 of the Ninety-nine prolog problems, which is a website I used back when I was learning Prolog for a University assignment. If it’s any good, maybe I’ll tackle the next lot in a future blog.

## 1. Find the last element of a list

``````Example:
?- my_last(X,[a,b,c,d]).
X = d``````

So given a list, I must find the last element and output that element as X.

``````my_last(X, [_|Rest]):-
my_last(X, Rest).
my_last(X, [X]).    ``````

To Prolog, is to think recursively.

So when we execute the program by calling `my_last(X, [1,2,3,4])` it’ll hit the predicate (line 1) which is recursively calling itself (line 2) removing the first element from the list each time. Eventually, when there’s only one element left in the list it hits our base case `my_last(X, [X])`. Notice that the first element of the list is represented by a `_` – that’s the goto when you don’t want anything to do with the element, like us, we’re just removing it.

## 2. Find the last but one element of a list

``````Example:
second_last(X, [1,2,3,4])
X = 3``````

This one is pretty much the same as the first, the only thing that changes is the base case:

``````second_last(X, [_|Rest]):-
second_last(X, Rest).
second_last(X, [X,_]).    ``````

So this is saying when there’s only two elements in the list left `[X,_]` give me X – which is the second from last element.

## 3. Find the K’th element of a list

``````The first element in the list is number 1.
Example:
?- element_at(X,[a,b,c,d,e],3).
X = c``````

This one is going to require us decrementing from K to 1, in Prolog that looks like: `K1 is K - 1`.

``````element_at(X, [_|Rest], K):-
K1 is K - 1,
element_at(X, Rest, K1).

element_at(X, [X|_], 1).``````

So entering `element_at(X, [1,2,3,4], 3)` as the query returns 3 as the result.

## 4. Find the number of elements

This one I solved a little differently to the website.

``````num_elements(X, List):-
num_elements(X, List, 0).

num_elements(X, [_|Tail], N):-
N1 is N + 1,
num_elements(X, Tail, N1).

num_elements(N, [], N).
``````

So with a query like: `num_elements(X, [1,2,3,4,5,6])` it would return X = 6. This is how they solved it:

``````my_length([],0).
my_length([_|L],N) :-
my_length(L,N1),
N is N1 + 1.``````

I thought I was being clever by having the user query with just two parameters: the list and the output (X) and then calling a subsequent predicate that has the output as well as the count. It’s actually an unnecessary step.

## 5. Reverse a list

This one was a little bit more difficult. I had to create a new list for the output and systematically plug in each element to the front of that list:

``````reverse_me([],X,X).

And then querying this with `reverse_me([1,2,3,4,5,6], X, [])` would return `<strong>X</strong> = [6, 5, 4, 3, 2, 1]`. I also found out that `reverse([1,2,3,4,5,6], X)` must be a built-in predicate, as I managed to get the query to run without writing the predicate.

## 6. Find out whether a list is a palindrome

My first thought for this problem is that a palindrome is just a string that is the same when reversed, so I can leverage my previous solution.

``````is_palindrome(List):-
reverse_me(List, List, []).``````

So calling `is_palindrome([1,2,3,2,1])` will return true and `is_palindrome([1,2,3,2,1,4])` will return false.

## 7. Flatten a nested list structure

``````Example:
?- my_flatten([a, [b, [c, d], e]], X).
X = [a, b, c, d, e]``````

After reading the documentation, there’s a built-in predicate for for flatten. So `flatten([a, [b, [c, d], e]], X).` gives us `<strong>X</strong> = [a, b, c, d, e]`.

Let’s try do this ourselves. So an empty list is already flattened by nature. If we want to flatten a non-empty list we have to flatten both the head and the tail and then concatenate those results together.

``````my_flatten([],[]).

my_flatten(Tail, FlatTail),

my_flatten(X, [X]):-
\+ is_list(X).``````

Now `my_flatten([a, [b, [c, d], e]], X).` gives us `<strong>X</strong> = [a, b, c, d, e]`

## 8. Elimate consecutive duplicates of list elements

``````Example:
?- compress([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
X = [a,b,c,a,d,e]``````

This one was a little easier, so if two first two elements of the list are the same, we call compress removing one of those elements. If they’re not the same, we plonk one of those elements into the out list and call compress with the rest of the list:

``````
compress([X],[X]).