COMP 481, Week 7, Chapter 11
Copyright By PowCoder代写 加微信 powcoder
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 <- action return (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 actions This has many layers of concepts, so a few examples, first without, and then with: line <- getLine let line' = reverse line putStrLn $ "You said " ++ line' ++ " backwards!" putStrLn $ "Yes, you said " ++ line' ++ " backwards!" Then `IO` as a functor where the type parameter is `String`: line <- fmap reverse getLine putStrLn $ "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` context and 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) getLine putStrLn line The 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 (\n 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 <- getStdGen
putStrLn "Enter a list of numbers (no commas or brackets):"
input <- getLine
let list = getList input
putStr "The list you entered was: "
print(list) -- == putStrLn $ show list
putStrLn "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 [] where
pure 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代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com