Programs with “Branching” in © 2018 by . All Rights Reserved.
Learning Outcomes
by the End of the Lecture, Students that Complete
Copyright By PowCoder代写 加微信 powcoder
the Recommended Exercises should be Able to:
Implement Branching Algorithms using Guards Describe the Different Approachs to Branching Practice Creating Branching Programs Employ Print Debugging in © 2018 by . All Rights Reserved.
Reading and Suggested Exercises
Copyright © 2018 by . All Rights Reserved.
Read the following Chapter(s):
Chapter 4: “Guards, guards!” “Where!?” “Let it be”
Control Structures Control Structures are used to Direct the Flow of
Control of Individual Statements in a Program
a “Branch” in an algorithm allows the Control Flow to Proceed in One Direction in Some Situations and in Another Direction in All Other Situations
a “Loop” allows the Control Flow to Repeat Statements a Preset number of times or Until an Event Occurs
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures Guards are Conditions for specifying Alternative
Expressions for Different Evaluation Cases name :: Type1 -> Type2 -> Type3
name param1 param2
| guard1 = result1
| guard2 = result2
| otherwise = result3
this Exemplifies the Requirement that Functions must have Exactly One Output for Each Valid Input
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures the Use of Guards is Analogous to the
Function Definition Convention that uses Cases n.b., the absolute value function, for instance, is often written with this convention
𝐚𝐛𝐬𝒏 =ቊ𝒏 𝐢𝐟𝒏≥𝟎 −𝒏 𝐢𝐟𝒏<𝟎
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures
Guards are Not the Only approach for introducing Branching Structures into Haskell (but they are the Most Representative of the Paradigm)
General Condition Expressions can be written: if condition then m else n
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures Entailment is an Operation in Logic for which
there exists the Implication Operator (i.e., →) Truth Table
for Logical Implication
How could Implication be Implemented as a Function in Haskell?
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures first Create the Type Declaration:
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures first Create the Type Declaration:
implies :: Bool -> Bool -> Bool
then Create the Function Definition:
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures first Create the Type Declaration:
implies :: Bool -> Bool -> Bool
then Create the Function Definition:
implies x y
| (x == True && y == True) = True
| (x == True && y == False) = False | (x == False && y == True) = True | (x == False && y == False) = True
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures first Create the Type Declaration:
implies :: Bool -> Bool -> Bool
then Create the Function Definition:
implies x y
| (x == True && y == True) = True
| (x == True && y == False) = False | (x == False && y == True) = True | otherwise = True
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures first Create the Type Declaration:
implies :: Bool -> Bool -> Bool
then Create the Function Definition:
implies x y =
if ((x == True) && (y == False)) then False
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures first Create the Type Declaration:
implies :: Bool -> Bool -> Bool
then Create the Function Definition: implies x y = (not x) || y
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures the Contrapositive is a Property of Implication
that can be used for Testing 𝑨 → 𝑩 = ¬𝑩 → ¬𝑨
first Create the Type Declaration:
then Create the Function Definition: Copyright © 2018 by . All Rights Reserved.
Branching Control Structures the Contrapositive is a Property of Implication
that can be used for Testing 𝑨 → 𝑩 = ¬𝑩 → ¬𝑨
first Create the Type Declaration: testContrapose :: Bool -> Bool -> Bool
then Create the Function Definition: testContrapose x y = (implies x y == implies (not y) (not x))
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures
How would you Write a Function that takes Three Integer Arguments and Returns the Largest?
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures
maxOfThree :: Integer -> Integer -> Integer -> Integer
maxOfThree x y z
| (x >= y && x >= z) = x | (y >= x && y >= z) = y | (z >= x && z >= y) = z
Could this Design be Improved?
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures
maxOfThree :: Integer -> Integer -> Integer -> Integer
maxOfThree x y z
| (x >= y && x >= z) = x | (y >= z) = y
| otherwise = z
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures
maxOfThree :: Integer -> Integer -> Integer -> Integer
maxOfThree x y z
| (x >= y && x >= z) = x | (y >= z) = y
| otherwise = z
How would this Expression? maxOfThree 6 7 (2 + 3)
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures
maxOfThree 6 7 (2 + 3)
?? ~ 6 >= 7 && 6 >= (2 + 3) ?? ~ False && 6 >= (2 + 3) ?? ~ False
?? ~ 7 >= (2 + 3)
?? ~ 7 >= 5
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures the Trace of maxOfThree 6 7 (2 + 3) yields
Two Interesting Observations:
Subexpression 2 + 3 is Not Evaluated Immediately (despite being the “innermost” parentheses because the result is Not Immediately Required)
Comparison between 6 and 2 + 3 is Not Required at all
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures
How can we Confirm that the Previous Operations are indeed being Performed in the Order we Expected?
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures
Print Debugging (probably the first debugging style that you ever attempted) is Using Print statements to Display Variable Values, Procedure Invocations, etc. in order to Observe the Flow of Execution
in Haskell, the Debug Library contains a Trace function that can be Used for Print Debugging
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures
trace :: String -> a -> a
“when called, trace outputs the string in its first argument, before returning the second argument as its result.”
How can this be Used for Print Debugging? Copyright © 2018 by . All Rights Reserved.
foo a b = a + b
Try Changing… …Into…
Branching Control Structures
| trace (“foo ” ++ show a ++ ” ” ++ show b) False = undefined
foo a b = a + b
How does Haskell now Evaluate foo 1 2 (for instance)?
Copyright © 2018 by . All Rights Reserved.
Branching Control Structures
import Debug.Trace
maxOfThree :: Integer -> Integer -> Integer -> Integer maxOfThree x y z
| (gteq x y) && (gteq x z) = x | (gteq y z) = y
| otherwise = z
gteq :: Integer -> Integer -> Bool
gteq x y | trace (“gteq (” ++ show x ++ ” ” ++ show y ++ “)”) False = undefined gteq x y = (x >= y)
add :: Integer -> Integer -> Integer
add x y | trace (“add (” ++ show x ++ “, ” ++ show y ++ “)”) False = undefined add x y = (x + y)
Now Try maxOfThree 6 7 (add 2 3) Copyright © 2018 by . All Rights Reserved.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com