[SOLVED] CS代写 COMP 481, Week 7, Chapter 11

COMP 481, Week 7, Chapter 11

Copyright By PowCoder代写加微信 assignmentchef

University of the Fraser Valley

COMP 481: Functional and Logic Programming

• functor design
• IO actions as functors
• functions as functors
• functor laws
• breaking the functor laws
• using applicative functors
• `Maybe` the applicative functor
• the applicative style
• lists (as applicative functors)
• IO (as an applicative functor)
• functions (as applicative values)
• `ZipList` Applicative Functor
• Applicative Laws
• Useful Functions for Applicatives

Interface-style

The Haskell programming language is:
• bigger on interface-style design
• than on classes- and subclass-hierarchy design

as in other object-oriented programming languages.

• some value in our programs can act as many different
kinds of things, described by different type classes

A thing can be categorized into many type classes,
not just one hierarchy.

Type Class

Recall type classes such as:
• `Eq` for describing types with values we can check for equality, and
• `Ord` for describing types with values that are orderable.

These examples of type classes demonstrate
the usefulness of abstract descriptions

Recall the `Functor` type class describes:
• types with nested values
• that can have a function applied
• and maintain the parent structure.

Functionality

`Functor` type class: types that can be mapped over.

Applying functions on elements of:
• an input set (a domain)…
• …to an output set (a range)
• (there could be repetition both in the input set and in the output set)

• this may seem overkill when the input set is a singleton
(like with the `Maybe` type)

• but it allows you to focus your work on the nested values

Realize that `Functors` allow you to begin to think of things
such as lists, `Maybe`, binary trees, etc., as having similar
possible behaviour.

— Functor Design —

The `Functor` type class has only one method that must be
implemented on any instances called `fmap`, which we have
already seen.

• again, its description is `fmap :: (a -> b) -> f a -> f b`

• see how the description fits within the context of `f` to the nested
values `a` and `b`

• the function passed in to `fmap` is NOT `f`, but the parameter
function `(a -> b)`

• `(a -> b)` is the function applied to the nested values, where as `f`
maintains itself as parent context

Parameters

To describe an instance of `Functor` as a type constructor, it
must be of kind `* -> *`:

• give one type parameter as input, and the type
constructor will evaluate to one concrete type

• e.g.: `Maybe` takes one type parameter, such
as `Maybe Int`, to describe a concrete type

Then with a type constructor such as `Either` that takes
two type parameters:

• we must additionally supply exactly one type parameter, `Either a`
• cannot write `instance Functor Either where`
• must write `instance Functor (Either a) where`

`Either a`
as a Functor

To implement `fmap` with the `Either a` type constructor
would then be described as:
fmap :: (b -> c) -> Either a b -> Either a c

• in the above `Either a` remains as a fixed type constructor
• the context is always a type constructor taking exactly one parameter

— I/O Actions as Functors —

Notice that the `IO a` type has the one parameter `a`,
where `IO` has been implemented as a Functor.

A description for how it is implemented already:

instance Functor IO where

fmap g action = do

let result <- actionreturn (g result)The input parameter `g` is NOT the parent context `f` (in this case `IO`)!The textbook often uses the same letter `f` for both functor and function:• `g` is some function passed in as a parameter of `fmap`• the context is an I/O action, suppose `IO String` (which is NOT `g`)Note that `return` wraps the IO parent context:• this requires an I/O action in the process, so it must be bound with `<-` assignment (unless it is the last line of the `do` block)• this must be done within a `do` block as part of multiple I/O actionsThis has many layers of concepts, so a few examples, first without, and then with:line <- getLinelet line’ = reverse lineputStrLn $ “You said ” ++ line’ ++ ” backwards!”putStrLn $ “Yes, you said ” ++ line’ ++ ” backwards!”Then `IO` as a functor where the type parameter is `String`:line <- fmap reverse getLineputStrLn $ “You said ” ++ line ++ ” backwards!”putStrLn $ “Yes, you said ” ++ line ++ ” backwards!”See how the function `reverse` passed in to `fmap` must work with types `String`:• input of `reverse` is String(the type for nested `getLine` output)• the output of `reverse` is also a String(determining the type for `line`)• but, we passed `reverse` in to `fmap`, which returns an `IO` context, so `fmap reverse getLine` result is of type `IO String`• the `<-` operation removes the `IO` contextand stores the nested `String` value in `line`Point-free • if you are wanting to perform I/O action and then a function on the • …instead consider using `fmap` and pass the function in together with the I/O action• then the function passed in can be a composition using point-free notation, or a lambda function, etc.line <- fmap (intersperse ‘-‘ . reverse . map toUpper) getLineputStrLn lineThe equivalent function passed to `fmap` written without using point-free is:(xs -> intersperse ‘-‘ (reverse (map toUpper xs)))

