8.3 Day 2: Spock’s Great Strength

With some characters, you might not notice their best qualities for quite some time. With Spock, it’s easy to grasp his great strengths. He’s brilliant, always logical, and completely predictable. Haskell’s great strength is also that predictability and simplicity of logic. Many universities teach Haskell in the context of reasoning about programs. Haskell makes creating proofs for correctness far easier than imperative counterparts. In this section, we’ll dig into the practical concepts that lead to better predictability. We will start with higher-order functions. Then, we’ll talk about Haskell’s strategy for combining them. That will take us into partially applied functions and currying. We’ll finally look at lazy computation. It’s going to be a full day, so let’s get started.

Higher-Order Functions

Every language in this book addresses the idea of higher-order programming. Haskell depends on the concept extensively. We will work quickly through anonymous functions and then apply them with the many prebuilt functions that work on lists. I will move much faster than I have with the other languages, because you’ve seen the concepts before, and there’s so much ground to cover. We’ll start things with anonymous functions.

Anonymous Functions

As you might expect, anonymous functions in Haskell have a ridiculously simple syntax. The form is (\param1 .. paramn -> function_body). Try it, like this:

Taken alone, they don’t add much. Combined with other functions, they become extremely powerful.

map and where

First, we built an anonymous function that just returns the first parameter. Next, we append a string. As you’ve seen in other languages, anonymous functions are an important feature for list libraries. Haskell has a map:

We’re applying the map function to an anonymous function and a list. map applies the anonymous function to each item in the list and collects the results. There’s no surprise here, but that form might be a bit much to digest all at once. We can package it all up as a function and break out the anonymous function as a locally scoped function, like this:

We’ve declared a function called squareAll that takes a parameter called list. Next, we use map to apply a function called square to all the items in list. Then, we use a new feature, called where, to declare a local version of square. You don’t have to bind functions with where; you can also bind any variable. We’ll see some examples of where throughout the rest of the chapter. Here’s the result:

You can also use map with part of a function, called a section, like this:

(+ 1) is actually a partially applied function. The + function takes two parameters, and we’ve supplied only one. The result is that we get a function like (x + 1), with a single parameter x.

filter, foldl, foldr

The next common function is filter, which applies a test to items in a list, like this:

You can also fold left and right, just as you did in Clojure and Scala. The functions you will use are variations of foldl and foldr:

We took an initial carry-over value of 0 and then applied the function to every item in the list, using the result of the function as the carryOver argument and each item of the list as the other. Another form of fold is convenient when you are folding with an operator:

This is using the + operator as a pure function taking two parameters and returning an integer. The result gives you the same thing as evaluating this:

You can also fold right to left, with foldr1.

As you might imagine, Haskell offers many other functions in the library of list functions, and many of them use higher-order functions. Rather than spend a whole chapter on dealing with them, I’ll let you do your own discovery. Now, I want to move on to the ways Haskell combines functions to work together.

Partially Applied Functions and Currying

We’ve talked briefly about function composition and partially applied functions. These concepts are important and central enough to Haskell that we should spend a little more time here.

Every function in Haskell has one parameter. You might ask yourself, “If that’s true, how could you write a function like + that adds two numbers together?”

In fact, it is true. Every function does have one parameter. To simplify the type syntax, let’s create a function called prod:

We created a function, and you can see that it works. Let’s get the type of the function:

The portion Num a => means “In the following type definition, a is a type of Num.” You’ve seen the rest before, and I lied to you about the meaning to simplify things. Now, it’s time to set the record straight. Haskell uses a concept to split one function on multiple arguments into multiple functions, each with one argument. Haskell does this job with partial application.

Don’t let the term confuse you. Partial application binds some of the arguments, but not all. For example, we can partially apply prod to create some other functions:

Look at the left side of these functions first. We defined prod with two parameters, but we applied only the first one. So, computing prod 2 is easy, Just take the original function of prod x y = x * y, substitute 2 for x, and you have prod y = 2 * y. The functions work just as you’d expect:

So, the mystery is solved. When Haskell computes prod 2 4, it is really computing (prod 2) 4, like this:

• First, apply prod 2. That returns the function (\y -> 2 * y).

• Next, apply (\y -> 2 * y) 4, or 2 * 4, giving you 8.

