Select Page

PL Perspectives

Perspectives on computing and technology from and for those with an interest in programming languages.

Functional Algorithm Design, Part 1

by Jeremy Gibbons on Nov 25, 2020 | Tags: , , ,

Functional Algorithm Design, Part 1

This is the middle part of a three-part article describing the approach that Richard Bird and I took to using functional programming for algorithm design in our recent book Algorithm Design with Haskell.

Part 0 contrasted algorithm development in a functional style with the corresponding activity using an imperative language. In this part, we see how the functional approach can be applied to the class of greedy algorithms: these can be used when the characteristics of a problem allow a globally optimal solution to be reached by making a series of locally optimal steps. Greedy algorithms are often very simple, but the proof that they do indeed yield a globally optimal solution can be surprisingly tricky. The final Part 2 presents the main novelty of the book: a step outside pure FP to admit careful and limited use of nondeterministic functions, which turn out to be necessary for the typical situation when the solution ordering being optimized admits ties.

Greedy algorithms

Let’s look at greedy algorithms as a more interesting example. We’ll consider algorithms that construct a single optimal candidate out of a collection of components. Instances include Huffman coding (a shortest encoding constructed from given symbols), line breaking (a least wasteful paragraph constructed from given words), minimum-cost spanning tree again (a lightest spanning tree constructed from given edges), and making change (a smallest handful of coins constructed from given denominations).

The greedy approach assembles an optimal candidate step by step from the given components, maintaining just a single partial candidate throughout: “think globally, act locally”. This generally leads to a simple algorithm, but often one with a tricky proof of correctness.

The problem can be specified as computing a minimum-cost candidate from given components:

\displaystyle \begin{array}{@{}l} \mathit{mcc} :: [\mathit{Component}] \rightarrow \mathit{Candidate} \\ \mathit{mcc} = \mathit{minWith}\;\mathit{cost} \cdot \mathit{candidates} \end{array}

Here, {\mathit{minWith}} selects from a non-empty list the (leftmost) minimal element according to a given cost function:

\displaystyle \begin{array}{@{}l} \mathit{minWith} :: \mathit{Ord}\;\beta \Rightarrow (\alpha\rightarrow\beta) \rightarrow [\alpha] \rightarrow \alpha \\ \mathit{minWith}\;f = \mathit{foldr1}\;(\mathit{minBy\;f}) \\ \quad\mathbf{where}\; \mathit{minBy}\;f\;a\;b = \mathbf{if}\;f\;a \le f\;b \;\mathbf{then}\;a\;\mathbf{else}\;b \end{array}

({\mathit{foldr1}} is a standard Haskell function to aggregate a non-empty list). We will suppose that {\mathit{candidates}} can be written as an instance of {\mathit{foldr}}:

\displaystyle \begin{array}{@{}l} \mathit{candidates} :: [\mathit{Component}] \rightarrow [\mathit{Candidate}] \\ \mathit{candidates} = \mathit{foldr}\;\mathit{step}\;c_0 \\ \quad \mathbf{where}\; \mathit{step}\;a\;c = \mathit{concat}\;(\mathit{map}\;(\mathit{extend}\;a)\;c) \end{array}

constructing a finite non-empty list of candidates, starting with a trivial initial candidate {c_0 :: \mathit{Candidate}}, and using a function {\mathit{extend} :: \mathit{Component} \rightarrow \mathit{Candidate} \rightarrow [\mathit{Candidate}]} that extends a single candidate by a single component in all possible ways. (The book also considers problems where {\mathit{candidates}} uses a different recursion pattern.)

For example, consider sorting a string: the components are characters, and candidates are strings, permutations of those components. The trivial initial candidate {c_0 = \mbox{``\,''}} is the empty string, and is extended by each component in turn in all possible ways:

\displaystyle \mathit{extend}\;x\;c = [ c_1 \mathbin{{+}\!\!\!{+}} [x] \mathbin{{+}\!\!\!{+}} c_2 \mid n \leftarrow [0 .. \mathit{length}\;c], \mathbf{let}\;(c_1,c_2) = \mathit{splitAt}\;n\;c ]

