Lecture 26: The Path Less Taken

Administrivia

As the final lecture of this course, I'd like to note that you stand at a fork in the road. There will be courses in functional programming available to you in the future, and perhaps even a more advanced course in Haskell. But it is possible for you to avoid functional programming, and many of you will chose to do so. We hope that if this is your last experience with functional programming, you'll still have benefited from it, and that it will color the way you think about programming going forward. Certainly, it's the case the traditional languages are in the midst of embracing functional constructs, and what you've learned here almost certainly will give you a leg up going forward.

But today is really for the rest of you: those who've enjoyed the expressiveness and power of functional programming, and who want to pursue the subject further. There are a number of courses offered here of possible interest, which somehow use or involve functional programming:

There are also many opportunities for self-study, and Haskell in particular seems to have inspired a rich, but generally accessible, technical literature, along with a large number of web articles, tutorials, etc. And there is always the possibility of using Haskell in your own projects, and gathering expertise thereby. We want to give you a few landmarks to help guide your journey.

Standard Modules

The Haskell Platform ships with a large variety of modules, some a part of GHC's core, along with others that have proven to be useful to the Haskell community generally. Some of these modules provide access to specialized capabilities, e.g., network or database access. But there is a large number that provide quality implementations of more advanced data structures than we've encountered in this course.

Indeed, we've relied very heavily on a few data structures: lists, tuples, a few standard monads, our own (often naïve) algebraic data types. These have been "good enough" for our immediate pedagogical purposes, which include creating a natural familiarity with these types, but there are often good reasons to consider more sophisticated types, and the modules that support them. To a certain extent, knowing these "good reasons" is why we require CS majors to take a course in Algorithms, which provides means of analysis that aren't accessible yet, but you will get to that point, and will be glad to know that Haskell's libraries provide more suitable data structures.

Data.Sequence

[] is wonderful, but sometimes we want a list-like data-structure that supports a larger set of efficient operations, e.g., constant time access to both ends, or efficient concatenation. If we can accept the restrictions of finiteness and strict underlying operations, Data.Sequence provides this.

Data.Set

Sets are the basic abstraction of mathematics, and a useful data abstraction in programming. We have often used lists over types that implement the Eq type class to represent sets, but this can be a inefficient implementation.

If our underlying type implements Ord, we can use the Haskell Platform's Data.Set, a balanced-binary tree implementation of sets. This module is meant to be imported qualified, as many of its functions clash with Prelude functions.

import Data.Set (Set) import qualified Data.Set as Set

The basic functions for constructing sets are

Where the power of sets really comes into play is operations that combine sets, e.g.,

There are a large number of other operations, e.g., member for element testing, findMin, deleteMin, analogous functions for max, null which tests a set for emptiness, and size which computes the number of elements in a set. A general rule of thumb is that before writing a new Set function, check and make sure that it hasn't already been implemented in Data.Set.

One of the disappointments with Set type is that Set is not a functor or a monad, nor can it be without considerable deviousness because of the constraint that the elements of a Set must be ordered. This is something that people are thinking about.

Data.Map

The Map type can be thought of as a an association list with more efficient operations, but the implementation is basically that of a Set in which the values are carried along with the keys. Naturally, this gives rise the Ord type class constraint on the keys of a Map.

Data.IntSet, Data.IntMap

There are specialized versions of the Set and Map types for use in the common case where the elements/keys are of type Int, and the actual keys in use are a dense subset of an interval. This allows for an array-like implementation, with substantially better lookup efficiency.

Data.Array

Surprisingly, Haskell does support an array type, but remembering that Haskell is a pure language, there's an obvious issue associated with assignment, because somehow we have to end up with both the old array and the new one. The effect of this is that Haskell has an array type that supports very efficient build and look-up, but the cost of an assignment is the same as the cost of a build, i.e., linear in array size. This means that naïve translations of array-based algorithms into Haskell can be hopelessly inefficient, but... many array-based algorithms can be re-expressed as iterative builds, i.e., as a sequence of steps in which a single new array is built based on values from the old array. In such cases, the algorithms can be very efficient.

The basic array type is Array i e, where i is the index type, which must belong to the typeclass Ix, and is often Int. Note, though, that Ix is closed under tuples, e.g., there is an instance (Ix a, Ix b) => Ix (a,b), enabling the use of multidimensional arrays.

Note that the bounds of an array are not a part of its type, unlike other programming languages.

One of the places where Haskell arrays really shine is in implementing dynamic programs -- these are programs in which solutions to sub-problems are memoized, avoiding unnecessary recalculation. Consider the problem of counting the number of distinct binary trees with n nodes. This can be attacked directly via a simple recursive program:

countTrees:: Integer -> Integer countTrees n = if n == 0 then 1 else sum [ countTrees left * countTrees right | left <- [0..n-1] , let right = n-left-1 ]

