Adventures in Prolog - Computations with lists

My last post was concerned with basic computations in Prolog using the powerful technique - recursion. Today's post is concerned with recursion as well, but this time recursion is applied to Prolog's main data structure - the list.

A list in Prolog is a recursive data structure itself. Why? Because a list can be built by remembering the following ...

1. the empty list [] is a list
2. a list can be built by appending any list T to an item H, which yields [HT]

Using this definition we can see that the list [1, 2, 3, 4] is indeed a list with H = 1 and T = [2, 3, 4]. Consequently, a list cannot only be built from points 1. and 2. but also decomposed according to 1. and 2. Therefore 1. and 2. form the underlying principle when computing with lists in Prolog.

Now that we have covered the basic principle underlying a list. I will present two operations on lists - the addition of elements of a list (sumList) and the multiplication of elements of a list (mulList).

Both operations make use of the presented recursive structure of a list. The needed recursion anchor is the processing of the empty list. This maps to the identity operation in addition and multiplication. Identity in addition is performed using the zero element thus - a + 0 = 0 + a = a. Identity in multiplication is done by multiplying with the one element thus a * 1 = 1 * a = a.

Employing both identities, the definition of sumList and mulList become straightforward. A list is peeled down until it is stripped to the empty list, in this case the identity operation is performed. While peeling the list each element is either added or multiplied with the result obtained by performing the operation on the remaining unpeeled list (the list's tail T).

%sumList/2 sum list elements%
sumList([], 0).
sumList([HT], L) :-
sumList(T, L1),
L is H + L1.

%mul list elements%
mulList([], 1).
mulList([HT], L) :-
mulList(T, L1),
L is H * L1.

In my next post, I will cover the abstraction from special computations on lists to defining a general operation on a list, which executes a special function on each list item. This is similar to F#'s list-map function.