lukegarrigan

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).

reverse_me([Head|Tail], Z,X) :- 
    reverse_me(Tail, Z,[Head|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([Head|Tail], Out):-
    my_flatten(Head, FlatHead),
    my_flatten(Tail, FlatTail),
    append(FlatHead, FlatTail, Out).

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]).
compress([Head, Head|Tail], Out):-
    compress([Head|Tail], Out).

compress([Head,Head2|Tail],[Head|Zs]) :- 
    Head \= Head2, 
   compress([Head2|Tail],Zs).

Conclusion

Prolog is a very fun program to code, I’d say it’s quite difficult to read someone else’s code though, so this probably wasn’t the best idea for a blog 😂. I’ll probably tackle some more problems in the future as I really enjoy doing it.

If you liked this blog then please sign up for my newsletter and join an awesome community!!

Leave a Reply