代写代考 Microsoft PowerPoint – Week4.pptx

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