• Back to main page

Module 02: Algebraic data types and pattern matching

• Record your team members here:

XXX FOR NEXT TIME: build in some places for reporting out

For this module, the person whose birthday is latest in the year should start out as the driver. The person sitting to their left (wrapping around if necessary) is the reporter. The module will indicate points when you should rotate roles (each role rotates left).

Remember, you should make sure that everyone on your team is understanding everything, regardless of their prior amount of Haskell experience.

> {-# LANGUAGE GADTs #-}

The above {-# LANGUAGE #-} thingy turns on a Haskell language extension called “GADTs”, which stands for “Generalized Algebraic Data Types”. You need not worry about what that means for now; it will enable us to use some nice syntax.

Enumerations

> data Color where
>   Red   :: Color
>   Green :: Color
>   Blue  :: Color
>   deriving Show
> 
> colorChar :: Color -> Char
> colorChar Red   = 'r'
> colorChar Green = 'g'
> colorChar Blue  = 'b'
> 
> isRed :: Color -> Bool
> isRed Red   = True
> isRed Green = False
> isRed Blue  = False

• Load this file into GHCi and type Red at the prompt. What happens?

• What is the type of Red?

• What does the function colorChar do? What does isRed do?

• The data Color where ... declaration defines an algebraic data type (ADT) called Color. Red, Green, and Blue are called data constructors, or just constructors for short. Explain what you think the relationship between an algebraic data type and its constructors is.

• Try removing or commenting out the last line of the definition of colorChar. Reload the module and try evaluating colorChar Blue. What happens?

• Now add > {-# OPTIONS_GHC -Wall #-} as the very first line of this file (with a blank line after it), and reload again. Explain what happens.

• (If you wish you can now put colorChar back to the way it was at first.)

More general ADTs

ROTATE ROLES

> data MaybeInteger where
>   No  :: MaybeInteger
>   Yes :: Integer -> MaybeInteger
>   deriving Show
> 
> mi1, mi2 :: MaybeInteger
> mi1 = No
> mi2 = Yes 6
> 
> unMaybe :: MaybeInteger -> Integer
> unMaybe No = 0
> unMaybe (Yes 6) = 249
> unMaybe (Yes n) = n
> 
> data Record where
>   NameAndAge      :: String -> Integer -> Record
>   AddressAndEmail :: String -> String -> Record
>   TopSecret       :: Integer -> Bool -> (Char, Integer) -> Record
>   deriving Show
> 
> record1, record2, record3 :: Record
> record1 = NameAndAge "McGrew" 6
> record2 = AddressAndEmail "55 Ridge Avenue" "mcgrew@mcgrew.com"
> record3 = TopSecret 17 False ('x',10)
> 
> recordAge :: Record -> Integer
> recordAge (NameAndAge _ age)          = age
> recordAge (AddressAndEmail _ _)       = 0
> recordAge (TopSecret age True _)      = age
> recordAge (TopSecret _ False (_,age)) = age
> 
> recordAge2 :: Record -> Integer
> recordAge2 r =
>   case r of
>     (NameAndAge _ age)          -> age
>     (AddressAndEmail _ _)       -> 0
>     (TopSecret age True _)      -> age
>     (TopSecret _ False (_,age)) -> age
> 
> foo :: Record -> Integer
> foo r = 3 * (case r of
>                 NameAndAge _ age -> age
>                 _                -> 7
>             )
>         + 2

• What is the type of No? What is the type of Yes?

• Explain in English what values of type MaybeInteger look like. (Hint: your answer should contain the word “either”.)

• Go back and reread your answer to the question about the relationship between algebraic data types and constructors. Has your answer changed at all? If so, write down a revised version here.

• What does unMaybe (Yes 50) evaluate to? What about unMaybe (Yes 6)?

• Try removing some parentheses from the definition of unMaybe, for example, change the middle line to > unMaybe Yes 6 = 249. Reload the module. Can you explain the resulting error message? (You can then put unMaybe back as it was.)

• Write a function of type MaybeInteger -> Integer with the following behavior:

  • If there is no Integer, return 0
  • If there is an even Integer, return half of it
  • If there is an odd Integer, return double it

You should write your function definition below, using bird tracks (greater-than signs) in front of your code, just like the rest of the code in this module. Be sure to :reload the module in GHCi to test your code.

• Describe in English what values of type Record look like.

• Look at the definition of recordAge. What do you think _ means? Predict the output of recordAge on the inputs record1, record2, and record3.

• Evaluate recordAge on record1, record2, and record3. Were you right? If not, does it change what you think _ means?

• The underscore _ which can occur on the left-hand side of the = sign in a function definition is called a wildcard. Can you go back and simplify the definition of the isRed function using a wildcard? Why or why not?

• Write a function of type MaybeInteger -> Integer which always returns 3, no matter what input it is given. Make your function definition as simple as possible.

• Can you go back and simplify the unMaybe function using a wildcard? Why or why not?

• Change the first line of the definition of recordAge to

  recordAge (NameAndAge name age) = age

  Does this change the behavior of recordAge? If so, how? If not, in what circumstances would you prefer using one definition or the other?

• What is the difference, if any, between the behavior of recordAge and recordAge2? Describe what you think case does.

• Predict the values of foo record1 and foo record2. Were you right?

Recursive ADTs

ROTATE ROLES

> data Nat where
>   Z :: Nat
>   S :: Nat -> Nat
>   deriving Show
> 
> three :: Nat
> three = S (S (S Z))
> 
> natToInteger :: Nat -> Integer
> natToInteger Z     = 0
> natToInteger (S n) = 1 + natToInteger n
> 
> natPlus :: Nat -> Nat -> Nat
> natPlus Z     n = n
> natPlus (S m) n = S (natPlus m n)
> 
> data IntList where
>   Empty :: IntList
>   Cons  :: Integer -> IntList -> IntList
>   deriving Show
> 
> intListLength :: IntList -> Integer
> intListLength Empty       = 0
> intListLength (Cons _ xs) = 1 + intListLength xs

• Give three different examples of values of type Nat (besides three).

• Describe in English what values of type Nat look like. Why do you think it is called Nat?

• What does natToInteger do? How does it work?

• Try natPlus on some examples. What does it do? Can you explain how it works?

• Give three different examples of values of type IntList.

• Describe in English what values of type IntList look like.

• Write a function intListLengthNat :: IntList -> Nat which works like intListLength but returns a Nat instead of an Integer.

  Note that it should be the case that any arbitrary value list :: IntList satisfies natToInteger (intListLengthNat list) == intListLength list.

• Write a function sumIntList :: IntList -> Integer which adds up all the Integer values contained in an IntList.

• Write a function incrIntList :: IntList -> IntList which adds one to all the Integer values contained in an IntList.

• Write a function intListAppend :: IntList -> IntList -> IntList which appends two IntLists together into one big IntList.

• Create an algebraic data type called ThreeTree, such that values of type ThreeTree look like either
  • a Leaf containing an Integer value, or
  • a Branch with three children (of type ThreeTree).

  Don’t forget to put deriving Show at the end of your definition so values of type ThreeTree can be displayed in GHCi.

• Give three example values of type ThreeTree.

• Write a function sumThreeTree :: ThreeTree -> Integer which adds up all the Integer values contained in a ThreeTree.

• Write a function incrThreeTree :: ThreeTree -> ThreeTree which adds one to all the Integer values contained in a ThreeTree.

Feedback

• How long would you estimate that you spent working on this module?

• Were any parts particularly confusing or difficult?

• Record here any questions, comments, or suggestions for improvement.