CSE 320: Programming Languages @ CSU, San Bernardino

Go back to home page

Lab #1: Functions

This lab is intended to introduce you to the Haskell programming language, and to some key ideas about the structuring of data, and the power of functions. This lab is intended to be completable within two hours of lab time, and the products of this lab must be submitted for review and credit before the end of that time.

If at any point you find something confusing, feel free to ask questions about it.

Introduction

Haskell is a “functional” programming language. There is some disagreement about what exactly this means, but there are a few criteria we can use to understand the term. Functional languages:

  • Tend to focus on functions as the basic unit of program construction.
  • Tend to prefer the elimination of explicitly managed program state.

Haskell fits both of these definitions, and so we call it a functional programming language. This is not terribly important, as every language even within a particular programming paradigm will do things in its own way, but it does help us to communicate at least a basic sense of what to expect when you hear the term used.

Basic Haskell Types

Haskell comes equipped with a collection of standard types, which are similar to the types you would expect to get from other programming languages. They are:

  • Bool, which can be False or True (this is case-sensitive, and we’ll get to why they’re capitalized later in this lab).
  • Char, which represents a single Unicode code points (“code point” is a very specific term from the Unicode standard. For our purposes, we’ll pretend it’s equivalent to “character,” although this isn’t exactly accurate. Feel free to read more on your own.)
  • String, which is an alias for [Char] (meaning a list of Chars). String is the basic text type in Haskell, written "like so", and it’s what we’ll use for our programs. Note that String is not a particularly good string representation, and that there are other types which should be used in real Haskell programs.
  • Lists, which you’ve just seen, written [1, 2, 3, 4]. They can contain any number of items of the same type.
  • Tuples, which are written like so: ('a', "Hello", 5). They can contain any number of items of different types.
  • Unit, or the empty tuple, written (). This is often used in Haskell to mean “no type.”
  • Integer, for arbitrary-precision integers. This means the Integer type can represent all integers, no matter how big they are.
  • Int, for fixed-precision integers of width [-2^(229), 2^(229 - 1)].
  • Float, for single-precision floating point numbers.
  • Double, for double-precision floating point numbers.

To try out these types, open the Glasgow Haskell Compiler Interpreter with the ghci command, and try some basic operations with these types. Feel free to ask questions, and experiment with operations on different types together. See what sort of messages you get from the compiler.

How to Define a Function

Functions in Haskell are defined like so:

addTwo x = x + 2

This defines a function that takes in a number, adds two to it, and returns the result.

Haskell can automatically determine (“infer”) almost all types in a program, but it is considered good practice to write the types of functions anyway. This is done like so:

addTwo :: Integer -> Integer
addTwo x = x + 2

This syntax may seem weird, but it means that addTwo is a function taking in a single value of type Integer, and returning a value of type Integer.

A more complex function may look like this:

addSomething :: Integer -> Integer -> Integer
addSomething x n = x + n

Notice that Haskell’s syntax makes no distinction between input types and outputs types, other than position. This is very important for understanding how Haskell works.

Currying

Currying is the idea that every function with multiple inputs can be turned into a series of functions with one input each. Take for example the following C++ code:

int doSomeMath(int x, int y, int z) {
    // does some math
}

Compare it to this C++ code:

int doSomeMath(int x) {
    return |int y| {
        return |int z| {
            // do some math
        }
    }
}

The first function defines a single function that takes in three inputs and returns some output. The second function defines a single function that takes in one input, and returns a function with takes in one input, which returns a function that takes in one input and returns some output. Are these things really that different?

It’s a little hard to see in C++’s syntax, but these two things aren’t that different in theory! Here’s the same idea in Haskell:

doSomeMath x y z = …

Compared to:

doSomeMath x = (\y -> (\z -> …))

This may still be a little crazy. Let’s look at some more ideas, and see if we can understand it better.

Higher-Order Functions

Did you know you can write functions that take other functions as parameters? These are called “higher-order functions” (a big name that we probably shouldn’t use, and which makes the whole idea more confusing than it needs to be).

Let’s look at an example:

addWith :: (Integer -> Integer) -> Integer -> Integer
addWith f x = (f x) + 1

This strange-looking function takes in a function and an integer. It applies the function to the integer, and then adds one to the result. You can use it like this:

multiplyByTwo :: Integer -> Integer
multiplyByTwo x = x * 2

addWith (multiplyByTwo) 5

And the result will be (5 * 2) + 1, resulting in an output of 11!

These are higher-order functions!

Write your own higher-order functions. Come up with five higher-order functions, and put them in a .hs file. Save these for review at the end of the lab.

Returning Functions From Functions

You can also write functions that return other functions! Here’s an example:

getAdder :: Integer -> (Integer -> Integer)
getAdder x = (\y -> x + y)

