# Seven Languages in Seven Weeks: Prolog Day 2

Here are my answers for the questions on day two of the Prolog chapter.

Reverse a list.

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

reverse_list([X|[Y|[]]], [Y,X]).

reverse_list([X|[Z|[Z2]]], [Z2, Z, X]).
```

Find the smallest element in a list.

```smallest([Head|Tail], Smallest) :-

smallest([], Smallest, Smallest).

smallest(Tail, Smallest1, Smallest).
```

Sort a list.

```reorder_elements([], _, [], []).

reorder_elements([X|Tail], Pivot, [X|LowElements], HighElements)
:- X < Pivot,
reorder_elements(Tail, Pivot, LowElements, HighElements).

reorder_elements([X|Tail], Pivot, LowElements, [X|HighElements])
:- X > Pivot,
reorder_elements(Tail, Pivot, LowElements, HighElements).

sort_list([], []).

sort_list([Pivot|Tail], SortedList)
:- reorder_elements(Tail, Pivot, LowElements, HighElements),
sort_list(LowElements, SortedLowElements),
sort_list(HighElements, SortedHighElements),
append(SortedLowElements, [Pivot|SortedHighElements], SortedList).
```

For this one, I remembered my college days where I had a course where we used Prolog. We had to implement Quicksort, so that’s what I went for. I started with the Wikipedia description of Quicksort but after wrestling with a stack overflow exception I had to look into my copy of Prolog Programming in Depth .

The algorithm in the book is similar, except that it uses the ! (cut) operator for optimisation. This operator allows Prolog to disregard other rules after it has crossed the cut operator.

The append rule is defined in Gnu Prolog as well as in other Prolog implementations.