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(Tail, Head, Smallest).	

smallest([], Smallest, Smallest).

smallest([Head|Tail], Smallest0, Smallest) :-
	Smallest1 is min(Head, Smallest0),
	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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s