02-ADTs

Module 02: Algebraic data types and pattern matching

  • Record your team members here:

For this module, the person whose birthday is latest in the year should start out as the driver. The module will indicate points when you should rotate roles.

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

{-# LANGUAGE GADTSyntax #-}

The above {-# LANGUAGE #-} thingy turns on a Haskell language extension called “GADTSyntax” (GADT stands for “Generalized Algebraic Data Type”). 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 the function 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 (by typing :reload or just :r at the GHCi prompt) 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.)

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

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?

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

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.