ONLamp.com
oreilly.comSafari Books Online.Conferences.

advertisement


Introduction to Haskell, Part 2: Pure Functions

by Adam Turoff
07/19/2007

General purpose programming languages can be divided into two broad categories: Haskell and everything else.

In Part 1 of this series, I described how all programming languages are grouped into four families: imperative, object-oriented, logic, and functional. Most programming languages start with an imperative core and add object-oriented or functional features on top. C, for example, is a purely imperative programming language. Languages like C++, Java, and C# build on C and wrap up this imperative model with objects. Perl, Python, and Ruby add a little bit of functional programming into the mix as well.

Haskell is different because it is a purely functional language. That is, it supports only the functional style of programming. This unconventional approach gives Haskell a reputation of being a difficult language to learn and use, especially among professional programmers who casually jump around between languages like Java, Perl, Python, PHP, and Ruby. Most languages focus on what features to add and blend to make developers more productive. Haskell takes the opposite approach, removing needless features until there is nothing left to take away.

Pure vs. Impure Functions

Functions are the heart of Haskell. However, functions in Haskell aren't like functions in other languages. Haskell functions are pure, meaning that they define a relationship between inputs and outputs, and have no side effects. This behavior mimics the notion of function you learned in algebra many years ago. Operations like square root, sine, and cosine are pure functions; the square root of four will always be two, regardless of how, where, or when it is computed.

Impure functions refer to external state, modify their behavior based on external state, or change external state. C functions like fopen(), printf(), and malloc() are examples. Calling malloc() returns a pointer to a different block of memory each and every time it is called, but when you attempt to allocate more than the operating system can provide, malloc() will fail. Similarly, if you attempt to allocate a large block of memory, malloc() may succeed, but cause the operating system to swap considerably, degrading performance for the entire machine. Clearly, impure functions are necessary, but unpredictable, because their behavior varies based on how, when, and where they are invoked.

Both kinds of functions are necessary to model the real world. Converting temperatures from Fahrenheit to Celsius is a pure function; by definition, 212° F should always convert to 100° C. Converting U.S. dollars to U.K. pounds is an impure function that is determined by a very large number of external variables, and there is no expectation that performing the same transaction at two different times or two different places should produce the same result.

Of course, to be a truly general purpose programming language, Haskell needs to support both pure and impure functions. Haskell makes impure functions available, but isolates them through the use of monads, which are actually built from pure functions. Monads are a deep and interesting topic, and are discussed in the next part of this series.

Programming with Pure Functions

Because pure functions refer only to their inputs, they are deterministic, easy to understand, and easy to predict. For example, a function like:

square x = x * x

will always receive a single argument, and return the value of multiplying that argument by itself. Therefore, an expression like square 2 always returns 4. A function that computes 2 * 2 and writes a message to the console or a logfile is an impure function whose behavior cannot be predicted; the computation may succeed, but the function may fail, due to the logging operation. Logging may succeed most of the time, but there is no way to predict whether this function will attempt to write to a closed file handle, write to a file on a filesystem that is no longer available, write to a full filesystem, or any of a number of other I/O failures.

The key to understanding pure functions is to think in terms of small, composable units of code. Simple operations like addition, multiplication, sine, cosine, and concatenation are all pure functions. Pure functions can be composed from other pure functions, like these here:

f x = (3 * x * x) + (6 * x) + 9

Many functions depend on more than one value, and accept multiple arguments:

min a b = if a < b 
            then a 
            else b

Note that Haskell can use indentation to signal when an expression is defined over multiple lines. This is known as the off-side rule, and is similar to Python's rules for block scoping. Unlike Python, Haskell's off-side rule is merely a convention for inferring where to place curly braces and semicolons around a series of expressions and statements. Either form is valid, but using the off-side rule is the more convenient and more common form. (The Haskell 98 Report defines the precise interpretation of the layout rule.)

