Summary of Algebraic Datatypes

Algebraic Datatypes: Summary

Types are defined like this

data TypeName = ConstructorName FieldType FieldType2 | AnotherConstructor FieldType3 | OneMoreCons

… or like this if we’re using type variables

data TypeName variable = Cons1 variable Type1 | Cons2 Type2 variable

You can have one or more constructors
Each constructor can have zero or more fields
Constructors start with upper case, type variables with lower case
Values are handled with pattern matching:

foo (ConstructorName a b) = a+b
foo (AnotherConstructor _) = 0
foo OneMoreCons = 7

Constructors are just functions:

ConstructorName :: FieldType -> FieldType2 -> TypeName
Cons1 :: a -> Type1 -> TypeName a

You can also define datatypes using record syntax:

data TypeName = Constructor { field1 :: Field1Type, field2 :: Field2Type }

This gives you accessor functions like field1 :: TypeName -> Field1Type for free.

Sidenote: Other Ways of Defining Types

In addition to the data keyword, there are two additional ways of defining types in Haskell.

The newtype keyword works like data, but you can only have a single constructor with a single field. It’s sometimes wise to use newtype for performance resons, but we’ll get back to those in part 2.

The type keyword introduces a type alias. Type aliases don’t affect type checking, they just offer a shorthand for writing types. For example the familiar String type is an alias for [Char]:

type String = [Char]

This means that whenever the compiler reads String, it just immediately replaces it with [Char]. Type aliases seem useful, but they can easily make reading type errors harder.

Exercises

All exercises can be found in Set5a and Set5b. Please pay attention in the title of the exercise in which file the exercises of this section can be found.

Exercises from 5a:

Exercise 5a.10

-- Ex 10: define a recursive datatype KeyVals for storing a set of
-- key-value pairs. There should be two constructors: Empty and Pair.
--
-- Empty represents an empty collection. It should have no fields.
--
-- Pair should have three fields, one for the key, one for the value,
-- and one for the rest of the collection (of type KeyVals)
--
-- The KeyVals datatype is parameterized by the key type k and
-- the value type v.
--
-- For example:
--
--  Pair "cat" True (Pair "dog" False Empty)  ::  KeyVals String Bool
--
-- Also define the functions toList and fromList that convert between
-- KeyVals and lists of pairs.

data KeyVals k v = KeyValsUndefined
  deriving Show

toList :: KeyVals k v -> [(k,v)]
toList = todo

fromList :: [(k,v)] -> KeyVals k v
fromList = todo

Exercise 5a.11

-- Ex 11: The data type Nat is the so called Peano
-- representation for natural numbers. Define functions fromNat and
-- toNat that convert natural numbers to Ints and vice versa.
--
-- Examples:
--   fromNat (PlusOne (PlusOne (PlusOne Zero)))  ==>  3
--   toNat 3    ==> Just (PlusOne (PlusOne (PlusOne Zero)))
--   toNat (-3) ==> Nothing
--

data Nat = Zero | PlusOne Nat
  deriving (Show,Eq)

fromNat :: Nat -> Int
fromNat n = todo

toNat :: Int -> Maybe Nat
toNat z = todo

Exercise 5a.12

-- Ex 12: While pleasingly simple in its definition, the Nat datatype is not
-- very efficient computationally. Instead of the unary Peano natural numbers,
-- computers use binary numbers.

-- Your task is to write functions prettyPrint, fromBin, and toBin that
-- convert Bin to human-readable string, Bin to Int, and Int to Bin
-- respectively. Check the original file for more explanation

data Bin = End | O Bin | I Bin
  deriving (Show, Eq)

-- This function increments a binary number by one.
inc :: Bin -> Bin
inc End   = I End
inc (O b) = I b
inc (I b) = O (inc b)

prettyPrint :: Bin -> String
prettyPrint = todo

fromBin :: Bin -> Int
fromBin = todo

toBin :: Int -> Bin
toBin = todo

You have reached the end of this section! Continue to the next section:

6. How do Algebraic Datatypes Work?

You can check your current points from the blue blob in the bottom-right corner of the page.