This function, getAdder, takes in an Integer, and returns a function that takes in an Integer and adds that Integer to the integer passed to getAdder… maybe it’s clearer with an example:

add10 :: Integer -> Integer
add10 = getAdder 10

fifteen = add10 5

add10 is a function that takes in an Integer and adds 10 to it, returning an Integer! Note that the type of add10 is exactly the return type of getAdder! When you call getAdder, the value of x is filled out in the body of the function, and the inner function is returned! This inner function takes in an Integer named y, adds 10 to it, and returns the result.

Write your own functions that return functions. Come up with five of them, and put them in a .hs file. Save these for review at the end of the lab.

Partial Application

This is all great, but it seems like a lot of work. Is there an easier way? Yes! There is! Haskell includes a feature called “partial application,” meaning that if you have a function with multiple parameters, and don’t pass in values for all of them, you get back the same function with just those values filled in. Let’s try the adder example again, but with partial application:

getAdder :: Integer -> Integer -> Integer
getAdder x y = x + y

add10 :: Integer -> Integer
add10 = getAdder 10

fifteen :: Integer
fifteen = add10 5

Look at that! By giving only one parameter to getAdder, even though it takes two parameters, we got back getAdder with that first parameter filled in! This is a really powerful feature of Haskell’s, and also happens to be based on the insight of currying (see? I said we’d come back to currying!). It’s thanks to the idea of currying, the idea that a function of many parameters is the same as many functions with one parameter each, that we can do partial application at all! The theory is useful!

Write some examples of partial application. Come up with five of them, and put them in a .hs file. Save these for review at the end of the lab.

Defining Your Own Types

So, now that we understand a bit about how functions work in Haskell, let’s talk about how data types work. Data types in Haskell are called “algebraic data types.” The term “algebraic” may suggest that you can do math with them, and you’re right! In Haskell there are both “product types” and “sum types,” which we’ll talk about now.

Sum Types

You’ve actually already met the most common sum types in Haskell: Bool! In Haskell, Bool is defined like so:

data Bool = False | True

This says that the data type Bool can be either False or True. It’s this “either” that makes the type a sum type. Sum types define a collection of potential values. Think of something kinda like an enum from C++.

These types can also hold data. For example, Haskell has a very useful type called Maybe that is defined like this:

data Maybe a = Nothing | Just a

The a is a placeholder for a type. It means that Maybe is always either Nothing (and contains no data), or Just a, meaning a single value of some type.

You can also have sum types with only one possibility, like this:

data Void = Void

This means that there is a type Void with only one constructor, also called Void.

That’s right! Those things on the right side of the equals sign are actually constructors! You’ve been defining functions this whole time! If you were to look at the type of True, it’d look like True :: Bool, which you can think this as saying that True has the type Bool, or that True is a function that takes in no parameter and returns a value of type Bool.

This is clearer with Just, which has a type like Just :: a -> Maybe a (once again, a is a placeholder for an arbitrary type). This makes it obvious that Just is a function, which takes in a value of some type, and returns a value of type Maybe a (meaning a Maybe containing a value of some arbitrary type).

Product Types

Haskell also has product types, which are the complement to sum types. They look like this:

data Pair = P Integer Double

That’s right! You’ve already seen these! Product types are just types collected together, like the Integer and Double in this example. You can read them as saying that a Pair is an Integer and and Double, together (contrast this to sum types, which are joined with an or, not an and).

Think of product types like structs in C++. A bunch of fields grouped together.

Write some types of your own! Can they have more than one type parameter? Can they have a concrete type? What can you do? Come up with ten of them, and put them in a .hs file. Save these for review at the end of the lab.

Pattern Matching

With all of this, you may be wondering how you access the contents of these types. The answer is pattern matching!

Take a function like this:

doListStuff :: [a] -> Integer
doListStuff list = case list of
                       [] -> 0
                       x  -> 1

This function is matching on the pattern, or structure, of list. If list is empty (denoted by []), the function returns 0. If list isn’t empty, the function returns 1.

This pattern is so common, Haskell actually provides a shorthand for it!

doListStuff :: [a] -> Integer
doListStuff [] = 0
doListStuff list = 1

This means the same thing as the earlier function, but with a lot less typing.

Applying this idea to Maybe, we can do something like this:

doMaybeStuff :: Maybe Integer -> Integer
doMaybeStuff Nothing = 0
doMaybeStuff Just x = x + 1

This function pattern matches on the contents of the Maybe Integer input. If the Maybe is of the Nothing variant, the function returns 0. If it’s of the Just variant, the function extracts the contained value, adds 1 to it, and returns the result. This is pattern matching!

Do some pattern matching of your own! What can you do? Come up with five uses of pattern matching, and put them in a .hs file. Save these for review at the end of the lab.

Conclusion

That’s it for today’s lab! When you’re done, let the professor know so he can take a look at your work and give you a grade.