CS代写 Microsoft PowerPoint – Week5.pptx

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