— Functions as Functors —

The syntax we have seen for descriptions
of functions is `a -> b`:

• notice it is written similar to a binary operator

• consider it written as `(->) a b`

• if we omit the last parameter, we get `(->) a`

• this describes the syntax for a constructor
of a function that takes one parameter

• this is used to implement an instance of `Functor`

instance Functor ((->) r) where

fmap f g = (x -> f (g x))

*Equivalent
Composition

The textbook just demonstrates how the composition
operator `.` is equivalent to `fmap` when implementing a
function as a `functor`.

• function composition suffers from the notation of mathematics
where they are applied in backward order from their evaluation

• piping would be much easier to read as code, similar to a `do` block

The above is just function composition, which could be
written more concisely as:

instance Functor ((->) r) where

fmap = (.)

The implementation exists in `Control.Monad.Instances`
module. Consider some re-writing of types:

fmap :: (a -> b) -> f a -> f b

fmap :: (a -> b) -> (->) r a -> (->) r b

fmap :: (a -> b) -> (r -> a) -> (r -> b)

• then see in this instance, `fmap` takes two functions as parameters
• the composition would be, mathematically `r -> a` then `a -> b`,

so that altogether the result is `r -> b`

Demonstrations
of Functions as

ghci> :t fmap (*3) (+100)
fmap (*3) (+100) :: (Num a) => a -> a

ghci> fmap (*3) (+100) 1

ghci> (*3) `fmap` (+100) $ 1

ghci> (*3) . (+100) $ 1

ghci> fmap (show . (*3)) (+100) 1

Note that the order of operations will first compose the
functions and then apply the one resulting function.

ghci> fmap (replicate 3) [1,2,3,4]

[[1,1,1],[2,2,2],[3,3,3],[4,4,4]]

ghci> fmap (replicate 3) (Just 4)

Just [4,4,4]

ghci> fmap (replicate 3) (Right “blah”)

Right [“blah”,”blah”,”blah”]

ghci> fmap (replicate 3) Nothing

ghci> fmap (replicate 3) (Left “foo”)

Left “foo”

— Functor Laws —

There are properties and behaviours of functors
we call laws:

• they are not checked by Haskell automatically

• however, all the library functors implement them

• we must check these laws when implementing our own functors

1. the function `id` mapped over a functor
must return the same functor value

2. `fmap` distributes across composition

Details of

1. the function `id` mapped over a functor must return
the same functor value
• i.e.: `fmap id = id`

• e.g.: `fmap id (Just 3)` vs `id (Just 3)`

2. `fmap` distributes across composition
• i.e.: `fmap (f . g) = (fmap f . fmap g)`
• i.e.: `fmap (f . g) x = fmap f (fmap g x)`
• ultimately, nothing about applying the functor as a type changes the

behaviour of other functions applied over it

• for example, there is nothing about lists that changes how a function
will operate on its elements

— Breaking the Functor Laws —

We will consider an example that breaks the laws, just to
see what happens.

data CMaybe a = CNothing | CJust Int a deriving (Show)

• the `C` stands for counter

• the first field in the `CJust` constructor will always have type `Int`

• this is similar to `Maybe a`,
but will just be used as a counter

• the second field is of type `a` and will depend
on the concrete type we choose later for `CMaybe a`

ghci> CNothing

ghci> CJust 0 “haha”

CJust 0 “haha”

ghci> :t CNothing

CNothing :: CMaybe a

ghci> :t CJust 0 “haha”

CJust 0 “haha” :: CMaybe String

ghci> CJust 100 [1,2,3]

CJust 100 [1,2,3]

Instance of

Now we will implement `CMaybe a` as a functor.
• so `fmap`

• applies the function passed in to the second field of `CJust`
• and increments the first field,

• and otherwise, a `CNothing` is left alone:

instance Functor CMaybe where

fmap g CNothing = CNothing

fmap g (CJust counter x) = CJust (counter + 1) (g x)

• (in ghci, no need for `let` with instance and can be multiline)

First Functor
Law Broken

See how we can apply fmap now:

ghci> fmap (++ “ha”) (CJust 0 “ho”)

CJust 1 “hoha”

ghci> fmap (++ “he”) (fmap (++ “ha”) (CJust 0 “ho”))

CJust 2 “hohahe”

ghci> fmap (++ “blah”) CNothing

But the first law does not hold:

ghci> fmap id (CJust 0 “haha”)

CJust 1 “haha”

ghci> id (CJust 0 “haha”)

CJust 0 “haha”

Functor Law

And neither does the second law hold:

ghci> fmap (++ “he”) . fmap (++ “ha”) $ (CJust 0 “ho”)

CJust 2 “hohahe”

