Microsoft PowerPoint – Week3.pptx
2022‐09‐21
Copyright By PowCoder代写 加微信 powcoder
Ch 3: Syntax in Functions
Ch 4: Hello, Recursion!
University of the Fraser Valley
COMP 481: Functional and Logic Programming
Chapter 3:
• pattern matching
• with tuples
• with list comprehensions
• as‐patterns
• where clauses
• local vs global scopes
• pattern matching with where
• functions in where blocks
• keyword let
• case expressions
Chapter 4:
• recursion
• recursive functions
• replicate
• quicksort
• designing with recursion
2022‐09‐21
— Pattern Matching —
• functions pattern match in a similar way conditional code
executes different branches or cases
• the following example defines a function to return different
lucky :: Int ‐> String
lucky 7 = “LUCKY NUMBER SEVEN!”
lucky x = “Sorry, you’re out of luck, pal!”
• calling the lucky function with input 7 will match the first
pattern describe
• calling lucky with any other input value will match with the last
pattern description
Consider how much more code it would take to write the following
function when required in a language that uses `if`‐statements.
2022‐09‐21
• order of cases matters, as having a pattern with variable `x` first
would match any input:
sayMe :: Int ‐> String
sayMe 1 = “One!”
sayMe 2 = “Two!”
sayMe 3 = “Three!”
sayMe x = “Not between 1 and 3!”
• notice the last case does not use argument `x`
• we could replace unused variables with underscore
• `_` is known as a temporary variable
• consider the factorial function but defined using recursion:
factorial :: Integer ‐> Integer
factorial 0 = 1
factorial n = n * factorial (n ‐ 1)
• If you try the above and call `factorial 50`,
what do you notice about the output?
• to call a function where the input does not match any of the
patterns will cause an exception
• then try to always describe a last pattern that will take care of all
other possible inputs
2022‐09‐21
— Pattern Matching with Tuples —
• consider defining a function in the two ways below:
let addVectors :: (Double, Double) ‐> (Double, Double) ‐> (Double, Double)
addVectors a b = (fst a + fst b, snd a + snd b)
let addVectors :: (Double, Double) ‐> (Double, Double) ‐> (Double, Double)
addVectors (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)
• the second version clearly has input tuples, increasing readability
2022‐09‐21
with Tuples
• we can make our own functions for pulling elements out of
triples, similar to `fst` and `snd` for pairs:
first :: (a,b,c) ‐> a
first (x, _, _) = x
second :: (a,b,c) ‐> b
second (_, y, _) = y
third :: (a,b,c) ‐> c
third (_, _, z) = z
— Pattern Matching with Lists —
2022‐09‐21
Pattern Matching
Comprehensions
let xs = [ (1,3),(4,3),(2,4),(5,3),(5,6),(3,1) ]
[ a+b | (a, b) <‐ xs ] • using pattern matching in the above list comprehension gives the result: [ 4, 7, 6, 8, 11, 4 ] • if one of the tuples in the list does not match the pattern, the list comprehension moves to the next tuple with Lists • we need to use parentheses around a pattern matched argument with parts • an example of returning a value regardless of what kind of list might be input: tell :: (Show a) => [a] ‐> String
tell [] = “List is empty!”
tell (x:[]) = “List has one element: ” ++ show x
tell (x:y:[]) = “List has two elements: ” ++ show x ++ ” and ” ++ show y
tell (x:y:_) = “Long list; 1st two items: ” ++ show x ++ ” and ” ++ show y
• keep in mind that `_` matches with any length list, even an empty list,
• the 2nd pattern matches for a list with exactly two elements
• so the last pattern only matches with lists of longer length.
2022‐09‐21
Pattern Matching
with Lists (2)
• a common pattern is `x:xs`, especially in recursive functions
• the above will match a singleton with the one head value as `x`
and the empty list as `xs`
• otherwise, `x` is the first element, and `xs` the tail
• `[]` can have elements added to the front of the list with `:`
• e.g.: re‐implementation of the `head` function:
• head’ (x:_) = x
• we can give an alternative pattern to simplify references
• prefix with a name you want to reference the whole pattern
• an example of using :
firstLetter :: String ‐> String
firstLetter “” = “Empty string, whoops!”
firstLetter = “The first letter of ” ++ all ++ ” is ” ++ [x]
2022‐09‐21
— Guards —
Guards (1)
• an example of using guards:
max’ :: (Ord a) => a ‐> a ‐> a
| x <= y = y | otherwise = x • the keyword `otherwise` can be replaced with Boolean value `True` 2022‐09‐21 Guards (2) • more complex cases can be used to define a function with the Sheffer stroke `|` as a “guard” • a guard begins successive lines and must be indented with at least one space • each guard is followed by a Boolean expression • if the expression result is `False`, the next guard will be tested • the expression among many guards that evaluates to `True` will be executed for the function • the last guard can take care of remaining cases with keyword `otherwise` in place of the Boolean expression • if no guards or patterns match, then an exception is thrown — where Clauses — 2022‐09‐21 where Clauses • guards can use variables defined in a final block of code starting with keyword `where` • these variables have a scope only inside the where block, so that any variable names do not pollute the global namespace tellRatio :: Double ‐> Double ‐> String
tellRatio x y
| r < zero = "That is a negative ratio." | r < small = "That is a fractional ratio." | r < substantial = "That is a substantial ratio." | r < large = "That is a large ratio!" | True = "Whatever, that ratio is ridiculously huge!" r = x / y; small = 1; substantial = 10; large = 100; where Clauses • note that you can leave out the braces `{ }` • and the semicolons `;` • but then the variables will need to be indented at least as far as the indentation of the `where` keyword 2022‐09‐21 — Local vs Global Scope — Local vs Global • beware that the `where` block has local scope • only for its immediately preceding guards, • and no previous function definitions or patterns messageHi = "Hello" messageBye = "Bye" greet :: String ‐> String
greet “Juan” = messageHi ++ “, Juan!”
greet “Fernando” = messageHi ++ “, Fernando!”
greet name = messageBye ++ “, ” ++ name ++ “!”
2022‐09‐21
— Pattern Matching with where—
• we could rewrite the ratio example to be more concise with pattern
matching used in the `where` clause
tellRatio :: Double ‐> Double ‐> String
tellRatio x y
| r < zero = "That is a negative ratio." | r < small = "That is a fractional ratio." | r < substantial = "That is a substantial ratio." | r < large = "That is a large ratio!" | True = "Whatever, that ratio is ridiculously huge!" (r, zero, small, substantial, large) = (x / y, 0, 1, 10, 100) 2022‐09‐21 Matching with • another example (but it could be done shorter with pattern matching in the function definition) initials :: String ‐> String ‐> String
initials firstname lastname = [f] ++ “. ” ++ [l] ++ “.”
f:_ = firstname
l:_ = lastname
— Functions in where Blocks —
2022‐09‐21
Functions in
where Blocks
• we may want to define a function in a `where` block to make use
of applying it to each element in a list
calcRatios :: [(Double, Double)] ‐> [Double]
calcRatios xs = [ratio x y | (x, y) <‐ xs]
ratio x y = x / y
— Keyword let—
2022‐09‐21
Keyword let
• the keyword `let` begins bindings to define variables you can
use elsewhere within another expression following `in` keyword
• the syntax is `let
cylinder :: Double ‐> Double ‐> Double
cylinder r h =
sideArea = 2 * pi * r * h
topArea = pi * r ^ 2
sideArea + 2 + topArea
where and let
• because `let` is an expression, you can use it anywhere an
expression can be used
• `where` must be used at the end of a function definition
• `let` expressions can define functions in a local scope
• let square x = x * x in (square 5, square 3, square 2)
• more than one binding can be included by separating them with
semicolons
• let a = 100; b = 200; c = 300 in a*b*c
• tuples make binding more concise
• (let (a,b,c) = (1,2,3) in a+b+c) * 100
• unfortunately, `let` expressions cannot be used across guards
due to their local scope
• some prefer `where` clauses to keep the function body closer to
its referenced name
2022‐09‐21
• going back to see the `tellRatio` example and we will replace the `where`
clause with a `let` expression:
calcLetRatios :: [(Double, Double)] ‐> [Double]
calcLetRatios xs = [ratio | (x, y) <‐ xs, let ratio = x / y] • we can use the `let` expression everywhere but in the generator part of the list comprehension, i.e.: `(x, y) <‐ xs` • it is also possible to specify further filters using the `let` expression: calcLetRatios :: [(Double, Double)] ‐> [Double]
calcLetRatios xs = [ratio | (x, y) <‐ xs, let ratio = x / y, ratio > 0.25]
— case Expressions —
2022‐09‐21
Expressions
• `case` keyword begins expressions much like the `let` keyword
head’ :: [a] ‐> a;
head’ xs = case xs of
[] ‐> error “No head for empty lists!”;
(x:_) ‐> x
• expressions such as `case` can be used many places 😇
• the first set of braces makes layout syntax unavailable
• so, lines are completed with semicolons
• OR just use layout syntax without braces for the whole
expression, but then we must use proper indentation
Expressions
• another example where a `case` is given further nested within
the description:
describeList :: [a] ‐> String
describeList ls = “The list is ” ++ case ls of {
[] ‐> “empty.”;
[x] ‐> “a singleton list.”;
xs ‐> “a longer list.”
• equivalently:
describeList :: [a] ‐> String
describeList ls = “The list is ” ++ what ls
what [] = “empty.”
what [x] = “has one element.”
what xs = “has many elements.”
2022‐09‐21
— Chapter 4: Hello, Recursion! —
The following are recursive functions to help practice all the
concepts learned so far.
max’ :: (Ord a) => [a] ‐> a
max’ [] = error “There is no maximum for an empty list!”
max’ [x] = x
max’ (x:xs) = max x (max’ xs)
2022‐09‐21
replicate’ :: (Eq b) => Int ‐> b ‐> [b]
replicate’ x y
| x <= 0 = [] | True = y:(replicate' (x ‐ 1) y) take' :: (Integral a, Eq b) => a ‐> [b] ‐> [b]
| n <= 0 = [] take' n (x:xs) = x : take' (n‐1) xs • note in the above that there is no `otherwise` or last `True` guard so that matching will move on to test the next pattern 2022‐09‐21 reverse' :: [a] ‐> [a]
reverse’ [] = []
reverse’ (x:xs) = (reverse’ xs) ++ [x]
repeat’ :: a ‐> [a]
repeat’ x = x : repeat’ x
• the above creates an infinite list of an element we pass in
• use in combination with another function that will cut off an
infinite number of the elements in some way
• we would really only want to use it together with `take`,
• for example, `take 5 $ repeat’ 3`
2022‐09‐21
zip’ :: [a] ‐> [b] ‐> [(a,b)]
zip’ _ [] = []
zip’ [] _ = []
zip’ (x:xs) (y:ys) = (x,y) : zip’ xs ys
elem’ :: (Eq a) => a ‐> [a] ‐> Bool
elem’ a [] = False
elem’ a (x:xs)
| a == x = True
| True = elem’ a xs
2022‐09‐21
—Quicksort —
qsort :: (Ord a) => [a] ‐> [a]
qsort [] = []
qsort (x:xs) =
left = [a | a <‐ xs, a <= x] right = [a | a <‐ xs, a > x]
(qsort left) ++ [x] ++ (qsort right)
2022‐09‐21
— Designing with Recursion —
How could smaller subproblem solutions be used
toward building up a larger problem solution?
• nothing to stop you from thinking in the reverse
• larger problem solution split to smaller subproblem solutions
• neither will work unless there is a true base case(s)
• tends to work well with data structures that can be
constructed with recursion
• general theorems could be reduced in scope by
restricting to data structures or subproblems to a
more specific kind that are then solved with recursion
2022‐09‐21
Thank You!
Questions?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com