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

COMP 481, Week 7, Chapter 11

Copyright By Assignmentchef 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 Haskells 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]