The programming languages that businesses have used for the past 50 years -- COBOL, C, C++, and the Java language -- are imperative languages; they let you tell your program how to do what it does. Functional programming languages let you tell your program what to do. This article explores functional programming by giving you an introduction to Haskell. (If you caught my Crossing borders article on concurrent programming with Erlang, another functional language, you've had a bit of a head start.)

When I researched Beyond Java (see Resources), three of the experts I interviewed mentioned Haskell as a language I should explore. At the time, I didn't think our marketplace was ready for a functional language because the paradigm is so alien to most programmers. I still don't think we're ready. But I've come to appreciate the raw productivity and power that a functional language can provide. I've just begun to get my head around Haskell, but the language has already had an impact on how I solve problems in the Java and Ruby languages.

Imperative languages and their drawbacks

Imperative programs are formed by a sequence of statements with an explicit order, and their algorithms and programming constructs rely heavily on application state. It's hard to imagine programming languages without these characteristics because imperative languages' "tell me how to do it" approach is so firmly entrenched in our everyday programming philosophies. Imperative programming definitely shapes your thinking. But learning the alternative tools in functional languages can expand the way you look at a problem. Consider these imperative constructs:

• Assignment. Users of imperative languages rely on assignments more than any other programming technique. Functional languages allow at most one assignment per variable. Any assignment that changes a value is called a destructive assignment and is not permitted. For example, most functional languages would not allow x = x + 1.
  
  
• Iteration. Imperative-language programs use iteration to process many different types of data structures. Many imperative control structures rely on destructive assignment to do iteration.
  
  
• Side effects. In imperative languages, any method that can possibly return different values, given the same input, has side effects. And any method that impacts the state of application variables also has side effects. Functional languages have no side effects.

If you haven't used functional languages, it's hard to imagine how to write applications without destructive assignment and side effects. But these bedrock features lead to some of the more serious problems with imperative languages:

• Correctness issues. A method with a side effect can return a value but also changes the program's state. Side effects complicate the math required to prove program correctness. But the complications go beyond the math: Side effects make it harder to test, understand, analyze, and document a program's behavior.
  
  
• Order-based bugs. Many optimizations depend on reordering key programming instructions to improve performance. When a program that depends on a given sequence is reordered, mistakes happen.
  
  
• Concurrency problems. When mutable state goes away, almost all concurrency problems go away with it. Brian Goetz concludes the first chapter in Java Concurrency in Practice (see Resources) with the rule "It's the mutable state, stupid."

Believe it or not, you can program efficiently without enforcing the order of operations or using side effects.

Back to top

Introducing functional programming

In mathematics, a function maps each input to a specific output. The functional-programming paradigm uses mathematical functions to express programs. Rather than executing commands, all functional languages express and evaluate mathematical functions to solve problems. Functional languages also usually have these two characteristics:

• Immutable data. Pure functional languages do not rely on operations that save or retrieve state and do not allow destructive assignments.
• No side effects. A function always returns the same value when invoked with the same input.

This is a slight oversimplification of most functional languages, but only a slight one. Functions known as monads are used to express changes in state mathematically, and functional languages such as Haskell tend to use monads to process input/output and manage changes in state.

Now that you've seen some of the restrictions of functional programming, you're probably thinking the programming paradigm is a step back to the dark ages, but stay with me. Functional languages are not toothless. In fact, language experts generally believe functional languages operate at a higher abstraction level than most object-oriented languages. They provide some tools that imperative languages usually don't. You'll see some of these tools in action throughout this article.

Back to top

Using Haskell

Two Haskell implementations are making noise: Hugs and the Glasgow Haskell Compiler (GHC) (see Resources). Dozens of other Haskell compilers and interpreters exist, including offshoots of Hugs and the GHC, but they are the main two. If you're new to Haskell, the Hugs interpreter is a good choice because it's easy to install and understand. Hugs does have two serious limitations: it lacks a compiler and you can't use stand-alone functions; you must load all functions from a file instead. More serious programmers are likely to use GHC. Its interpreter is a little slower, but it has a compiler mode and allows stand-alone functions. I'm using Hugs for this article, so you should use it too if you're interested in coding along, because the two dialects vary in a few ways.

Coding in Hugs

Download Hugs (see Resources) for your OS and start it up. I tabled my trusty Macbook Pro in favor of my Windows machine to get an environment I could install quickly. WinHugs is a Hugs implementation with a one-click installer for the Windows platform.

You'll see an interpreter window with a Hugs prompt. Start simply. Type a few numbers and math expressions, as in Listing 1. You'll see that Hugs returns a math expression's result. That's the behavior you'd expect within a functional language.

Haskell 98 mode: Restart with command line option -98 to enable extensions

Type :? for help
Hugs>5
5
Hugs>5+4
9

Haskell has a powerful typing model. The language is strongly typed, meaning you can do allowed operations only on a given instance of a type. (If you try to add a number to a string, for example, Hugs complains.) Haskell is statically typed, so once you assign a variable to a value, the variable always holds the same type. Haskell does some type inference, meaning it infers the types of elements from syntactic clues in a program, so you'll see me use some functions without declaring associated types. Haskell complains if you use a type ambiguously or if you try to use an unsupported type with a function. Haskell also has subtypes and is completely polymorphic; these features go beyond this article's scope, but they're worth exploring on your own if you're interested.

Now that you've seen some primitive types such as integers, it's time to move on to a few slightly more sophisticated types. Often, the available data structures within a language define the way the language is used. C uses structs, and Java uses classes. Haskell uses neither.

The three most prominent data structures in Haskell are tuples, lists, and user-defined types. I'll focus on the first two. Tuples, which you surround with ( ), have a fixed length. Tuples contain primitive elements of mixed types and can even contain other tuples or lists. Lists, in contrast, have a variable length and are made of homogeneous elements. You surround a list with [ ]. You can use Hugs to experiment with tuples and lists, as in Listing 2:

Hugs> [1,2]
[1,2]
Hugs> [1,"a"]
ERROR - Cannot infer instance
*** Instance   : Num [Char]
*** Expression : [1,"a"]

Hugs> (1,2,3)
(1,2,3)
Hugs> (1,"a")
(1,"a")

Hugs> [(1,2),(3,4)]
[(1,2),(3,4)]
Hugs> [(1,2),(3,4),(5,6,7)]
ERROR - Type error in list
*** Expression     : [(1,2),(3,4),(5,6,7)]
*** Term           : (5,6,7)
*** Type           : (c,d,e)
*** Does not match : (a,b)

In Listing 2, you can see that each element in a tuple can be of a different type, but the types in a list must be homogeneous. Further, if you have a list of tuples, each of the tuples must have the same length, and the type of the nth element in a tuple must match the nth element in all of the other tuples in the list.

As you'd expect, Haskell has many functions that operate on lists. The simplest are head and tail. head returns the first element of a list, and tail returns everything else. Listing 3 shows some simple list functions:

Hugs> [1,2,3,4,5]
[1,2,3,4,5]
Hugs> length [1,2,3,4,5]
5
Hugs> head [1,2,3,4,5]
1
Hugs> tail [1,2,3,4,5]
[2,3,4,5]

In Listing 3, you can see that head returns an element, and tail returns a list of elements. You'll see later (in Writing functions) how these functions form the backbone of many recursive functions in Haskell.

When you're building a list, you use the : operator, called the cons operator (for construct). To build a list, you simply pass an element to another list. You can chain many cons operators together.

Strings are simply syntactic sugar for a list of characters, and lists such as [1,2,3] are syntactic sugar for 1:2:3:[]. This feature makes string operations much easier to implement. Listing 4 shows how cons works and how to build a string out of a sequence of characters:

Hugs> 6:[]
[6]
Hugs> 6:[7]
[6,7]
Hugs> 6:7:[]
[6,7]
Hugs> 'd':'o':'g':' ':'h':'a':'s':' ':'f':'l':'e':'a':'s':[]
"dog has fleas"

The kind of syntactic sugar you'll find with strings and lists is common in Haskell, but just remember: Everything is a function.

Treating functions as data

Haskell lets you treat functions as data. This important capability lets many Haskell functions take a function as a parameter. This strategy lets you apply a function to each of a function's elements in a variety of ways. Listing 5 shows a series of functions that apply functions to each element of a list:

Hugs> :l Char
Char> map toUpper "Hello"
"HELLO"
Char> filter isUpper "To Be or Not to Be"
"TBNB"
Char> foldr (max) 0 [1,2,3,2,1]
3
Char> foldr (+) 0 [1,2,3,2,1]
9

The :l command loads a module. You can then call the functions in the Char module. (Other versions of Haskell allow, for example, Char.toUpper, but Hugs doesn't, so you load a module and then use the functions in it.) The first statement calls a function (in this case, toUpper, which converts a character to uppercase) on each element of a list. Because Haskell strings are just lists of characters, you get the "HELLO" string back. The filter function calls a test function, which returns a boolean, on each element of a list and includes that element only if the test function returns True.

fold functions are a little more complicated. They come in two forms: foldl and foldr. A fold function takes a function, an element, and a list. You can think of a fold function in this way:

1. Start by placing the element (the second parameter) on the left (foldl) or right (foldr) side of a list.
2. Place the operator between all elements in the list.
3. Apply the operator, from one side of the list to the other, beginning with the left for foldl or right for foldr.

For example, foldr (+) 0 [1,2,3] reduces to 1 + (2 + (3 + 0)), or 6. Sometimes order matters, which is why Haskell provides both foldr (right associative, building from right to left) and foldl (left associative, building from left to right). When you're dealing with lists, the fold functions provide a good way to roll up results of any binary computation.

Combining functions

You can combine functions in many different ways within Haskell programs. Composing functions in complex ways is the key to productivity in functional languages because you're continually raising your level of abstraction.

For example, think of a Java application to count the number of uppercase letters in a sentence. You'd need to iterate over the list, incrementing a local variable by 1 each time you encounter an uppercase character. In Haskell, you'd simply take the length of a filtered list, with length (filter (isUpper) "To Be or Not to Be"). This is how a Haskell programmer works around using destructive updates. Each function keeps its intermediate results internally, and you're not burdened with such details.

Back to top

Writing functions

If you're using Hugs, you need to compose your functions in a separate source file. WinHugs has decent integration to my editor, so it's not too much of a burden. You place functions in a module and load the module with the :l command. You've already seen me load the system module Char in Listing 5. Module names, and the files that contain them, begin with an uppercase character. Functions begin with a lowercase character. Haskell program files end with a .hs extension.

You'll notice Haskell programs frequently use recursion to solve a problem. Java developers often eschew recursion because of the performance implications and stack-depth limitations. Haskell has two primary advantages when dealing with recursion: Haskell optimizes tail recursion, and Haskell is lazy.

Tail-recursion optimization means the compiler or interpreter can express recursion as iteration if recursion occurs at the end of a function. Tail-recursion optimization has no stack overhead, so the strategy reduces the cost of processing recursion to simple iteration. To understand what I mean by lazy, type the following function into a file called Generate.hs:

generate = 1:generate

This function is an infinite list of 1s. More precisely, generate adds 1 to the results of generate through the cons operator -- initially, an empty list. If you were to load and execute the function, you'd go into a recursive infinite loop because nothing would stop the recursion. Oddly enough, you can use the results of generate within your applications, as in Listing 6:

Hugs> :l Generate
Main> head generate
1
Main> head (tail generate)
1

Though generate represents an infinite list of 1s, Haskell computes only the portion of the list that it needs. In Listing 6, the first command loads the function, the second command gets the head (or first) element, and the third command gets the head of the tail (or second element). Haskell computes only the first two elements of the list. The rest is deferred and computed only as needed. This style of lazy processing makes functional languages much more efficient than you'd otherwise expect and allows a powerful abstraction called infinite streams that's not available to other programming languages (see Resources).

The classic Haskell functions that you'll find in most tutorials are recursive math functions, such as Fibonacci functions and factorials. A Fibonacci sequence is defined as the sum of the previous two numbers in a sequence beginning with 1 and 1. So, the first five numbers of a Fibonacci sequence are 1, 1, (1+1) = 2, (1+2) = 3, and (2+3) = 5. The Haskell implementation of this sequence closely resembles the mathematical definition, as in Listing 7:

fib 1 = 1
fib 2 = 1
fib x = fib(x-1) + fib(x-2)

You can type the code in Listing 7 into a file called Fib.hs, load it with :l fib, and run it by typing fib(4) to generate the fourth number of a sequence. Notice I did not need to declare any variables to hold intermediate results. You can see the higher level of abstraction in this example. If your problem set is a good fit for Haskell, that higher abstraction will work for you. If not, the higher abstraction will be more of a curse.

You can think of factorials in much the same way as Fibonacci sequences. A factorial of x is the product of all numbers from 1 to x. In Haskell, you'd define a function to compute factorials, as in Listing 8:

factorial 1 = 1
factorial x = x * factorial(x-1)

Traversing any list works in the same way. To process a list, you process the first node and then process the rest of the list (which itself is a list). Listing 9 shows a recursive function to compute the sum of all elements in a list:

sum [] = 0
sum (h:t) = h + sum(t)

If you haven't seen this pattern before, it takes a little getting used to. The first line says the sum of an empty list is 0. The second line has an idiom that is common across almost all functional languages. (h:t) represents a list as a tuple, with the head of the list (containing the first element) in h and the remainder of the list contained in t. With tail-recursion optimization, this idiom is a marvelously concise way to iterate over a list. Your thought process wonderfully matches your code: do the first, and save the rest for later; when there's nothing left, you're done.

You can traverse much more complex data structures in the same way. With a little more effort, I can express a binary tree -- a tree with each node holding a value and exactly two branches. A simple binary tree in Haskell looks like this:

data Tree a = Null | Node (Tree a) a (Tree a)

In this example, data is a means to build an abstract type. a is a type. You're telling Haskell that a tree is made up of nothing or of a tree, followed by a value, followed by another tree. Each node in the tree has a value, a left child, and a right child. (The children may or may not be null.)

To traverse the tree, your code looks much like the code for traversing a list. You want the sum for a null tree to be null and the sum for a typical node to be the sum of the left tree, plus the sum of the value, plus the sum of the right tree, as shown in Listing 10:

sum_tree :: Tree Integer -> Integer
sum_tree Null = 0
sum_tree (Node left val right) = sum_tree left + val + sum_tree right

In Listing 10, the first line defines the types the function will use. sum_tree :: Tree Integer -> Integer means the function sum_tree will take a Tree of Integers as a parameter and return an Integer. The next two lines of code specify the function. The sum of an empty tree is zero, and the sum of other trees is the sum of the left tree plus the value of the Integer plus the sum of the right tree.

Now you can put it all together in Tree.hs, shown in Listing 11:

data Tree a = Null | Node (Tree a) a (Tree a)

sum_tree :: Tree Integer -> Integer
sum_tree Null = 0
sum_tree (Node left val right) = sum_tree left + val + sum_tree right


t::Tree Integer
t=Node Null 4 Null

In this example, t::Tree Integer binds Tree to a type, and the next line binds t to a value. You can load Listing 11 into Hugs with :l Tree and enter sum_tree t. You can also express more-complex trees, such as Node Null 6 (Node Null 7 Null) for a tree with one right node. Go ahead and experiment by placing different trees into t and running sum_tree again. (Remember, you need to reload the function each time you try.)

Back to top

Revisiting functional "limitations"

Haskell deals with data structures very well. Because you can look at a string as a simple list of characters, not only does Haskell do an excellent job of processing all forms of text, but you can also process trees, sophisticated math, and nested structures effectively. Functional languages are used frequently for building compilers or tools that parse languages because languages are normally expressed as syntax trees. Because you can include functions in the data structures, functional languages make excellent platforms for metaprogramming.

Now that you've seen the basics of a functional language, you can begin to see how you could live with no side effects and only limited support for state. As I mentioned earlier, monads can represent changes in state. But even with monads, managing state is difficult -- so don't try. Instead, think of ways to solve your problems by defining compositions of functions that don't require intermediate state. Instead of thinking in terms of iteration, use recursion or one of the functions -- map, filter, or fold -- that applies an expression to each element of a list. To use a functional language, you just need to let go of imperative programming styles. Learning to write in a more functional style has several benefits:

• You can express ideas in a form that's often more compact.
• By eschewing side effects, you can limit the impact of certain kinds of bugs on your applications.
• By reducing local variables, you can make your code more scalable.

Functional languages can dramatically impact the way you think about programming. For years, MIT programmers used Lisp first because that language was so effective at helping programmers learn to work at a higher level of abstraction.

This article has merely scratched the surface of functional languages. I encourage you to pull down Haskell or another functional language and play with it. My guess is that it will shape the way you think about programming.

Resources

Learn

• Beyond Java (Bruce Tate, O'Reilly, 2005): The author's book about the Java language's rise and plateau and the technologies that could challenge the Java platform in some niches.
  
  
• Haskell: Learn more about this pure functional programming language.
  
  
• Hugs: Hugs is a pure interpreted version of Haskell.
  
  
• The Glasgow Haskell Compiler: GHC is a Haskell implementation with both a compiler and an interpreter. It's perhaps the most prominent implementation.
  
  
• "Yet Another Haskell Tutorial" (Hal Daume III, University of Southern California, 2002-2006): The author leaned on this tutorial extensively for learning Haskell, and by extension, for this article.
  
  
• "A Gentle Introduction to Haskell" (Paul Hudak, John Peterson, and Joseph Fasel, haskell.org, June 2000): Another Haskell tutorial. Don't let the title fool you. It ramps up sharply.
  
  
• Structure and Interpretation of Programs (Hal Abelson, Jerry Sussman, and Julie Sussman, MIT Press, 1984): This book, used in introductory courses at MIT, includes some excellent material on lazy interpretation and infinite streams.
  
  
• Java Concurrency in Practice by Brian Goetz, Tim Peierls, Joshua Bloch, Joseph Bowbeer, David Holmes, and Doug Lea (Addison-Wesley, May 2006): A book defining a new strategy for dealing with concurrency in Java programming.
  
  
• The Java technology zone: Hundreds of articles about every aspect of Java programming.
  
  

Get products and technologies

• Hugs: Download a Hugs implementation from the Haskell site.
  
  

About the author

Bruce Tate is a father, mountain biker, and kayaker in Austin, Texas. He's the author of three best-selling Java books, including the Jolt winner Better, Faster, Lighter Java. He recently released Beyond Java.. He spent 13 years at IBM and is now the founder of the RapidRed consultancy, where he specializes in lightweight development strategies and architectures based on Java technology and Ruby on Rails. 

Rate this article

Comments

Back to top

Table of contents

• Imperative languages and their drawbacks
• Introducing functional programming
• Using Haskell
• Writing functions
• Revisiting functional "limitations"
• Resources
• About the author
• Comments

Dig deeper into Java on developerWorks

IBM SmartCloud trial. No charge.

Unleash the power of hybrid cloud computing today!

---

Public and private solutions in one trial.

Special offers