Microsoft PowerPoint – Week5.pptx
2022‐10‐05
Copyright By PowCoder代写 加微信 powcoder
Ch 7: Making Our Own Types and Type Classes
Ch 8: Input and Output
University of the Fraser Valley
COMP 481: Functional and Logic Programming
• Data Types
• Nesting Types (7‐‐12)
• Record Syntax (13‐‐15)
• Type Parameters (16‐‐28)
• Example 3D Vector (29‐‐33)
• Derived Instances (34‐‐49)
• Type Synonyms (50‐‐61)
• Recursive Data Structures (62‐‐69)
• Example Tree Type (70‐‐101)
• The Functor Type Class (102‐‐115)
• Kinds (116‐‐119)
• Separating Pure from Impure (121‐‐125)
• Gluing I/O Actions Together (126‐‐134)
• Reverse Strings in I/O (135‐‐139)
• Demos of Some I/O Action Functions (140‐‐154)
2022‐10‐05
Creating a
Defining our own type follows the syntax for what could be
the `Bool` type:
data Bool = False | True
• `data` keyword, followed by the capitalized name of the type
• equal sign
• capitalized value constructors separated by “or” Sheffer stroke `|`
We want a Shape type to have both circles or rectangles.
Then the type could be defined as:
{‐ multiline in ghci, otherwise scripts are forgiving ‐}
data Shape =
Circle Float Float Float
| Rectangle Float Float Float Float
• the uses of `Float` here act as constructor parameters
• `Circle` and `Rectangle` act like constructor functions
• try out the type description/signature for each `:t Circle`
• notice that they return type `Shape`
2022‐10‐05
Constructor
A function that takes a `Shape` and calculates its area:
area :: Shape ‐> Float
area (Circle _ _ r) = pi * r ^ 2
area (Rectangle x1 y1 x2 y2) = (abs $ x2 ‐ x1) * (abs $ y2 ‐ y1)
• we cannot write the function as `Circle ‐> Float`
• incorrect as `True ‐> Int`
• `Circle` is defined as a value and `Shape` is its type
• `Circle` constructor function has the same name
• we can pattern match with a constructor and its parameters
• circle needs no position to calculate its area, so `_` is used
Type Class
To declare a type as an instance of the `Show` type class:
data Shape =
Circle Float Float Float
| Rectangle Float Float Float Float deriving (Show)
• then we can create values of Shape:
Circle 1 2 3
Rectangle 10 20 30 40
• and partially apply constructor functions:
map (Circle 10 20) [4,5,6,6]
2022‐10‐05
—Nested Types —
Make Circle type convey more with a nested Point type:
data Point = Point Float Float deriving (Show)
data Shape =
Circle Point Float
| Rectangle Point Point deriving (Show)
• the `Point` type is repeated as the one value name
• then we use `Point` in the constructor definition
of `Circle` and `Rectangle`
• pattern matching needs to be updated
area :: Shape ‐> Float
area (Circle _ r) = pi * r ^ 2
area (Rectangle (Point x1 y1) (Point x2 y2)) = (abs $ x2 ‐ x1) *
(abs $ y2 ‐ y1)
2022‐10‐05
Using Nested
Constructors
area (Circle (Point 0 0) 24)
area . Rectangle (Point 0 0) $ Point 100 100
• a few reminders:
• dot product composes functions
(that take one parameter each)
• `$` applies the function immediately after it
(avoid writing parentheses)
At this point we have enough to justify making our own
`Shape` module (see `shape.hs` script).
• specify constructors we want to export in parentheses:
• If we just want all of the parameters then use `(..)`,
• shorter than specifying `Shape (Rectangle, Circle)`
module Shapes
( Point(..)
, Shape(..)
, baseCircle
, baseRect
2022‐10‐05
Without `(..)`:
• a user could not create new shapes except with functions
`baseCircle` and `baseRect`
• hiding constructors makes the `Shape` type more abstract
• might be good if we want to stop users from pattern matching with
value constructors
• edits to the value constructors would not cascade
(like we saw earlier with Shape and Point)
• we get back to this discussion later with `Data.Map`
Previously, we defined functions with the notation `‐>`
between input parameters, but not so for constructors.
Use Function
Constructors
Try out the functions after loading shape.hs:
:l shape.hs
nudge (baseRect 40 100) 60 23
nudge (baseCircle 8) 3 5
2022‐10‐05
— Record Syntax —
We can create types with a record syntax:
• the value constructor parameters are given meaningful names
• avoids creating nested types
• also creates corresponding functions, one for every single parameter
• call the constructor and specify parameters in any order we choose
For example:
data Car = Car {
company :: String,
model :: String,
year :: Int
} deriving (Show)
Call the constructor:
Car {company = “Ford”, model = “Mustang”, year = 1967}
2022‐10‐05
Choose to use record syntax when the order of the fields
do not immediately make sense.
• a 3D vector would be obvious
• the fields specify the coordinates `x` `y` `z` values
• but, for `Car` parameter order is arbitrary
— Type Parameters —
2022‐10‐05
Parameters
Similar to functions taking parameters, we can generate
new types by passing types as parameters.
Consider Maybe as a type constructor:
data Maybe a = Nothing | Just a
Pass in a type for the parameter `a`, we generate a new
type, such as:
• `Maybe Int`, `Maybe Car`, `Maybe String`, etc.
• `Maybe` is a type constructor, not to be used to create values
• a type constructor must have all parameters passed in
• the value Just ‘a’ has type Maybe Char
• sometimes we want a value to be of more specific type
• Just 3 is at its most generic of type Num a => Maybe a
• we can specify like so: Just 3 :: Maybe Int
General vs specific type also apply to list types:
• `[[String]]` (triple nested list)
• we cannot have a value that has a type of just `[]`
• any value always has a concrete type associated
• a concrete type has no unspecified type parameters
2022‐10‐05
Polymorphic
A more generic type such as `Maybe a` is polymorphic:
• `Maybe a` can manage different kinds of subtypes
with type parameters `a`
Just “Haha”
:t Just “Haha”
:t Just 84
:t Nothing
Just 10 :: Maybe Double
2022‐10‐05
Examples of defining concrete types similar to `Maybe a`
where `a` is replaced by concrete type might be:
data IntMaybe = INothing | IJust Int
data StringMaybe = SNothing | SJust String
data ShapeMaybe = ShNothing | ShJust Shape
Polymorphic
Or we might design something to be as entirely generic.
• `Maybe a` has type parameter `a` so that it could handle working with
values of anything at all
• similarly, the type for empty list is `[a]`
• again, `a` is any type element so the empty list `[]` can operate with
any other type of list:
[1,2,3] ++ []
[“har”,”har”,”har”] ++ []
2022‐10‐05
Generalizing
The `year` field of the `Car` type can be parameterized:
data Car a = Car {
company :: String,
model :: String,
} deriving (Show)
• have the above either in a script without `let`
• or in ghci give the definition all on one line without `let`
• or use multiline `:{ :}` and do not use `let`
A function to display the information of a `Car` would
change from our previous definition of `Car`:
tellCar :: (Show a) => Car a ‐> String
tellCar (Car {company = c, model = m, year = y}) =
“This ” ++ c ++ ” ” ++ m ++ ” was made in ” ++ show y
(compare signature without generic tellCar :: Car ‐> String)
Try out tellCar in ghci:
tellCar (Car {company = “Tesla”, model = “Roadster”, year = 2022 })
2022‐10‐05
Polymorphism
This second version of `tellCar` allows us to work with
various instance types of `Show`:
tellCar (Car “Ford” “Mustang” 1967)
tellCar (Car “Ford” “Mustang” “nineteen sixty seven”)
:t Car “Ford” “Mustang” 1967
:t Car “Ford” “Mustang” “nineteen sixty seven”
• we would likely only ever use the version of `tellCar` that has a year
with `Int` type
• so, parameterizing is not worth the trouble in this case
Book Pattern Matching (Simranjit Singh)
data Book = Book {
title :: String
, author :: String
, pageNum :: Int
deriving (Show)
Book { title = “Fairy Tale”, author = ” “, pageNum = 600 }
tellBook :: Book ‐> String
tellBook (Book {title = t, author = a, pageNum = p}) =
t ++ ” was written by ” ++ a ++ “. It’s ” ++ show (p) ++ ” pages long.”
2022‐10‐05
Conventions
Parameters
Notice the generic types that use type parameters:
• have little need in their implementation for
anything with respect to the type parameters
• e.g.: we would only do things with a list itself that has nothing to do
directly with the type of its elements
• anything we would do with elements, such as a `sum`, we can
specify its implementation when we specify the concrete type
• the same goes for the `Maybe`
• it allows us to specify an implementation when we need to
deal with potentially not having a value of a concrete type we want
• (`Nothing`)
• or having it (`Just x`)
Constraints
Declarations
Type class constraints should not be in the data
declarations of our parameterized types.
• functions which would use the parameterized types
• then have to declare the type‐class constraints regardless
2022‐10‐05
— Example 3D Vector —
An example for implementing our own vector 3D data type
with one parameterization:
data Vector a = Vector a a a deriving (Show)
vplus :: (Num a) => Vector a ‐> Vector a ‐> Vector a
(Vector i j k) `vplus` (Vector p q r) = Vector (i+p) (j+q) (k+r)
dotProd :: (Num a) => Vector a ‐> Vector a ‐> a
(Vector i j k) `dotProd` (Vector p q r) = (i*p) + (j*q) + (k*r)
vmult :: (Num a) => Vector a ‐> a ‐> Vector a
(Vector i j k) `vmult` p = Vector (i*p) (j*p) (k*p)
2022‐10‐05
Parameters
We restrict the vector functions for the parameter to be of
type class `Num`, since we could not expect calculations
where components are of type `Bool` nor `Char`.
• also notice that the definitions restrict only vectors of the same
element concrete types to calculate together
• cannot add vectors with one of type `Int` and the other `Double`
• notice no `Num` restriction in the type declaration of `Vector`
• still need the same restrictions of type class in the functions anyway
Type vs Value
Constructors
Note the difference between type constructors and value
constructors:
• type constructors appear on the left of `=` in type definitions
• value constructors appear on the right of `=` in type definitions
• in function declarations
• use type constructors where types would go
• use value constructors in place of a pattern or value
• the following would not be possible with our `Vector` as defined:
Vector a a a ‐> Vector a a a ‐> a
• the type constructor is `Vector a` and not `Vector a a a`
2022‐10‐05
Give some vector functions a try:
Vector 3 5 8 `vplus` Vector 9 2 8
Vector 3 5 8 `vplus` Vector 9 2 8 `vplus` Vector 0 2 3
Vector 3 9 7 `vmult` 10
Vector 4 9 5 `dotProd` Vector 9.0 2.0 4.0
Vector 2 9 3 `vmult` (Vector 4 9 5 `dotProd` Vector 9 2 4)
— Derived Instances —
2022‐10‐05
Type classes are like interfaces in Java:
• any type within the type class is considered an instance of it
• the type class specifies what kind of behaviour must be
implemented in any type belonging to it
• the type class has no implementation itself
We can take advantage of the type classes that already
exist in Haskell:
* `Eq`, `Ord`, `Enum`, `Bounded`, `Show`, and `Read`
The `deriving` keyword allows us to do so:
data Person = Person {
firstName :: String,
lastName :: String,
age :: Int
} deriving (Eq)
• Haskell compares two Person values to see if their value
constructors are the same
• then checks if the corresponding fields also have equal values
• so, all fields must be types also each an instance of `Eq`
2022‐10‐05
Using `==`
We can test using `==` on values of our `Person` type:
mikeD = Person {firstName = “Michael”, lastName = “Diamond”, age = 43}
adRock = Person {firstName = “Adam”, lastName = “Horovitz”, age = 41}
mca = Person {firstName = “Adam”, lastName = “Yauch”, age = 44}
Give equality tests a try:
mca == adRock
mikeD == adRock
mikeD == mikeD
mikeD == Person {firstName = “Michael”, lastName = “Diamond”, age = 43}
Additionally, we can use `Person` values with anything that
takes `Eq` as a type class constraint, e.g.: `elem` function:
let beastieBoys = [mca, adRock, mikeD]
mikeD `elem` beastieBoys
2022‐10‐05
— `Show` and `Read` —
`Show` and `Read`
Derived Instances
We can make `Person` type
• become an instance of `Show` and `Read` type classes
in order to convert values between strings and back
• again, we need the fields to also be of a type that
are instances of `Show` and `Read`
data Person = Person {
firstName :: String,
lastName :: String,
age :: Int
} deriving (Eq, Show, Read)
• try printing some of the values:
mikeD = Person {firstName = “Michael”, lastName = “Diamond”, age = 43}
“mikeD is: ” ++ show mikeD
2022‐10‐05
String and
If we tried to print without the `Show` derivation, then
Haskell would give us an error message.
We can convert back the other direction and get a `Person`
value from a `String`.
• put the following in a script, then load in ghci:
mysteryDude =
“Person { firstName =\”Michael\”” ++
“, lastName =\”Diamond\”” ++
“, age = 43}”
Give a type annotation to tell Haskell what concrete type it
should evaluate:
read mysteryDude :: Person
Annotations
Type annotation is not needed if Haskell can infer the type:
read mysteryDude == mikeD
• if the type requires further specification with a
parameter type, then we also need to annotate that
• the following will give an error:
read “Just 3” :: Maybe a
• so, then we should adjust the above to be concrete annotation:
read “Just 3” :: Maybe Int
2022‐10‐05
—Ordering —
The `Ord` type class applied to a type definition
• means our defined order for values is considered their ordering from
smallest to largest
See how it is implemented with `Bool`:
data Bool = False | True deriving (Ord)
True `compare` False
True > False
True < False • try swapping False and True in declaration for Bool 2022‐10‐05 Two values created with the same constructor are equal, unless there are fields that must also be compared. • the fields must also have type an instance of the `Ord` type class • e.g.: the `Nothing` value is smaller than any other `Maybe` value • any `Just` values will have their nested elements compared Nested functions cannot be compared, so keep in mind this is only for elements that are also `Ord`. Nothing < Just 100 Nothing > Just (‐49999)
Just 3 `compare` Just 2
Just 100 > Just 50
We cannot do `Just (*2) < Just (*3)` because the nested elements are functions. — Enums, etc. — 2022‐10‐05 data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday deriving (Eq, Ord, Show, Read, Bounded, Enum) Some reminders: • `Enum` places values in a sequential order, with each value having a predecesor and a successor • `Bounded` expects a type to have a lowest value and a largest value With the above, try out a few simple statements: show Wednesday read "Wednesday" :: Day By instance of the `Eq` and `Ord` type classes: Saturday == Sunday Saturday == Saturday Saturday > Friday
Monday `compare` Wednesday
Also by `Bounded` instance:
minBound :: Day
maxBound :: Day
More possible as part of `Enum`:
pred Tuesday
succ Thursday
[Monday .. Friday]
[minBound .. maxBound] :: [Day]
2022‐10‐05
— Type Synonyms —
We can define another name for a type like so:
type String = [Char]
This allows us to use either type name interchangeably:
• note that there is no use of the `data` keyword
The following are equivalent:
toUpperString :: [Char] ‐> [Char]
toUpperString :: String ‐> String
2022‐10‐05
We first declared a `phoneBook` variable with type
`[(String,String)]`.
Use type synonym to make things a bit more readable:
type PhoneNumber = String
type Name = String
type PhoneBook = [(Name, PhoneNumber)]
See how much easier to read functions:
inPhoneBook :: Name ‐> PhoneNumber ‐> PhoneBook ‐> Bool
inPhoneBook name pnum pbook = (name, pnum) `elem` pbook
Use of type
Otherwise, without synonyms, the function would be
described as:
inPhoneBook :: String ‐> String ‐> [(String,String)] ‐> Bool
Try to be judicious with synonyms; do not overuse them.
We can also use synonyms to create type constructors:
type AssocList k v = [(k, v)]
The signature of a function to get the value corresponding
to a key in an association list might look like the following:
(Eq k) => k ‐> AssocList k v ‐> Maybe v
2022‐10‐05
Constructors
Remember, a type constructor takes type parameters and
returns a concrete type, for example `AssocList Int String`.
Perhaps a partially applied type constructor, for example:
type IntMap v = Map Int v
…can be expressed more simply:
type IntMap = Map Int
To implement the above, you will likely need to do a
qualified import and precede the `Map` with module name:
type IntMap = Map.Map Int
Annotations
We cannot use synonyms as a constructor themselves:
AssocList [(1,2),(4,5),(7,9)]
Instead, they are used to specify with type annotations:
[(1,2),(4,5),(7,9)] :: AssocList Int Int
Note that type synonyms, and types in general:
• can only be used in Haskell where the syntax allows for it
(as we have done in our definitions, descriptions, and declarations)
2022‐10‐05
— Two Kinds of Values —
A design for a kind of type we use later has the following
description:
data Either a b = Left a | Right b
deriving (Eq, Ord, Read, Show)
No need to define the above; it is already in `Prelude`.
See how values of the `Either` type are described:
Left “woot”
:t Right ‘a’
:t Left True
2022‐10‐05
for Errors
The `Either` type has similar result as for `Nothing` as
`Maybe a` where one of the parameters is polymorphic.
• `Maybe` type helped deal with computations that could have an error
• the error is for exactly one reason
• e.g.: `find` did not get a match for it to return
With an `Either` type description, we have flexibility to
pass forward more reasoning for an error.
As an example, we will design a map that:
• manages locker numbers,
• tracks lockers’ states so we know which ones are currently used,
• and store a secret combination string for each locker
import qualified Data.Map as Map
data LockerState = Taken | Free deriving (Show, Eq)
type Code = String
type LockerMap = Map.Map Int (LockerState, Code)
• the `LockerState` keeps track of whether the locker is taken or free
• the `Code` and `LockerMap` are only synonyms
2022‐10‐05
Next, we will write a function that searches for the code in
a locker map.
The return value of type `Either` helps deal with two ways
the function could fail:
• the locker could be taken already, so no code should be given back
• the locker number might not exist
In both cases we use a different string to
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com