So {\mathit{extend}\;\mbox{`a'}\;\mbox{``bcd''} = [ \mbox{``abcd''} , \mbox{``bacd''}, \mbox{``bcad''}, \mbox{``bcda''} ]}. The cost to be minimized is the inversion count, the number of out-of-order pairs in the permutation:

\displaystyle \mathit{ic}\;c = \mathit{length}\;[(x,y) \mid x:c' \leftarrow \mathit{tails}\;c, y:c'' \leftarrow \mathit{tails}\;c', x>y ]

Calculating the greedy algorithm

We can calculate a greedy algorithm for computing a minimum-cost candidate by fusing selection {\mathit{minWith}\;\mathit{cost}} with generation {\mathit{candidates}}, so that we maintain only a single candidate at each step. Since the generation process is an instance of {\mathit{foldr}}, we use the fusion law:

\displaystyle h \cdot \mathit{foldr}\;f\;e = \mathit{foldr}\;f'\;e' \quad\Leftarrow\quad h\;(f\;a\;b) = f'\;a\;(h\;b) \land h\;e = e'

Now {h} is {\mathit{minWith}\;\mathit{cost}}, {f} is {\mathit{step}}, {e} is {[c_0]}, {e'} is {c_0}, and we have to come up with a function {\mathit{gstep}}, the “greedy step”, to play the role of {f'}—that is, to satisfy

\displaystyle \mathit{minWith}\;\mathit{cost}\;(\mathit{step}\;x\;cs) = \mathit{gstep}\;x\;(\mathit{minWith}\;\mathit{cost}\;cs)

We calculate:

\displaystyle \begin{array}{@{}l} \quad \mathit{minWith}\;\mathit{cost}\;(\mathit{step}\;x\;\mathit{cs}) \\ =\qquad \{ \mbox{definition of }\mathit{step} \} \\ \quad \mathit{minWith}\;\mathit{cost}\;(\mathit{concat}\;(\mathit{map}\;(\mathit{extend}\;x)\;\mathit{cs})) \\ =\qquad \{ \mbox{distributive law} \} \\ \quad \mathit{minWith}\;\mathit{cost}\;(\mathit{map}\;(\mathit{minWith}\;\mathit{cost})\;(\mathit{map}\;(\mathit{extend}\;x)\;\mathit{cs})) \\ =\qquad \{ \mathit{map}\mbox{ distributes over composition} \} \\ \quad \mathit{minWith}\;\mathit{cost}\;(\mathit{map}\;(\mathit{minWith}\;\mathit{cost} \cdot \mathit{extend}\;x)\;\mathit{cs}) \\ =\qquad \{ \mbox{define }\mathit{gstep}\;x = \mathit{minWith}\;\mathit{cost} \cdot \mathit{extend}\;x \} \\ \quad \mathit{minWith}\;\mathit{cost}\;(\mathit{map}\;(\mathit{gstep}\;x)\;\mathit{cs}) \\ =\qquad \{ \mbox{greedy condition} \} \\ \quad \mathit{gstep}\;x\;(\mathit{minWith}\;\mathit{cost}\;\mathit{cs}) \end{array}

The first step is just to unfold the definition of the function {\mathit{step}}. The second step is a “bookkeeping law”: to aggregate a collection of collections, either combine them into one big collection to aggregate, or aggregate each subcollection and aggregate the intermediate results. The third step fuses two consecutive maps into one. The fourth step simply names the subterm {\mathit{minWith}\;\mathit{cost} \cdot \mathit{extend}\;x}. The fifth step

\displaystyle \mathit{minWith}\;\mathit{cost}\;(\mathit{map}\;(\mathit{gstep}\;x)\;\mathit{cs}) = \mathit{gstep}\;x\;(\mathit{minWith}\;\mathit{cost}\;\mathit{cs})

is wishful thinking: that taking the best final candidate obtained by making a greedy step from each of a collection of initial candidates gives the same result as taking a greedy step from the single best initial candidate. Call this wishful thought the greedy condition.

The point is that the greedy condition alone suffices to satisfy the premises of the fusion law; every other step in the calculation is universally valid. If the greedy condition is satisfied, then we have the greedy algorithm

\displaystyle \mathit{mcc} = \mathit{foldr}\;\mathit{gstep}\;c_0 \quad \mathbf{where}\;\mathit{gstep}\;x = \mathit{minWith}\;\mathit{cost} \cdot \mathit{extend}\;x

for finding the minimum-cost candidate. In words, from the empty candidate {c_0}, make a single greedy step with each component {x} in turn. A single greedy step consists of considering each possible way of extending the current candidate, and taking the (locally) best of them.

Greedy sorting

So, does the greedy condition hold for sorting? Sadly, it does not. Consider the two partial candidates “eabc” and “cbae” (in that order), each with inversion count 3, and suppose that the next component is ‘d’. Because these two candidates tie on inversion count, it is an arbitrary choice which is ‘minimal’; our {\mathit{minWith}} happens to pick the leftmost minimal element, namely “eabc”. But the best extension of “eabc” with ‘d’ is “eabcd”, with inversion count 4, whereas the best extension of “cbae” with ‘d’ is “cbade”, with inversion count 3. The single best initial candidate “eabc” does not lead to the best final candidate.

The essence of the obstacle is that ordering by inversion count is not linear, because not antisymmetric: two different permutations can have the same inversion count. I can think of three possible fixes.

The first fix is that sometimes this kind of tie can’t happen in context. In particular, for sorting, there is always a unique minimal-cost permutation, namely the sorted one (at least, it is unique when the elements themselves are linearly ordered). Although “eabc” and “cbae” are tied, they and all other permutations lose to “abce”. One can refine the calculation of the greedy algorithm to take this context into account, which will overcome the obstacle for sorting. However, this fix does not work for all greedy algorithms.

The second fix is to change the cost function. In the case of sorting, we can switch from {\mathit{ic}} to {\mathit{id}}—no-one said that the ‘cost’ had to be a number. This fixes the issue at a single stroke! The problem is then to find the lexically least permutation (namely, the sorted one), which will also be the one with minimal inversion count (namely, zero). In general, the ordering is refined to a linear order, often by adding dimensions to the cost function. However, I think this is really cheating: prejudicing the specification in light of the intended implementation.

The third fix, and the one taken forward in the book, is to allow nondeterministic functions in a few, carefully controlled places. Specifically, when there is a tie, we consider all optimal partial candidates, not an arbitrary single one of them. This third fix is explained in Part 2 of the article.

Bio: Jeremy Gibbons is Professor of Computing at the University of Oxford, where he leads the Algebra of Programming research group and is former Deputy Head of Department. He served as Vice Chair then Past Vice Chair of ACM SIGPLAN, with a particular focus on Open Access. He is also Editor-in-Chief of the Journal of Functional Programming, SC Chair of ICFP, on the Advisory Board of PACMPL, an editor of Compositionality, and former Chair of IFIP Working Group 2.1 on Algorithmic Languages and Calculi.

Disclaimer: These posts are written by individual contributors to share their thoughts on the SIGPLAN blog for the benefit of the community. Any views or opinions represented in this blog are personal, belong solely to the blog author and do not represent those of ACM SIGPLAN or its parent organization, ACM.