Some functions are complex and refer to more involved sub-expressions. Here is a function that calculates the cost of a shopping basket, where some items are taxable, and others are not:

taxRate = 0.06

total cart = subtotal + tax
  where
    subtotal = sum cart
    taxable  = filter isTaxable cart
    tax = (sum taxable) * taxRate

This example defines two functions, taxRate, which returns a constant value, and total, which computes the total cost of the list of items in a shopping cart. (Although the taxRate definition appears to be defining a variable, it's best to think of it as a constant function, a function that takes no parameters and always returns the same value.) The definition of total is quite expressive, and highlights the intent of the function, by isolating and naming important sub-expressions in the computation. (total also refers to an isTaxable function, not presented here.)

The where clause in total defines meaningful sub-expressions that are used to evaluate the primary expression, subtotal + tax. The subtotal, as you would expect, is just the sum of all the items in the cart. The definition of tax refers to taxable, which is the subset of all items in the cart that are taxable (more precisely, the set of items in the cart where isTaxable is true for that item). Computing the tax involves computing the sum of the taxable subset, and multiplying it by the tax rate. The two utility functions sum and filter do what their names imply and are predefined in the Prelude, Haskell's standard library of useful functions.

We could also define total by avoiding the sub-expressions in the where clause, and writing the entire computation out in a fully expanded form. This version is just as correct, but much harder for people to understand:

total cart = (sum cart) + 
             (sum (filter isTaxable cart)) * taxRate

The compiler doesn't care how you write these functions, because they are equivalent expressions of the same idea. In fact, the compiler is allowed to rewrite the first definition into the second. However, using tools like where clauses and libraries of useful and reusable functions can help make functions concise and expressive, and easier for people to read.

Real-World Functional Programming

Haskell has deep roots in the world of mathematics, and it is easy to see how it can be used to define simple mathematical functions. However, real-world problems have very little in common with simple mathematical functions.

Or do they?

Consider a program that needs to find the 10 most-used words in a document. Assume for the time being that the document is available as a string value. (Reading a file from disk or standard input would require using the I/O monad, which will be discussed in the next article in this series.)

Fortunately, there are a variety of pre-defined functions in the Prelude that can make this job simple. The first step is to convert a document into a list of words. This is precisely the operation performed by the words function in the Prelude:

top10 doc = ....
  where
    listOfWords = words doc
    ...

Next, the list of words needs to be normalized so that variations in capitalization don't sway the results. One way to do this is to convert every word to lowercase. However, there is no lowercase that converts every uppercase character in a string to its lowercase equivalent. But there is a toLower function in the Data.Char library that will lowercase one character. Using map we can apply this transformation to each character in a string:

import Data.Char

lowercase str = map toLower str

Or, more consisely:

import Data.Char

lowercase = map toLower

The Haskell compiler can infer that lowercase must take a string (a list of characters) as an argument, because it knows that map takes two arguments (a function and a list), and toLower converts one character into another. Because map toLower needs one argument, lowercase must need the same argument.

Updating the definition of top10 is easy. Instead of splitting the document into a list of words, we can split the lowercased version of the document into a list of lowercased words:

import Data.Char

lowercase = map toLower

top10 doc = ....
  where
    listOfWords = words (lowercase doc)
    ...

Next, the words need to be sorted and grouped. These operations can be performed by the sort and group functions in the Data.List library. The sort function does what you would expect. The group function takes a list of values and returns a list of nested lists, where each nested list contains adjoining equal values. For example:

$ ghci
Prelude> :module + Data.List
Prelude Data.List> group [1,3,3,1]
[[1],[3,3],[1]]
Prelude Data.List> group (sort [1,3,3,1])
[[1,1],[3,3]]

Adding this feature to top10 is straightforward:

import Data.List

top10 doc = ....
  where
    listOfWords = words (lowercase doc)
    wordGroups  = group (sort listOfWords)
    ...

Pages: 1, 2

Next Pagearrow





Sponsored by: