Functional Prolog: Map, Filter and Reduce

Prolog is old, but one of the things it does really well is recursion. However, there's only so many decades you can write recursive predicates before you start to notice some patterns. These patterns can be abstracted out into meta-predicates, making our lives easier. They've also had a huge impact on big data computation through parallel programming. We'll look at the big three: map, filter and reduce.

Map

To map in functional programming is to apply some function onto every element of a collection, collecting the results in another collection. In Prolog, the commonly built-in maplist/N will assume this collection is a list, which it typically is. However, should you wish to apply a predicate to a collection of elements other than a list, such as a tree, all you need do is author a suitable maptree/N predicate that traverses your data structure.

Let's take a look at a simple maplist/N predicate.

maplist(_Predicate, []).
maplist(Predicate, [H|T]) :-
    call(Predicate, H),
    maplist(Predicate, T).

maplist(_Predicate, [], []).
maplist(Predicate, [H1|T1], [H2|T2]) :-
    call(Predicate, H1, H2),
    maplist(Predicate, T1, T2).

% and so on for increasing numbers of arguments

maplist(atom, [map, reduce, filter, NotAnAtom]).

maplist(upcase_atom, [map, reduce, filter], UpperCase).

By using call/N we can do some awesome things with only a single line because we can provide a predicate with some arguments to maplist/N, if your dialect of Prolog supports lambda functions you can also re-arrange the order of arguments via a lambda. (maplist([E]>>memberchk(E, [map, reduce, filter]), List))

maplist(between(1), [10, 100, 1000, 3], [5, 50, 500, Between1And3]).

Map is probably the easiest of these to get your head around and the most common. We'll take a look at the second easiest and probably most common next.

Filter

To filter is to apply a predicate to a collection to determine their inclusion in the output collection. In Prolog you'll often find an include/3 and an exclude/3 predicate, where include/3 will keep the element if the predicate is true whereas exclude/3 will keep the element if the predicate is false. Again the built-ins tend to assume a list in Prolog, but again there's nothing stopping you from taking the idea and applying it to a different data structure provided you can reduce the structure in some sensible way.

Let's take a look at some simple include/3 and exclude/3 predicates. We'll use the (_ -> _ ; _) conditional branching syntax for efficiency. Note, this includes an implicit cut, which you'll need to be wary of, however we don't know what predicate an author might feed as a goal to our predicates, which means we don't know how expensive it is to call. For this reason, we'll make sure to only call it once, hence the cut. Despite this aim for efficiency, we're not going to use a tail-call optimized recursion simply to aid in readability. Should this be important for you, a difference list will preserve the order.

include(_Goal, [], []).
include(Goal, [Head|Tail], Included) :-
    include(Goal, Tail, IncludedSoFar),
    ( call(Goal, Head)
    -> Included = [Head|IncludedSoFar]
    ; Included = IncludedSoFar
    ).

exclude(_Goal, [], []).
exclude(Goal, [Head|Tail], NotExcluded) :-
    exclude(Goal, Tail, NotExcludedSoFar),
    ( call(Goal, Head)
    -> NotExcluded = NotExcludedSoFar
    ; NotExcluded = [Head|NotExcludedSoFar]
    ).

include(atom, [map, Var, reduce, 1, filter, compound(term)], Atoms).

exclude(atom, [map, Var, reduce, 1, filter, compound(term)], NotAtoms).

Alright, we can take a collection, filter out the elements we're interested in and apply predicates to them. That's already a powerful set of ideas, but there's one more to come.

Reduce

To reduce is to take a collection and reduce it to a single element. This can be the most tricky and there are a few ways it can be done, especially if you're dealing with parallel computing. We'll look at the non-parallel folds, there's a left fold and a right one. To fold a collection is to combine the elements into a single element, the direction denotes the order in which they are combined. Note, a left fold can be tail-call optimized, a right one can't. Again, no need for this to be a list, but typically in Prolog, if you have a built-in foldl/N or foldr/N it'll be expecting a list.

To see why direction is important, consider that, for dividing a list of numbers: [1, 2, 3], we can either do: 1 ÷ (2 ÷ 3) = 1½ or (1 ÷ 2) ÷ 3 = ⅙. When folding from the right: 1 ÷ (2 ÷ 3), we'll need to run through the list to the last element then start applying the predicate on the way out of the recursion. When folding from the left: (1 ÷ 2) ÷ 3, we'll start applying the predicate to elements as we meet them.

If you look elsewhere for fold functions, and perhaps predicates, you'll likely find talk of the generative element, this is the argument that can be provided with another one such that the result of the function is the "other one". So for addition, this would by 0: x + 0 = x, for multiplication it would be 1: x * 1 = x. This is an implementation detail and leftover from the functional theories upon which these are based. As pragmatists we'll be replacing it with the actual leftmost or rightmost element of the list so that we don't need it.

% foldr, peel off the last element for the base
foldr(_Predicate, [LastElem|[]], LastElem).
% travel down the list, calling the predicate on exit
foldr(Predicate, [H|T], Result) :-
    foldr(Predicate, T, Acc),
    call(Predicate, H, Acc, Result).

% foldl, peel off the first element for the base
foldl(Predicate, [H|T], Result) :-
    foldl(Predicate, T, H, Result).

% call the predicate to update the accumulator, then continue
foldl(Predicate, [H|T], Acc, Result) :-
    call(Predicate, Acc, H, NewAcc),
    foldl(Predicate, T, NewAcc, Result).
% emptied the list, the Accumulator is the Result
foldl(_Predicate, [], Result, Result).

add(A, B, C) :-
    C is A + B.

divide(A, B, C) :-
    C is A / B.

foldl(add, [1, 2, 3], Result), foldr(add, [1, 2, 3], Result).

foldl(divide, [1, 2, 3], LeftFold).

foldr(divide, [1, 2, 3], RightFold).

So there we go, we can now apply a predicate between elements of a list to reduce that list to a single element. Before you get carried away basking in the wonder of it all, note that this implementation only works in the forward direction, other modes of use make an interesting exercise!

Conclusion

These are the big 3 of functional programming, may they save your fingertips from much typing when authoring the procedural meaning behind your Prolog. Not only that, but we've done the whole lot without a mention of Haskell or Category Theory, until now at least! If you were disappointed by this, you may enjoy Mercury.

A couple of things to pay attention to, all of these predicates are Functor/N, because they can be called with multiple lists if your goal predicate uses them. Also, these are abstractions of common patterns, be wary of using them for a non-common pattern. Each of these traverse the list at least once, sometimes you'll find yourself using these in a way that you're traversing the list multiple times, when writing your own recursive predicate could do the job in one traversal.

There's lots to be playing with here, before you write your own do check to see if your Prolog dialect provides them as built-ins, they are quite popular. When you're comfortable with these, see if your dialect offers lambdas too!