8.2 Day 1: Logical

Like Spock, you’ll find that Haskell’s core concepts are easy to grasp. You’ll work strictly with defining functions. Given the same input parameters, you’ll get the same output parameters, every time. I’m going to use GHC, or the Glasgow Haskell Compiler, version 6.12.1. It’s widely available across many platforms, but you can find other implementations as well. As always, I’m going to start in the console. Type ghci:

You’ll see Haskell load a few packages, and then you’re ready to type commands.

Expressions and Primitive Types

We’re going to talk about Haskell’s type system a little later. In this section, we’ll focus on using primitive types. As with many of the other languages, we’ll start with numbers and some simple expressions. We’ll move quickly into more advanced types such as functions.

Numbers

By now, you know the drill. Type a few expressions:

Order of operations works just about like you’d expect:

Notice you can group operations with parentheses. You’ve seen a couple of types of numbers. Let’s look at some character data.

Character Data

Strings are represented with double quotes, like this:

Notice that you’ll concatenate with ++ instead of +. You can represent single characters like this:

Notice that a string is just a list of characters. Let’s briefly look at some boolean values.

Booleans

A boolean is another primitive type that works much as they do in most of the other infix notation languages in this book. These are equal and not-equal expressions, returning booleans:

Try an if/then statement:

That’s the first major departure from other languages in the book. In Haskell, indentation is significant. Haskell is guessing that there’s a follow-up line that is not indented correctly. We’ll see some indented structures later. We won’t talk about layouts, which control indentation patterns; follow predictable indentation strategies that mimic what you see here, and you will be OK. Let’s do a full if/then/else statement:

In Haskell, if is a function, not a control structure, meaning it returns a value just like any other function. Let’s try a few true/false values:

Haskell is strongly typed. if takes strictly boolean types. Let’s try to force another type collision:

This error message gives us the first glimpse into Haskell’s type system. It says “There is no function called + that takes a Num argument followed by [Char], a list of characters.” Notice that we haven’t told Haskell what types things are. The language is inferring types based on clues. At any point, you can see what Haskell’s type inference is doing. You can use :t, or you can turn on the :t option that does something similar, like this:

Now, after every expression, you can see the type that each expression returns. Let me warn you that using :t with numbers is confusing. That has to do with the interplay between numbers and the console. Try to use the :t function:

That is not the same as the type we got before, it :: Integer. The console will try to treat numbers as generically as possible, unless you have done a :set t. Rather than a pure type, you get a class, which is a description of a bunch of similar types. We’ll learn more in ​Classes​.

Functions

The centerpiece of the whole Haskell programming paradigm is the function. Since Haskell has strong, static typing, you’ll specify each function in two parts: an optional type specification and the implementation. We’re going to go quickly through concepts you’ve seen in other languages, so hang on tight.

Defining Basic Functions

A Haskell function traditionally has two parts: the type declaration and the function declaration.

Initially, we’re going to be defining functions within the console. We’ll use the let function to bind values to implementations. Before defining a function, try let. As with Lisp, in Haskell, let binds a variable to a function in a local scope.

When you’re coding a Haskell module, you’ll declare functions like this:

In the console, though, we’ll use let to assign the function in local scope, so we can use it. Here’s an example of a simple double function:

At this point, we’ll switch to using files with programs. We can then work with multiline definitions. Using GHC, the full double definition would look like this:

Notice that we added a module called Main. In Haskell, modules collect related code into a similar scope. The Main module is special. It is the top-level module. Focus on the double function for now. Load Main into the console, and use it like this:

So far, we haven’t enforced a type. Haskell is being forgiving by inferring a type for us. There’s definitely an underlying type definition for each function. Here’s an example of a definition with a type definition:

And we can load it and use it as before:

You can see the associated type of the new function:

This definition means that the function double takes an Integer argument (the first Integer) and returns an Integer.

This type definition is limited. If you went back to the earlier, typeless version of double, you’d see something else entirely:

Now, that’s different! In this case, a is a type variable. The definition means “The function double takes a single argument of some type a and returns a value of that same type a.” With this improved definition, we can use this function with any type that supports the + function. Let’s start to crank up the power. Let’s look at implementing something slightly more interesting, a factorial.

Recursion

Let’s start with a little recursion. Here’s a recursive one-liner that implements a factorial within the console:

That’s a start. The factorial of x is 1 if x is 0, and it’s fact (x - 1) * x otherwise. We can do a little better by introducing pattern matching. Actually, this syntax looks and acts a lot like Erlang’s pattern matching:

The definition has three lines. The first declares the type of the argument and return value. The next two are different functional definitions that depend on the pattern match of the inbound arguments. factorial of 0 is 1, and factorial of n is factorial x = x * factorial (x - 1). That definition looks exactly like the mathematical definition. In this case, the order of the patterns is important. Haskell will take the first match. If you wanted to reverse the order, you’d have to use a guard. In Haskell, guards are conditions that restrict the value of the arguments, like this:

In this case, the guards have boolean values on the left and the function to apply on the right. When a guard is satisfied, Haskell calls the appropriate function. Guards often replace pattern matching, and we’re using it to initiate the base condition for our recursion.

Tuples and Lists

As you’ve seen in other languages, Haskell depends on tail-recursion optimization to efficiently deal with recursion. Let’s see several versions of a Fibonacci sequence with Haskell. First, we’ll see a simple case:

That’s simple enough. fib 0 or fib 1 is 1, and fib x is fib (x - 1) + fib (x - 2). But that solution is inefficient. Let’s build a more efficient solution.

Programming with Tuples

We can use tuples to provide a more efficient implementation. A tuple is a collection of a fixed number of items. Tuples in Haskell are comma-separated items in parentheses. This implementation creates a tuple with consecutive Fibonacci numbers and uses a counter to assist in recursion. Here’s the base solution:

fibTuple takes a three-tuple and returns a three-tuple. Be careful here. A single parameter that is a three-tuple is not the same as taking three parameters. To use the function, we’ll start recursion with two numbers, 0 and 1. We will also provide a counter. As the counter counts down, the first two numbers get successively larger numbers in the sequence. Successive calls to fibTuple (0, 1, 4) would look like this:

• fibTuple (0, 1, 4)

• fibTuple (1, 1, 3)

• fibTuple (1, 2, 2)

• fibTuple (2, 3, 1)

• fibTuple (3, 5, 0)

You can run the program, like this:

The answer will be in the first position. We can grab the answer like this:

We just use pattern matching to grab the first position. We can simplify the usage model like this:

That function uses the two helper functions to build a quite fast Fibonacci generator. Here is the whole program together:

And here are the results (which appear instantaneously):

Let’s try another approach with function composition.

Using Tuples and Composition

Sometimes, you need to combine functions by chaining them together by passing the results of one function to another. Here’s an example that computes the second item of a list by matching the head of the tail of a list:

We’re just defining a function in the console. second = head . tail is equivalent to second lst = head (tail lst). We’re feeding the result of one function into another. Let’s use this feature with yet another Fibonacci sequence. We’ll compute a single pair, as before, but without a counter:

Given two numbers in the sequence, we can always compute the next one. The next job is to recursively compute the next item in the sequence:

The base case is the value (1, 1) for an n of 1. From there, it is simple. We just compute the next item of the sequence based on the last one. We can get any pair in the sequence:

Now, all that remains is to match the first item of each pair and combine them into a sequence. We’ll use a convenient function composition of fst to grab the first element and fibNthPair to build a pair:

Said another way, we take the first element of the nth tuple. And we’re done. With a little work done for tuples, let’s solve a few problems with lists.

Traversing Lists

You’ve seenlists in many different languages. I’m not going to fully rehash them, but I will go over a basic recursion example and then introduce a few functions you haven’t seen yet. Breaking a list into the head and tail can work in any binding, like a let statement or a pattern match:

We’re binding the list [1, 2, 3, 4] to (h:t). Think of this construct as the various head|tail constructs you’ve seen in Prolog, Erlang, and Scala. With this tool, we can do a few simple recursive definitions. Here are size and prod functions for a list:

I’m going to use Haskell’s type inference to handle the types of these functions, but the intention is clear. The size of a list is 1 + the size of a tail.

zip is a powerful way to combine lists. Here’s the function in action:

So, we built a tuple of the two items. You can also zip lists together, like this:

It combines the nth elements of each of the lists into a tuple.

So far, the features you’ve seen in Haskell have been remarkably similar to those covered in other languages. Now, we’ll start working with some more advanced constructs. We’ll look at advanced lists including ranges and list comprehensions.

Generating Lists

We’ve already looked at a few ways to process lists with recursion. In this section, we’ll look at a few options for generating new lists. In particular, we’ll look at recursion, ranges, and list comprehensions.

Recursion

The most basic building block for list construction is the : operator, which combines a head and tail to make a list. You’ve seen the operator in reverse used in pattern matching as we call a recursive function. Here’s : on the left side of a let:

We can also use : to do construction, instead of deconstruction.

Here’s how that might look:

Remember, lists are homogeneous. You can’t add a list to a list of integers, for example:

You could, however, add a list to a list of lists or even an empty list:

Here’s list construction in action. Let’s say we wanted to create a function that returns the even numbers from a list. One way to write that function is with list construction:

Our function takes a list of integers and returns a list of even integers. allEven for an empty list is an empty list. If there is a list, if the head is even, we add the head to allEven applied to the tail. If the head is odd, we discard it by applying allEven to the tail. No problem. Let’s look at some other ways to build lists.

Ranges and Composition

As with Ruby and Scala, Haskell includes first-class ranges and some syntactic sugar to support them. Haskell provides a simple form, consisting of the end points of a range:

You specify the endpoints, and Haskell computes the range. The default increment is 1. What if Haskell can’t reach the endpoint with the default increment?

You’ll get an empty list. You can specify an increment by specifying the next item in the list:

You can also work in fractional numbers:

Ranges are syntactic sugar for creating sequences. The sequences need not be bound. As with Clojure, you can take some of the elements of a sequence:

We’ll talk more about lazy sequence in day 2. For now, let’s look at another way to automatically generate lists, the list comprehension.

List Comprehensions

We first looked at list comprehensions in the Erlang chapter. In Haskell, a list comprehension works the same way. On the left side, you’ll see an expression. On the right side, you’ll see generators and filters, just as you did with Erlang. Let’s look at a few examples. To double all items in a list, we do this:

In English, the list comprehension means “Collect x * 2 where x is taken from the list [1, 2, 3].”

As with Erlang, we can also use pattern matching within our list comprehensions. Say we had a list of points representing a polygon and wanted to flip the polygon diagonally. We could just transpose x and y, like this:

Or, to flip the polygon horizontally, we could subtract x from 4, like this:

We can also compute combinations. Let’s say we wanted to find all of the possible landing parties of two taken from a crew of Kirk, Spock, or McCoy:

That composition almost worked but did not remove duplicates. We can add conditions to filter the list comprehension like this:

That is a little better, but order doesn’t matter. We can do a little better by including only the options that appear in sorted order, discarding the rest:

With a short, simple list comprehension, we have the answer. List comprehensions are a great tool for rapidly building and transforming lists.

An Interview with Philip Wadler

Now that you’ve seen some of the core features of Haskell, let’s see what someone from the committee that designed Haskell has to say. A theoretical computer science professor at the University of Edinburgh, Philip Wadler is an active contributor of not only Haskell but also Java and XQuery. Previously, he worked or studied at Avaya Labs, Bell Labs, Glasgow, Chalmers, Oxford, CMU, Xerox Parc, and Stanford.

Bruce Tate:

Why did your team create Haskell?

Philip Wadler:

In the late 1980s there were a large number of different groups creating designs and implementations of functional languages, and we realized we would be stronger working together than apart. The original goals were not modest: we wanted the language to be a foundation for research, suitable for teaching, and up to industrial uses. The entire history is covered in detail in a paper we wrote for the History of Programming Languages conference, which you can find on the Web.[26]

Bruce Tate:

What are the things you like about it the most?

Philip Wadler:

I really enjoy programming with list comprehensions. It’s nice to see that they’ve finally made their way into other languages, like Python.

Type classes provide a simple form of generic programming. You define a data type, and just by adding one keyword, derived, you can get routines to compare values, to convert values to and from strings, and so on. I find that very convenient and miss it when I’m using other languages.

Any good programming language really becomes a means of extending itself to embed other programming languages specialized to the task at hand. Haskell is particularly good as a tool for embedding other languages. Laziness, lambda expressions, monad and arrow notation, type classes, the expressive type system, and template Haskell all support extending the language in various ways.

Bruce Tate:

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

Philip Wadler:

With distribution becoming so important, we need to focus on programs that run on multiple machines, sending values from one to the other. When you send a value, you probably want it to be the value itself (eager evaluation), rather than a program (and the values of all the free variables of the program) that can be evaluated to yield the value. So, in the distributed world, I think it would be better to be eager by default but make it easy to be lazy when you want.

Bruce Tate:

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

Philip Wadler:

I’m always blown away by the uses folks find for Haskell. I remember years ago being amazed at uses of Haskell for natural-language processing and years after that when it was used for protein folding with an application to fighting AIDS. I just had a look at the Haskell Community page, and it lists forty industrial applications of Haskell. There are now many users in finance: ABN Amro, Credit Suisse, Deutsche Bank, and Standard Chartered. Facebook uses Haskell for an in-house tool to update code in PHP. One of my favorites is the use of Haskell for garbage collection—not the kind we do in software but real garbage collection...programming engines to be used in garbage trucks!

What We Learned in Day 1

Haskell is a functional programming language. Its first distinguishing characteristic is that it is a pure functional language. A function with the same arguments will always produce the same result. There are no side effects. We spent most of day 1 covering features you have seen in other languages in this book.

We first covered basic expressions and simple data types. Since there are no mutable variable assignments, we used recursion to define some simple math functions and to deal with lists. We worked with basic Haskell expressions and rolled those up into functions. We saw pattern matching and guards as we found in Erlang and Scala. We used lists and tuples as the basic collections as you found in Erlang.

Finally, we took a look at building lists that took us into list comprehensions, ranges, and even lazy sequences. Let’s put some of those ideas into practice.

Day 1 Self-Study

By this time, writing functional programs should be getting easier if you’ve been working through all of the other functional languages. In this section, I’m going to push you a little harder.

Find:

• The Haskell wiki

• A Haskell online group supporting your compiler of choice

Do:

• How many different ways can you find to write allEven?

• Write a function that takes a list and returns the same list in reverse.

• Write a function that builds two-tuples with all possible combinations of two of the colors black, white, blue, yellow, and red. Note that you should include only one of (black, blue) and (blue, black).

• Write a list comprehension to build a childhood multiplication table. The table would be a list of three-tuples where the first two are integers from 1--12 and the third is the product of the first two.

• Solve the map-coloring problem (​Map Coloring​) using Haskell.