*CSE 320: Programming Languages @ CSU, San Bernardino*

# 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`Char`

s).`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 `struct`

s 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.