ghci> fmap ((++ “he”) . (++ “ha”)) $ (CJust 0 “ho”)

CJust 1 “hohahe”

Independent
of Context

The functor laws are necessary to ensure they do not
obfuscate the use of our other functions we may write.

• i.e.: we should not get confused about how a function will be applied
to nested elements depending on context

• this makes our code easier to read

• in turn, many of the other “-ities” become supported, such as
extensibility, maintainability, etc.

— Using —

in Context

Functors can be taken to a more general context by
partially applying the function passed in to `fmap`:

fmap (*) Just 3

The above results in `Just ((*) 3)` or `Just (3 *)`.

• the nested value becomes a partially applied function

ghci> :t fmap (++) (Just “hey”)

fmap (++) (Just “hey”) :: Maybe ([Char] -> [Char])

ghci> :t fmap compare (Just ‘a’)

fmap compare (Just ‘a’) :: Maybe (Char -> Ordering)

ghci> :t fmap compare “A LIST OF CHARS”

fmap compare “A LIST OF CHARS” :: [Char -> Ordering]

ghci> :t fmap (x y z -> x + y / z) [3,4,5,6]

fmap (x y z -> x + y / z) [3,4,5,6] :: Fractional a => [a -> a -> a]

In the expressions involving `compare` function

• the type for compare is `compare :: (Ord a) => a -> a -> Ordering`

• `fmap compare “A LIST OF CHARS”`

• the first `a` in the type description for `compare` is inferred to be `Char`

• then the second `a` must be type `Char`

• the combined partially-applied compare function and the functor
together generate a list of functions of type `Char -> Ordering`

Multiparameter

• you may wonder how to work with the last expression
• assign the expression result to a variable: `functions` (see below)

• each function is missing two parameters: `y` and `z`

• these correspond to the `[ a -> a ->` part of the type description

• apply the element functions `fmap (f -> f 1 2) $ functions`
• this adds `0.5 = y / z` to each of the already

supplied values of `x` in the original list [3,4,5,6]

functions = (fmap (x y z -> x + y / z) [3,4,5,6])

ghci> fmap (f -> f 1 2) functions

— `Maybe` the Applicative Functor —

We have seen how to use functions on the nested
elements of functors.

• “functor value” just means some context with nested elements

Applicative functors go one step more abstract and allow
us to define operations between functor values.

Consider the following situation:

• we have a functor full of nested partially applied functions

• we have another functor full of nested elements

• we want the corresponding nested functions and
nested elements to be calculated together

Consider such an operation:

ghci> Just (+3) <*> Just 9

We need the `Applicative` type class:
• we must then implement the `pure` function, and
• we must implement the `<*>` function

The `Applicative` type class
(remember, `f` is likely NOT a function!):

class (Functor f) => Applicative f where
pure :: a -> f a
<*> :: f (a -> b) -> f a -> f b

Maybe as an
Applicative

A function named with all special characters is
automatically a binary operator.

Implementation for the `Maybe` type:

instance Applicative Maybe where

pure = Just

Nothing <*> _ = Nothing

(Just g) <*> something = fmap g something

• `pure = Just` is equivalent to `pure x = Just x`

Implementation

(Just g) <*> something = fmap g something

• the last line may be difficult to imagine what is happening, but recall
the example we are working toward

• we want to get the function `g` out of the first functor `(Just g)`
• apply the function `g` to the second functor
• (`something` contains elements that can have `g` applied to them)
• by implementation, we are forced to have the two functors in exactly

this order with `<*>`

• we cannot transpose the order for nested function and something

These implementations are already part of Haskell, so give
them a try:

Just (+3) <*> Just 9

pure (+3) <*> Just 9

Just (++ “haha”) <*> Nothing

Nothing <*> Just “woot”

• there are many kinds of applicative functors
• so, there are many kinds of results for `pure`
• `pure (+3)` takes advantage of Haskell’s inference

• what functor type will match with `Just 9`
in order to match on the left an expression `Just (+3)`

— The Applicative Style —

The order of operations using `<*>` is from left-to-right
• when writing larger expressions of more than two functor values
• this is called left-associative
• then partially applied functions leftmost need more parameters

For example:
pure (+) <*> Just 3 <*> Just 5

• notice that the above expression is similar in syntax as `(+) 3 5`
• the given expression is equivalent to

• `(pure (+) <*> Just 3) <*> Just 5`
• …and result of `(pure (+) <*> Just 3)` is `Just (3+)`

Applicative

The advantage of applicative types:
• we can use functions on nested values within functors without

having to worry about what those functors are

• `pure g <*> x <*> y <*> …`

• the `g` can have as many parameters as desired

• each successive evaluation of `<*>` applies one more parameter

• `pure g <*> x` is equivalent to `fmap g x`

