Cover by Donald Bruce Stewart, Bryan O'Sullivan, John Goerzen

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

O'Reilly logo

Taking Advantage of Functions as Data

In an imperative language, appending two lists is cheap and easy. Here’s a simple C structure in which we maintain a pointer to the head and tail of a list:

struct list {
    struct node *head, *tail;
};

When we have one list and want to append another list onto its end, we modify the last node of the existing list to point to its head node, and then update its tail pointer to point to its tail node.

Obviously, this approach is off limits to us in Haskell if we want to stay pure. Since pure data is immutable, we can’t go around modifying lists in place. Haskell’s (++) operator appends two lists by creating a new one:

-- file: ch13/Append.hs
(++) :: [a] -> [a] -> [a]
(x:xs) ++ ys = x : xs ++ ys
_      ++ ys = ys

From inspecting the code, we can see that the cost of creating a new list depends on the length of the initial one.[34]

We often need to append lists over and over in order to construct one big list. For instance, we might be generating the contents of a web page as a String, emitting a chunk at a time as we traverse some data structure. Each time we have a chunk of markup to add to the page, we will naturally want to append it onto the end of our existing String.

If a single append has a cost proportional to the length of the initial list, and each repeated append makes the initial list longer, we end up in an unhappy situation: the cost of all of the repeated appends is proportional to the square of the length of the final list.

To understand this, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required