Microsoft PowerPoint – Week4.pptx
2022‐09‐28
Copyright By PowCoder代写 加微信 powcoder
Ch 5: Higher‐Order Functions
Ch 6: Modules
University of the Fraser Valley
COMP 481: Functional and Logic Programming
Chapter 5:
• function currying
• creating functions
• simplifying functions
• functions for processing with Lists
• composition
• applying functions when passed as parameter
Chapter 6:
• Data.List, Data.Char, Data.Maybe, Data.Map
2022‐09‐28
The types for many of the functions we have seen so far
included many parameters.
• Haskell only has functions with exactly one parameter
• this is called curried functions
• one parameter applied to the function at a time
• returns a partially applied function
• a partially applied function then takes the remaining parameters
to pass in as arguments
multTriple :: Int ‐> Int ‐> Int
multTriple x y z = x*y*z
This function could be called with `multTriple 3 5 9`, but
the expression `((multTriple 3) 5) 9` is equivalent.
• applies functions partially in order of nested parentheses,
innermost first
• `multTriple 3` is a partially applied function
with one constant `3` and takes two parameters
• also, `(multTriple 3) 5` is a partially applied function with
constants `3` and `5` and takes one parameter
• note that the function type can be written equivalently as
`multTriple :: Int ‐> (Int ‐> (Int ‐> Int))`
2022‐09‐28
It is quite useful to create functions quickly from other
functions:
multPairWithNine = multTriple 9
multPairWithNine 2 3
Definitions
The following two function definitions are equivalent:
• because `compare 100` is a partially applied function itself
compareWithHundred :: Int ‐> Ordering
compareWithHundred x = compare 100 x
compareWithHundred :: Int ‐> Ordering
compareWithHundred = compare 100
Note that `compare` has type
`(Ord a) => a ‐> (a ‐> Ordering)`
2022‐09‐28
Parentheses
Sections are functions surrounded by parentheses:
isUpper :: Char ‐> Bool
isUpper = (`elem` [‘A’..’Z’])
The minus sign has multiple uses, where `(‐1)` means a
negative number, not partially applied subtraction:
• partially applied subtraction function is `(–)`
• OR e.g.: `(subtract 1)`
“subtract 1 from the next parameter”
Without `let`, if we just type a partially applied function:
• ghci will try to print the result, but a function is
not an instance of the `Show` type class.
For example:
multTriple 3 4
will result in an error:
No instance for (Show (Int ‐> Int)) arising from a use of `print’
(maybe you haven’t applied a function to enough arguments?)
In a stmt of an interactive GHCi command: print it
2022‐09‐28
Parameters
Haskell can define functions that take other functions as parameters.
applyTwice :: (a ‐> a) ‐> a ‐> a
applyTwice f x = f (f x)
Try the examples of using the `applyTwice` function:
applyTwice (+3) 10
applyTwice (++ ” HAHA”) “HEY”
applyTwice (“HAHA ” ++) “HEY”
applyTwice (multTriple 2 2) 9
applyTwice (3:) [1]
zipWith’ function can apply operations across two lists.
zipWith’ :: (a ‐> b ‐> c) ‐> [a] ‐> [b] ‐> [c]
zipWith’ _ [] _ = []
zipWith’ _ _ [] = []
zipWith’ f (x:xs) (y:ys) = f x y : (zipWith’ f xs ys)
Some of the interesting examples combine infinite lists:
zipWith’ (*) (replicate 5 2) [1..]
zipWith’ (zipWith’ (*))
[[1,2,3],[4,5,6],[7,8,9]]
[[9,8,7],[6,5,4],[3,2,1]]
2022‐09‐28
Parameters
Consider the two ways to implement the standard library `flip`
flip’ :: (a ‐> b ‐> c) ‐> (b ‐> a ‐> c)
flip’ f = g
where g x y = f y x
flip’ :: (a ‐> b ‐> c) ‐> (b ‐> a ‐> c)
flip’ f x y = f y x
Note that because functions are curried, the second set of
parentheses in the type description is not needed.
An example of using the flip’ function:
zipWith (flip’ div) [2,2,..] [10,8,6,4,2]
2022‐09‐28
Processing
Most of the advantages of functional programming use
operations on lists:
map’ :: (a ‐> b) ‐> [a] ‐> [b]
map’ _ [] = []
map’ f (x:xs) = f x : map’ f xs
map’ (replicate 3) [3..6]
map’ (map’ (^2)) [[1,2],[3,4,5,6],[7,8]]
map’ fst [(1,2),(3,4),(5,6),(7,8),(9,10)]
However, there is already the map function in Haskell.
Note that the following are equivalent:
map (+3) [1,2,3,4,5]
[x+3 | x <‐ [1,2,3,4,5]] Using the map function makes code a bit more readable, especially when applying maps of maps. 2022‐09‐28 A predicate is a function: • that inputs something • and results in `True` or `False` The filter function applies a predicate function • to the elements of a list • and creates a new list with only those elements that return `True` by the predicate. filter' :: (a ‐> Bool) ‐> [a] ‐> [a]
filter’ _ [] = []
filter’ p (x:xs)
| p x = x : filter’ p xs
| True = filter’ p xs
Again, there is a standard library filter function.
Some examples of using the filter function:
filter (>3) [1,5,3,2,6,4,6,3,1,2]
filter (==3) [1,2,3,4,5]
filter even [1..10]
let notNull x = not (null x)
in filter notNull [[1,2,3],[],[3,4,5],[2,2],[],[],[]]
2022‐09‐28
We did similar to filtering with list comprehensions,
but up to context and your taste for a readable style.
Applying many predicates:
• can be done through multiple `filter` calls
• or using logical `&&` operators in one `filter` call,
• or, finally, listing the predicates in a list comprehension
filter (<15) (filter even [1..20]) [x | x <‐ [1..20], x < 15, even x] Simplifying Another nice aspect of `filter` is that we can use it to simplify our `qsort` code: qsort :: (Ord a) => [a] ‐> [a]
qsort [] = []
qsort (x:xs) =
left = filter (<= x) xs right = filter (> x) xs
(qsort left) ++ [x] ++ (qsort right)
2022‐09‐28
largestDivisible = head (filter p [100000,99999..])
where p x = x `mod` 3829 == 0
The above example demonstrates:
• Haskell evaluates only what it needs to,
• being lazy, it only returns the first value satisfying predicate `p`
(because of `head` only returning one value).
takeWhile is a function similar to `filter`:
• returns a list for the first elements of input list that satisfy predicate
• and no elements after one is found to not satisfy predicate.
• see an example of how to parse the first word from a string:
takeWhile (/=’ ‘) “elephants know how to party”
An example involving quite a few nested functions:
sum ( takeWhile (<10000) (filter odd (map (^2) [1..])) ) 2022‐09‐28 Alternative to Nesting We can rearrange how function composition is written using the concept of piping: let a `pipe` b = flip ($) a b (map (^2)) [1..] (filter (odd)) (takeWhile (<10000)) There is also an alternative with an equivalent list comprehension version: sum (takeWhile (<10000) [m^2 | m <‐ [1..], odd (m^2)]) 2022‐09‐28 • begin with any natural number (1 or larger) for 𝑎 • if 𝑎 is 1, stop, otherwise: 𝑎 , 𝑎 even 3𝑎 1, 𝑎 odd • repeat with the resulting number Does the sequence that forms a chain always end in the • this is an open problem no one has solved yet • the largest value known to stop at 1 is 2^100000 ‐ 1 (as of 2018) • https://ieeexplore.ieee.org/document/8560077 The recursive function below creates Collatz chains: chain :: Integer ‐> [Integer]
chain 1 = [1]
| even n = n : chain (n `div` 2)
| True = n : chain (3*n + 1)
2022‐09‐28
Conjecture
• copyright: (YouTube) Coding Train
• Coding in the Cabana 2: Collatz Conjecture
• https://youtu.be/EYLWxwo1Ed8?t=1263
And we can count chains with more than 15 elements
(considering chains generated up to input integer 100):
numOfLongChains :: Int
numOfLongChains =
length (filter isLong (map chain [1..100]))
where isLong xs = length xs > 15
2022‐09‐28
Partially applied functions can be used to create functions
that take multiple parameters.
Combine this with Haskell’s laziness:
listOfFuns = map (*) [0..]
(listOfFuns !! 4) 5
• the first line returns a function for each element
• the last line pulls element at index `4` to apply its function
`(4*)` to the value `5`
It is often more concise to use anonymous functions known
as lambda functions. A simple example first:
(\x ‐> x + 2) 3
Then another example using lambda function as
parameter:
numLongChains :: Int
numLongChains = length (filter (\xs ‐> length xs > 15)
(map chain [1..100]))
Note that lambdas are expressions, so we can use them
anywhere expressions can be used.
2022‐09‐28
Use partial application to avoid using lambdas when it is
not even necessary, as seen in equivalent examples:
map (\x ‐> x + 3) [1, 2, 3]
map (+3) [1, 2, 3]
A few more involved examples with two parameters:
zipWith (\a b ‐> a + b) [6,5,4,3,2,1] [1,2,3,4,5,6]
Another example with pattern matching:
map (\(a,b) ‐> a + b) [(1,2),(3,5),(6,3),(2,6),(2,5)]
The textbook mentions no cases for lambdas directly, but
you can still use case constructs:
(\(a, b) ‐> case (a, b) of
(1, 2) ‐> 2
(3, 4) ‐> 7
(a, b) ‐> 1
The above example applies the lambda function
immediately to the pair (1, 2).
Keep in mind that if the match for a pattern fails,
a runtime error occurs.
2022‐09‐28
Emphasized
This example overemphasizes currying by way of
unnecessary lambda functions:
addThree’ :: Int ‐> Int ‐> Int ‐> Int
addThree’ x y z = x + y + z
addThree’ :: Int ‐> Int ‐> Int ‐> Int
addThree’ = \x ‐> \y ‐> \z ‐> x + y + z
Note that lambdas written without parentheses assume
everything to the right of `\` belongs to the lambda.
Implementation
There are times it is convenient to use flip.
But you could use a lambda to emphasize a function is
meant to be passed as an argument for:
• `map`, `zipWith`, `filter`, etc.,
flip’ :: (a ‐> b ‐> c) ‐> b ‐> a ‐> c
flip’ f = \x y ‐> f y x
Note that flip reads as if the parameters of the lambda
function are not being used until later.
map (flip subtract 20) [1, 2, 3, 4]
2022‐09‐28
Recursive functions are useful for:
• iterating over a list
• and evaluating some result
Haskell has a feature designed to facilitate this:
• this involves an accumulator value that helps process the list to
adjust value during each level of recursion
• it also needs a binary function that operates on the accumulator
and the next element of recursion in the list
• each recursive call uses the resulting accumulator value
repeatedly with the binary function and the next element
• and so on, until all elements are processed
sum’ :: (Num a) => [a] ‐> a
sum’ xs = foldl (\acc x ‐> acc + x) 0 xs
sum’ :: (Num a) => [a] ‐> a
sum’ xs = foldl (\acc x ‐> acc + x) 0 xs
Notice that the lambda function is not needed because of
sum’ :: (Num a) => [a] ‐> a
sum’ xs = foldl (+) 0 xs
Also, in general, if you have a function such as
`foo a = bar b a`
you can simplify it to
`foo = bar b`
2022‐09‐28
, there are right folds with `foldr`.
• the values in the binary function are applied in reverse order
• the list value is the first operand, and the accumulator is the second
For either left or right folds, the accumulator can be a
result of any type as per your design.
For example:
mapr :: (a ‐> b) ‐> [a] ‐> [b]
mapr f xs = foldr (\x acc ‐> f x : acc) [] xs
We could implement the above equivalently
with left fold:
mapr :: (a ‐> b) ‐> [a] ‐> [b]
mapr f xs = foldl (\acc x ‐> acc ++ [f x]) [] xs
2022‐09‐28
The `:` operation is more efficient than `++` operation, so
we mostly use folding on the right for processing lists.
Right folds work on infinite lists, whereas left folds do not.
Yet another implementation of the `elem` function:
elem’ :: (Eq a) => a ‐> [a] ‐> Bool
elem’ y ys = foldr (\x acc ‐>
if x == y then True else acc
) False ys
2022‐09‐28
First Element
Accumulation
`foldl1` and `foldr1` functions assume the accumulator is
the value of the first item in the list that they process.
Another implementation of `max`:
max’ :: (Ord a) => [a] ‐> a
max’ = foldl1 max
• partial application to help create functions
• the difficulty is in knowing that `foldl1` takes two parameters
• the second parameter is a list
Empty List
For your own implementations, you can see the
conciseness of `foldl1` and `foldr1` functions.
• choose them when the design of your function does not make sense
when given an empty list
• choose `foldl` and `foldr` when it does make sense to process an
empty list
2022‐09‐28
We have two implementations of reverse function:
reverse’ :: [a] ‐> [a]
reverse’ = foldl (\acc x ‐> x : acc) []
reverse’ :: [a] ‐> [a]
reverse’ = foldl (flip (:)) []
Multiplication will require the correct type class:
product’ :: (Num a) => [a] ‐> a
product’ = foldl (*) 1
2022‐09‐28
Another implementation of `filter`:
filterr :: (a ‐> Bool) ‐> [a] ‐> [a]
filterr p = foldr (\x acc ‐> if p x then x : acc else acc) []
Remember, the accumulator parameter is always ordered
on the side you are folding.
Finally, we give another implementation for the `last`
last’ :: [a] ‐> a
last’ = foldl1 (\_ x ‐> x)
2022‐09‐28
Right Fold
Operations
Suppose we want to apply a right fold with binary function
`f` on the list `[3,4,5,6]`.
• this can be seen as the expression
`f 3 (f 4 (f 5 (f 6 acc)))`
• the value `acc` is the starting accumulator value
• if `f` is replaced with `+` and `acc` starts with `0`,
• then the expression would be
`3 + (4 + (5 + (6 + 0)))`.
Operations
Consider a left fold with `g` as the binary function on the
same list:
g (g (g (g acc 3) 4) 5) 6
Replace `g` with the `flip (:)` binary function and begin
`acc` with an empty list `[]`, the expression becomes:
flip (:) (flip (:) (flip (:) (flip (:) [] 3) 4) 5) 6
Check an evaluation of the above and we have `[6,5,4,3]`.
2022‐09‐28
The `and’` function will combine Boolean elements of a list
together with the `&&` operator.
and’ :: [Bool] ‐> Bool
and’ = foldr (&&) True
Take special care to use the `foldr` function, and not the
`foldl` function, since the input could be an infinite list.
Circuiting
Because `&&` short circuits evaluation:
• if the first value is `False`,
• `foldr` on an infinite list with `and’` can short circuit,
• and completes once an element in the list results `False`.
• maybe a dangerous function since all the elements in an
infinite list could be `True`
Go ahead and try the expression:
and’ (repeat False)
2022‐09‐28
`scanl`/`scanr` functions are similar to
`foldl`/`foldr`
• they return a list with all of the intermediate accumulator values
from processing the input list
• of course, there are also the `scanl1` and `scanr1` functions
Try yourself and see the results:
scanl (+) 0 [3,5,2,1]
scanr (+) 0 [3,5,2,1]
scanl1 (\acc x ‐> if x > acc then x else acc)
[3,4,5,3,7,9,2,1]
scanl (flip (:)) [] [3,2,1]
The last accumulator value when using `scanl` will be in the
last element of the resulting list.
For `scanr`, the first element in the resulting list is the last
accumulator value.
2022‐09‐28
sqrtSums :: Int
sqrtSums = length (takeWhile (<1000) (scanl1 (+) (map sqrt [1..]))) Equivalently: sqrtSums :: Int sqrtSums = (map sqrt) [1..] `pipe` (scanl1 (+)) `pipe` (takeWhile (<1000)) `pipe` (length) sum (map sqrt [1..130]) sum (map sqrt [1..131]) Using $ to sqrt 3 + 4 + 9 can be equivalently written as (((sqrt 3) + 4) + 9) • the `$` operator applies a function, but with the lowest precedence in the expression • it is described with types as ($) :: (a ‐> b) ‐> a ‐> b
and defined as
f $ x = f x
• the definition does not make its usefulness explicit
sqrt $ 3 + 4 + 9
2022‐09‐28
Parentheses
Observe how $ can clean up nesting a bit:
sum (filter (> 10) (map (*2) [2..10]))
sum $ filter (> 10) (map (*2) [2..10])
sum $ filter (> 10) $ map (*2) [2..10]
Alternative
Perhaps you prefer use of `pipe`:
(map (*2) [2..10])
(filter (> 10))
2022‐09‐28
with $ as a
Another important use of $ is to tell Haskell to immediately
apply some function:
map ($ 3) [(4+), (10*), (^2), sqrt]
Note that the `($ 3)` function takes some other function
as input and applies that function to `3`.
Composition
𝑓 · 𝑔 𝑥 𝑓 𝑔 𝑥
Function composition in Haskell uses dot as operator:
(.) :: (b ‐> c) ‐> (a ‐> a) ‐> a ‐> c
f . g = \x ‐> f (g x)
map (\x ‐> negate (abs x)) [5,‐3,‐6,7,‐3,2,‐19,24]
map (negate . abs) [5,‐3,‐6,7,‐3,2,‐19,24]
Note that composition will require exactly one input.
2022‐09‐28
Associative
• function composition is right‐associative
• this is similar to our right folds, with
f (g (h x))
equivalently
(f . g . h) x
map (negate . sum . tail) [[1..5],[3..6],[1..7]]
Multiline:
We can make functions have one parameter with currying:
sum (replicate 5 (max 6.7 8.9))
(sum . (replicate 5) . max 6.7) 8.9
We can use multiline with layout syntax after dot operator
(do not use let keyword; this is not a definition; no need to indent):
(replicate 2 . product . map (*3) .
(zipWith max [1,2])) [4,5]
We cannot do so with $:
replicate 2 . product . map (*3) $ zipWith max [1,2] [4,5]
2022‐09‐28
Simplifying
Definitions
Recall that we had simplified creating functions by using
partially applied functions.
sum’ :: (Num a) => [a] ‐> a
sum’ = foldl (+) 0
We had removed a reference to `xs` on both sides of the
function equation to simplify it.
Simplifying
with . and $
Instead, Haskell has dot notation to help with creating a
function in what is termed point‐free style:
fn x = ceiling (negate (tan (cos (max 50 x))))
fn = ceiling . negate . tan . cos . max 50
We cannot just remove `x` on both sides
• because it does not make sense to express `cos (max 50)`
• that is, we cannot take the cosine of a function.
The second equivalent statement removes notation `x`.
2022‐09‐28
Point‐free
Now we rewrite `sqrtSum`
• sum of square roots for the first `n` integers
reaches a threshold of `1000` in point‐free form:
sqrtSum :: Integer
sqrtSum = length . takeWhile (<1000) . scanl1 (+) $ map (sqrt) [1..] demonstrates extreme consideration of reduction optimizations in realistic code: • https://www.youtube.com/watch?v=yRVjR9XcuPU • current research! 2022‐09‐28 — Chapter 6 — A module in Haskell is a file with some type classes, types, and functions defined inside. • a Haskell program is a collection of modules • some of the module contents can be exported for other Haskell programs to use • with more generic code, such as a module, it facilitates reuse 2022‐09‐28 The Haskell standard library is separated by modules, e.g.: • managing lists • concurrent programming • complex numbers • and more… The type classes, types, and functions we have used are part of the default imported Prelude module. To import modules: import Data.List 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com