There is only one tree with zero nodes, the empty tree. For non-empty trees, after fixing the top node, we consider each of the ways of dividing the remaining nodes between the left and right subtrees, and count each way of combining a distinct left subtree with a distinct right subtree.

The code here is conceptually quite clear, but unfortunately, it's not fast: computing countTrees 15 takes a few seconds on a modern machine, but countTrees 30 would require more than a century. Can we do better?

Our approach will be to fill an Array with values of the function, while using those same values to facilitate the calculation:

countTreesFast :: Integer -> Integer countTreesFast n = a ! n where a = array (0,n) [(i,ct i) | i <- [0..n]] ct n = if n == 0 then 1 else sum [ a ! left * a ! right | left <- [0..n-1] , let right = n-left-1 ]

Let's take this apart:

The performance characteristics of countTreesFast are very different from countTree. We can compute

> countTreesFast 100 896519947090131496687170070074100632420837521538745909320

almost instantaneously, and

> countTreesFast 1000

in a few seconds, obtaining a 598 digit answer.

Data.ByteString

String is wonderful, but it comes with very large space overheads and associated inefficiencies, especially if we're dealing with strings of ASCII characters on 64-bit machines. A ByteString is packed arrays of Word8's, i.e., raw bytes, suitable for high-performance/large data quantities. I've used ByteString to handle bioinformatics data-sets containing hundreds of megabytes of ASCII data. You wouldn't want to do this with ordinary Haskell strings, which take 20(!) bytes of memory to represent a single byte of data. There are basically two costs associated with ByteString: first cons is expensive, as it involves recopying the array, the second is that non-ASCII characters cannot easily be represented. The default Data.ByteString class adds the further complication that the values of the array are not typed as characters. This often makes Data.ByteString.Char8 more convenient in practice.

Data.Text

Data.Text provides a more efficient representation of Unicode text than String, albeit at the cost of requiring you to learn the interface.

Additional Language Features

We've presented Haskell as a pure, lazy, functional programming language. In fact, it's not perfectly pure, either in its purity, or its laziness. It's just that pure and lazy are the defaults.

Seq and friends.

There's a primitive Haskell function, seq :: a -> b -> b, which can be used to force the partial evaluation of a term into so-called "weak head normal form," i.e., sufficiently defined so that the least non-trivial pattern match can succeed. Using seq provides a very fine-grained control over when and how evaluation takes place, and there are sometimes good reasons for wanting to exercise this level of control.

If you have code that you think should be running in constant space, but isn't, it's often because laziness is creating thunks (unreduced expressions) where you're not expecting them. In such cases, adding a seq can force an evaluation, and eliminate the space leak.

There is a trap here. Programmers with an inaccurate understanding of Haskell's evaluation model often find it difficult to understand how seq helps, but know (if only by anecdote) that sometimes it does. So they start to "sprinkle" their code with seq's, in the hope that something good will happen. And sometimes (often enough to reward bad behavior), it does. The problem here is that unnecessary seq's can actually make your code slower and/or less space efficient. It's not that lazy vs. eager is a choice between good and bad, or bad and good if you prefer, but that each context needs to be understood before any reliable judgment can be made.

It is somewhat easier to use bang-patterns, i.e., strictness annotations on either data (which doesn't require a language extension) or on functions (which does require a language extension), which is worth keeping in mind if you need them. Seek, and you will find.

Control.Monad.ST

It's a bit confusing, if you dig through the Haskell Platform documentation, to encounter what appear to be two distinct state monads: Control.Monad.State, and Control.Monad.ST. The difference is that the former provides the illusion of state, implemented by pure means; whereas the later gives you honest-to-goodness assignment and mutability. It is indeed possible to write Fortran programs in Haskell.

Control.Monad.ST isn't for the faint of heart. It's verbose, and more than a bit dangerous. But the essential genius of Control.Monad.ST is that it enables you to implement "pure" functions by impure means, and there are sometimes (less often than you'd think, but not never) opportunities to write far more efficient code this way. In particular, Data.Array's accumArray function (a kind of index-based foldr for arrays) has such an implementation, and accumArray is a very useful function to know about.

The Rest of the Typeclassopedia

We've encountered a large number of algebraically- and category-theoretically inspired type classes this quarter, but we've hardly exhausted the topic. The next type class for you to learn is Traversable, after which it's useful to turn your attention to Category and Arrow. The Arrow type class is heavily used in various libraries, notably the HXT (Haskell XML Toolkit) modules.

Parallel and Concurrent Haskell

One of the nicest parts of a pure language is that it is relatively easy for the language compiler to support parallelism, as purity entails a lack of dependence on order of operations. Haskell was written in such a way as to support parallel and concurrent programming, and there are nice libraries (and an eponymous and excellent book in the O'Reilly series written by Simon Marlowe) that support it.