Getting Started with Haskell

You can implement this function using either an if expression or a guard. We’ll look at both solutions, starting with the solution that uses an if expression.

The first thing we need to do is write our function and define our base case. We’ll leave the rest of the function undefined for the moment:

factorial n =
  if n <= 1
  then 1
  else undefined

Technically speaking, factorial is only defined for positive numbers. We haven’t yet learned how to prevent users from passing in negative numbers, so we’ll fall back to defensive programming practices and just check for any number less than or equal to one. If our number is small enough, we’ll return the smallest factorial number: one.

What about for a larger factorial? In that case we need to multiply the current number by the next smallest factorial. What’s the value of the next smallest factorial? We can find it out using the factorial function:

factorial n =
  if n <= 1
  then 1
  else n * factorial (n - 1)

As you can see in this example, the “next smallest factorial” is our recursive call to factorial with the next smallest value, n - 1.

If you prefer guards, you’ll notice that the implementation with them is nearly identical:

factorial n
  | n <= 1 = 1
  | otherwise = n * factorial (n - 1)

You can implement the fibonacci function using either if expressions or guards. We’ll use guards in this solution.

The definition of fibonacci is similar to the factorial that you should have created in the previous exercise. Let’s take a look:

fibonacci n
  | n <= 0 = 0
  | n == 1 = 1
  | otherwise = fibonacci (n - 1) + fibonacci (n - 2)

Once again, you’ll notice that we’re being a bit generous with our smallest base case. We’re checking for numbers less than or equal to zero so that we can give a sensible answer even if the user passes in a negative number.

In the next base case, we check to see if our value is 1. If so, we just return 1. These two base cases let use get the sequence started with the first two numbers:

fibonacci 0 = 0
fibonacci 1 = 1

In the next step, n is 2. This is a recursive case, and we’re going to look back both one step to n = 1 and two steps to n = 0:

fibonacci 2 = fibonacci (2 - 1) + fibonacci (2 - 2)
            = fibonacci 1 + fibonacci 0
            = 1 + 1
            = 1

Let’s follow up one more time, just to make sure we have the pattern down.

fibonacci 3 = fibonacci (3 - 1) + fibonacci (3 - 2)
            = fibonacci 2 + fibonacci 1
            = (fibonacci (2 - 1) + fibonacci (2 - 2)) + 1
            = (fibonacci 1 + fibonacci 0) + 1
            = (1 + 0) + 1
            = 1 + 1
            = 2

Remember, when you’re working with recursive functions, try to walk through the recursion manually if you’re having trouble understanding how the function works.

Let’s start by defining our own version of curry called exampleCurry. Our function will need to take three arguments:

• f is a function that takes in a tuple and returns a value
• a is a value; it’s the first value in the tuple we’ll pass to f
• b is a value; it’s the second value in the tuple we’ll pass to f

It’s easiest to write this function as a one-liner:

exampleCurry f a b = f (a,b)

In this code, we’re taking three arguments as input. We’re calling our first argument, the function we want to curry, using a tuple made up of the next two arguments.

If we use this function in ghci we can see it behaves like you’d expect:

λ addTuple tuple = fst tuple + snd tuple
λ exampleCurry addTuple 1 2
3

Just like with the curry function defined for us in Prelude, we can use exampleCurry to create a new function:

λ addTwo = exampleCurry addTuple
λ addTwo 1 2
3
λ addTwo 2 3
5

This might be a bit surprising, since you’re still getting used to Haskell. Remember that Haskell makes it easy for us to do partial application. We could have written addTwo without partial application by taking in the two arguments that we should call the curried function with:

λ addTwo a b = exampleCurry addTuple a b
λ addTwo 1 2
3
λ addTwo 2 3
5