# Module 03: Polymorphism and Lists

- Record your team members here:

In this module we will complete our initial exploration of the Haskell programming language. For today, choose whoever you wish to start as the driver.

## Maybe

```
data Maybe a where
Nothing :: Maybe a
Just :: a -> Maybe a
```

Note that the above definition of `Maybe`

does not have bird tracks in front of it since it is already defined in the standard library; I just wanted to show you its definition.

```
> w :: Maybe Int
> w = Just 3
>
> x :: Maybe String
> x = Just "hello"
>
> y :: Maybe Char
> y = Nothing
>
> z :: Maybe (Maybe Int)
> z = Just Nothing
>
> safeDiv :: Integer -> Integer -> Maybe Integer
> safeDiv _ 0 = Nothing
> safeDiv x y = Just (x `div` y)
>
> showDiv :: Integer -> Integer -> String
> showDiv x y = case safeDiv x y of
> Nothing -> "Division by zero"
> Just z -> "Result is " ++ show z
```

Give two example values of type

`Maybe Bool`

.How many distinct values of type

`Maybe (Maybe Bool)`

are there? List all of them.How is

`safeDiv`

different from`div`

?Try

`showDiv`

on some examples. Describe in words what it does.What does the

`a`

in the definition of`Maybe`

represent?What Java feature does it remind you of?

Write a function

`plusMaybe :: Maybe Integer -> Maybe Integer -> Maybe Integer`

which performs addition if both arguments are`Just`

, and returns`Nothing`

otherwise.

**When you reach this point, STOP and let Dr. Yorgey know.**

## Lists

**ROTATE ROLES**

```
> ints :: [Integer]
> ints = [3, 5, 92]
>
> noInts :: [Integer]
> noInts = []
>
> moreInts :: [Integer]
> moreInts = 7 : ints
>
> yetMoreInts :: [Integer]
> yetMoreInts = 4 : 2 : ints
>
> someInts :: [Integer]
> someInts = 8 : 42 : noInts
>
> ints2 :: [Integer]
> ints2 = 3 : 5 : 92 : []
```

Evaluate

`length ints`

and`length noInts`

.Explain what

`[]`

means.Evaluate

`moreInts`

and`length moreInts`

.Do the same for

`yetMoreInts`

.Now evaluate

`ints`

. Has it changed?Write an expression

`e`

such that`length e`

evaluates to`6`

.Explain what the

`(:)`

operator does.What will

`someInts`

evaluate to? How about`length someInts`

? Write down your guesses*before*typing them into GHCi.Now check your guesses.

Evaluate

`ints2`

. What do you notice?

**When you reach this point, STOP and let Dr. Yorgey know.**

## Strings

**ROTATE ROLES**

```
> greeting :: String
> greeting = "Hello"
>
> greeting2 :: String
> greeting2 = ['H','e','l','l','o']
>
> greeting3 :: [Char]
> greeting3 = ['H','e','l','l','o']
>
> everyone :: String
> everyone = "world"
```

Evaluate

`greeting`

,`greeting2`

, and`greeting3`

. What differences do you notice? What can you conclude? (Hint: try typing`:info String`

at the GHCi prompt.)Try evaluating

`greeting : everyone`

. What happens?Now try evaluating

`greeting ++ everyone`

. What happens?Explain the difference between

`(:)`

and`(++)`

.What are the types of

`(:)`

and`(++)`

? Do they match your explanation above?Explain the difference between

`'a'`

and`"a"`

.Write an expression using

`greeting`

and`everyone`

which evaluates to`"Hello, world!"`

.

**(You know the drill)**

## List pattern matching

**ROTATE ROLES**

```
> listLength [] = (0 :: Integer)
> listLength (_:xs) = 1 + listLength xs
>
> startsWith :: String -> String -> Bool
> startsWith [] _ = undefined
> startsWith (_:_) [] = undefined
> startsWith (x:xs) (y:ys) = undefined
```

What is the type of

`listLength`

? (Feel free to ask GHCi.)The type of

`listLength`

probably has a lowercase letter in it, like`t`

or`a`

. Explain what the type of`listLength`

means.Evaluate

`startsWith "cat" "catastrophe"`

. What happens?Complete the definition of

`startsWith`

by replacing`undefined`

with appropriate expressions.`startsWith`

should test whether the second argument has the first argument as a prefix. For example:`startsWith "cat" "catastrophe" -> True startsWith "ban" "banana" -> True startsWith "" "dog" -> True startsWith "at" "catastrophe" -> False startsWith "dog" "" -> False`

Write a function

`contains :: String -> String -> Bool`

, which tests whether the second argument contains the first argument as a (contiguous) substring. For example,`contains "cat" "catastrophe" -> True contains "cat" "concatenate" -> True contains "cat" "create" -> False contains "fly" "old lady" -> False`

Hint: use

`startsWith`

.Write a function

`listReverse :: [a] -> [a]`

which reverses a list. For example,`listReverse [] -> [] listReverse [1,2,3] -> [3,2,1] listReverse "Hello" -> "olleH"`

**DO NOT**look at any existing implementation of reverse.