CS 214: Programming Languages
Spring 2009

Home|Syllabus|Schedule
<<|>>|Haskell templates

Simple Haskell Functions
Haskell, Iteration 2

For this Haskell iteration, you'll be writing some more factorial functions.

Do all of your work in languages/haskell/factorial.

Pattern Matching

You already have this definition in Factorial.hs:

factorial 0 = 1
factorial n = n * factorial (n-1)

Open up any mathematics book that contains a definition of factorial, and it'll look nearly identical to this.

You're using a very basic, numeric pattern matching here. The first definition says that if factorial is called with the argument 0, then the result should be 1. When that doesn't match, the alternative is tried, and since n will match any number, it's triggered, and no matter patterns are needed.

Let's rewrite this with a more interesting pattern. But first, write some tests.

In FactorialTest.hs, write tests for factorial2. (That is, create a variable factorial2Tests which makes all the same assertions as factorialTests, but using factorial2 instead of factorial. Add factorial2Tests to the main function.)

Compile the code, and see the compiler error.

Get rid of the compilation error with a dummy definition to make sure the tests are being run.

Define factorial2 n = 0.

Compile the code, and run for a red bar.

Try this definition of factorial2:

factorial2 0     = 1
factorial2 (n+1) = (n+1) * factorial2 n

Enter this definition into the Factorial module, compile, and run the tests for a green bar.

In this case, there's perhaps little reason to write it this way since you have to use (n+1) on the right hand side, but in some cases this ability to match a computation is kind of nice.

When you start using interesting data structures, this pattern matching will become really nice.

Boring If Expression

In just about any other language, you'd write the factorial computation using an if expression or statement. Haskell has one.

  1. Write tests for factorialIf. Compile for an error.
  2. Write a dummy definition for factorialIf. Compile, and red bar.

Since there's no pattern matching to do, you'll just need factorialIf n as the functions signature. You just need to know the syntax of an if expression.

Read the brief "if Expressions" section at WikiBooks.

Have you noticed that not once have you ever explicitly returned a value from a Haskell function? That's because returning a value is the default action. (In fact, return is a function for a very special context.) That's why I keep calling it an "if expression".

Now the definition can fit on one line:

factorialIf n = if n == 0 then 1 else n * factorialIf (n-1)

If you want to add some line breaks, feel free. (But follow the indenting suggestions of the WikiBook.)

Write a good definition of factorialIf, compile, and green bar.

Guards

Other languages also have guards (like Perl and Ruby), but they usually employ keywords like if and unless and they come at the end of an expression. In Haskell, a guard is always part of the declaration and is an implicit if.

A guard is a boolean expression which works a little bit like pattern matching in Haskell.

  1. Write tests for factorialGuards. Compile for an error.
  2. Write a dummy definition for factorialGuards. Compile, and red bar.

Get an idea what they're about:

Read the section "Guards".

Here's what I came up with using guards:

factorialGuards n
  | n == 0     = 1
  | otherwise  = n * factorialGuards (n-1)

Define factorialGuards, compile, and green bar.

So, Which One's Best?

As best I can tell (and infer), there's no performance advantage one way or the other with any of these styles. It mostly comes down to what version is the most expressive. I'd expect to see an implementation of a function like factorial written like factorial or factorialGuards. If you have a computation that can be broken down this same way, those are the styles I'd look at first.

And if performance were really an issue, we'd use this definition:

factorial n = product [1..n]

This is very fast for reasons that we'll explore later. But it demonstrates something important about Haskell. Functional programming has this rap for being all about recursive programming. That's the least of its powers. It's true power comes from functional composition and treating functions as first-class objects. When you use a language the way it was intended, you (hopefully) get code that's easier to read and executes faster.