• (this is one of the applicative laws we will discuss later)

Instead of writing `pure g <*> x <*> …` we could just write
`fmap g x <*> …`

• however, there is an infix version of `fmap` to make expressions even
more concise with `<$>`

(<$>) :: (Functor f) => (a -> b) -> f a -> f b

g <$> x = fmap g x

• so, we could instead write `g <$> x <*> y <*> …`
• note that `g` is a function (a variable one)

Type Descriptions with <$> and <*>

Another example:

(++) <$> Just “Doctor Strange ” <*> Just “and the Multiverse of Madness”

• recall the type for concatenation `(++) :: [a] -> [a] -> [a]`

• the `<$>` operation results in a partially applied function of type
Just (“Doctor Strange “++) :: Maybe ([Char] -> [Char])

• can you work out the type of the last functor in the example?

(Simranjit Singh)

— Presentation 3

— Simranjit Singh

— playing with random, IO, and <$>

import System.Random

getList :: String -> [Int]

getList xs = foldr (
acc -> (read n :: Int) : acc) [] list

where list = words xs

(Simranjit Singh)

genNewList :: [Int] -> StdGen -> IO ()

genNewList xs gen =

(randNumber, newGen) =
randomR (1,3) gen :: (Int, StdGen)

secretCalc x

| x == 1= print $(+75) <$> xs

| x == 2= print $ (*5) <$> xs

| x == 3= print $ (`div` 3) <$> xs

| True=

putStrLn “Something went terribly wrong”

secretCalc randNumber

(Simranjit Singh)

gen <- getStdGenputStrLn “Enter a list of numbers (no commas or brackets):”input <- getLinelet list = getList input putStr “The list you entered was: “print(list) — == putStrLn $ show listputStrLn “I have now done a secret operation on your list”putStr “Your new list is: “genNewList list gen— Lists (as applicative functors) — We have the implementation of lists as applicative instance Applicative [] wherepure x = [x]fs <*> xs = [g x | g <- fs, x <- xs]• notice that `pure` creates a singleton list always• also notice that the `g` and `x` in the above create ALL possible combinations of functions from `fs` and values from `xs`• the type of `<*>` restricted to lists:
`(<*>) :: [a -> b] -> [a] -> [b]`

• since there are potentially many functions,
the implementation needs list comprehensions
(to facilitate all possible combinations)

with Lists

Lists with `<*>` will remind you when you apply it that you
will get every combination of result possible.

[(*0),(+100),(^2)] <*> [1,2,3]

The next example shows step-by-step evaluation of
multiple operations:

ghci> [(+),(*)] <*> [1,2] <*> [3,4]

[(+1),(+2),(*1),(*2)] <*> [3,4]

[4,5,5,6,3,4,6,8]

One more example:

ghci> (++) <$> [“ha”, “he”, “hm”] <*> [“?”, “!”, “.”]

[“ha?”,”ha!”,”ha.”,”he?”,”he!”,”he.”,”hm?”,”hm!”,”hm.”]

Nondeterministic
Computation

We can think of lists as nondeterministic computations.

• a value such as `”what”` or `100` is deterministic
• a value such as `[1,2,3]` may decide among its three elements
• the `<*>` presents us with all possible outcomes on lists

Notice how we can use `<*>` to replace list
comprehensions:

ghci> [ x*y | x <- [1,2,3], y <- [4,5,6] ][4,5,6,8,10,12,12,15,18]ghci> (*) <$> [1,2,3] <*> [4,5,6]

[4,5,6,8,10,12,12,15,18]

Combining with `filter` is especially useful:

ghci> filter (> 10) $ (*) <$> [1,2,3] <*> [4,5,6]

[12,12,15,18]

— IO (as an applicative functor) —

Applicative

We look at the implementation of `IO` as an applicative

instance Applicative IO where

pure = return

s <*> t = do

return (g x)

• `pure = return` works as an IO action ignoring the value passed in

• `<*>` for `IO` has description `<*> :: IO (a -> b) -> IO a -> IO b`

• implementation of `<*>` must then remove the `IO` context for both s
and t parameter values

• `do` is needed to glue together multiple I/O actions into one

• `return` will place the result `(g x)` back into an `IO` context

x <- (++) <$> getLine <*> getLine

putStrLn $ “two lines concatenated: ” ++ x

• the nested result of a `getLine` I/O action is a `String`

• the order of the performed I/O action of each `getLine`
determines the order of the concatenated values

• the result of `(++) <$> getLine <*> getLine`
is of type `IO b`
where `b` in this case is `String`

• this is altogether one I/O action and we can
assign the yield to `x` as a `String` value

— Functions (as applicative values) —

The implementation for functions as applicatives:

instance Applicative ((->) r) where

程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]