That process is called currying, and just about every multiple-argument function in Haskell gets curried. That leads to greater flexibility and simpler syntax. Most of the time, you don’t really have to think about it, because the value of curried and uncurried functions is equivalent.

Lazy Evaluation

Like Clojure’s sequence library, Haskell makes extensive use of lazy evaluation. With it, you can build functions that return infinite lists. Often, you’ll use list construction to form an infinite list. Take this example that builds an infinite range, starting at x, in steps of y:

The syntax is strange, but the overall effect is beautiful. We’re building a function called myRange, taking a starting point and a step for our range. We use list composition to build a list with start as the head and (myRange (start + step) step) as the tail. These are the successive evaluations for myRange 1 1:

• 1:myRange (2 1)

• 1:2:myRange (3 1)

• 1:2:3:myRange (4 1)

...and so on.

This recursion will go on infinitely, so we’ll typically use the function with others that will limit the recursion. Make sure you load my_range.hs first:

Some recursive functions work more efficiently using list construction. Here’s an example of the Fibonacci sequence, using lazy evaluation with composition:

The first function builds a sequence where every number is the sum of the previous two. We effectively have a sequence, but we can improve on the API. To be a proper Fibonacci sequence, we must start the sequence with 1 and 1, so fib seeds lazyFib with the first two numbers. Finally, we have one more helper function that allows the user to grab just one number of the sequence with drop and take. Here are the functions in action:

The three functions are beautiful and concise. We define an infinite sequence, and Haskell computes only the part necessary to do the job. You can really start to have fun when you start to combine infinite sequences together. First, let’s add two Fibonacci sequences together, offset by one:

Surprise. We get a Fibonacci sequence. These higher-order functions play well together. We called zipWith, which pairs each item of the infinite list by index. We passed it the + function. Or, we could double a range:

We’re using map to apply the partially applied function * 2 to the infinite range [1 ..], and then we’re using the infinite range, beginning with 1.

The nice thing about functional languages is that you can compose them in unexpected ways. For example, we can use function composition in conjunction with partially applied functions and lazy sequences effortlessly:

That code packs a punch, so let’s take it apart. Starting from the inside and working out, we first have (* 5). That’s a partially applied function. Whatever we pass into the function will be multiplied by five. We pass that result into another partially applied function, (* 2). We pass that composed function into map and apply the function to every element in the infinite fib sequence. We pass that infinite result to take 5 and generate the first five elements of a Fibonacci sequence, multiplied by five and then again by 2.

You can easily see how you’d compose the solutions to problems. You just pass one function to the next. In Haskell, f . g x is shorthand for f(g x). When you’re building functions in this way, you might want to apply them from first to last. You’d do so with the . operator. For example, to invert an image, flip it vertically and then flip it horizontally, an image processor might do something like (flipHorizontally . flipVertically . invert) image.

An Interview with Simon Peyton-Jones

To take a quick break, let’s hear from another person on the committee that created Haskell. Simon Peyton Jones spent seven years as a lecturer at University College London and nine years as a professor at Glasgow University, before moving to Microsoft Research (Cambridge) in 1998 where his research focus is the implementation and application of functional programming languages for uniprocessor and parallel machines. He is the lead designer of the compiler used in this book.

Bruce Tate:

Tell me about the creation of Haskell.

Simon Peyton-Jones:

A very unusual thing about Haskell is that it is a successful committee language. Think of any successful language, and the chances are that it was originally developed by one person or a very small team. Haskell is different: it was originally designed by an international group of twentyish researchers. We had enough agreement about the core principles of the language—and Haskell is a very principled language—to keep the design coherent.

Also, Haskell is enjoying a substantial upsurge in popularity some twenty years after it was designed. Languages usually succeed or (mostly) fail in the first few years of their lives, so what is going on? I believe that it is because Haskell’s principled adherence to purity, the absence of side effects, is an unfamiliar discipline that has prevented Haskell from being a mainstream language. Those long-term benefits are gradually becoming apparent. Whether or not the mainstream languages of the future look like Haskell, I believe they will have strong mechanisms for controlling side effects.

Bruce Tate:

What are the things you like about it the most?

Simon Peyton-Jones:

Apart from purity, probably the most unusual and interesting feature of Haskell is its type system. Static types are by far the most widely used program verification technique available today: millions of programmers write types (which are just partial specifications) every day, and compilers check them every time they compile the program. Types are the UML of functional programming: a design language that forms an intimate and permanent part of the program.

From day 1 Haskell’s type system was unusually expressive, mainly because of type classes and higher-kinded type variables. Since then, Haskell has served as a laboratory in which to explore new type system ideas, something I have enjoyed very much. Multiparameter type classes, higher-rank types, first-class polymorphism, implicit parameters, GADTs, and type families...we are having fun! And, more importantly, we are extending the range of properties that can be statically checked by the type system.

Bruce Tate:

What are the things you’d change if you had it to do all over again?

Simon Peyton-Jones:

I’d like a better record system. There are reasons that Haskell’s record system is so simple, but it’s still a weak point.

I’d like a better module system. Specifically, I want to be able to ship a Haskell package P to someone else, saying “P needs to import interfaces I and J from somewhere: you provide them, and it will offer interface K.” Haskell has no formal way to say this.

Bruce Tate:

What’s the most interesting problem you’ve seen solved with Haskell?

Simon Peyton-Jones:

Haskell is a truly general-purpose programming language, which is a strength but also a weakness because it has no single “killer app.” That said, it is quite common to find that Haskell is a medium in which people have been able to dream up particularly elegant and unusual ways to solve problems. Look at Conal Elliot’s work on functional reactive animation, for example, which rewired my brain by making me think of a “time-varying value” as a single value that could be manipulated by a functional program. On a more mundane (but very useful) level, there are lots of libraries of parser and pretty-printing combinators, each encapsulating great intellectual cleverness behind simple interfaces. In a third domain, Jean-Marc Eber showed me how to design a combinatory library to describe financial derivatives, something I would never have thought of on my own.

In each case, the medium (Haskell) has allowed a new level of expressiveness that would be much harder to achieve in a mainstream language.

By now, you have enough knowledge to tackle some hard problems in Haskell, but you can’t do some easy stuff, such as dealing with I/O, state, and error handling. These problems will take us into some advanced theory. On day 3, we’ll look into monads.

What We Learned in Day 2

In day 2, we looked at higher-order functions. We started with the same kinds of list libraries that you’ve seen in almost every language in this book. You saw map, several versions of fold, and some additional functions like zip and zipWith. After working with them on fixed lists, we then worked with some lazy techniques such as the ones you used with Clojure.

As we worked through advanced functions, we learned to take a function and apply some of the parameters. This technique was called partially applied functions. Then, we used partially applied functions to translate a function that took multiple arguments at once (f (x, y)) to a function that took arguments one at a time (f(x)(y)). We learned that in Haskell, all functions are curried, which explained the type signatures of Haskell functions taking multiple arguments. For example, the type signature of the function f x y = x + y is f :: (Num a) => a -> a -> a.

We also learned function composition, a process that used the return from one function as the input of another. We could effectively string functions together this way.

Finally, we worked with lazy evaluation. We were able to define functions that built infinite lists, which would be processed on demand. We defined a Fibonacci sequence in this way and also used composition with lazy sequences to effortlessly produce new lazy sequences.

Day 2 Self-Study

Find:

• Functions that you can use on lists, strings, or tuples

• A way to sort lists

Do:

• Write a sort that takes a list and returns a sorted list.

• Write a sort that takes a list and a function that compares its two arguments and then returns a sorted list.

• Write a Haskell function to convert a string to a number. The string should be in the form of $2,345,678.99 and can possibly have leading zeros.

• Write a function that takes an argument x and returns a lazy sequence that has every third number, starting with x. Then, write a function that includes every fifth number, beginning with y. Combine these functions through composition to return every eighth number, beginning with x + y.

• Use a partially applied function to define a function that will return half of a number and another that will append \n to the end of any string.

Here are some more demanding problems if you’re looking for something even more interesting:

• Write a function to determine the greatest common denominator of two integers.

• Create a lazy sequence of prime numbers.

• Break a long string into individual lines at proper word boundaries.

• Add line numbers to the previous exercise.

• To the above exercise, add functions to left, right, and fully justify the text with spaces (making both margins straight).