12/08/2020 Quiz (Week 5)
Quiz (Week 5)
E ects and Purity Question 1
Which of the following C functions would be considered pure?
1. ✔
2. ✗
3. ✗
4. ✗ strcpy()
sqrt()
printf()
rand()
Computing a square root is pure, as the result depends solely on the input to the function. Indeed, the square root is a function in the mathematical sense and therefore is, by de nition, pure.
The printf() function is not pure as it performs I/O, a type of effect.
The rand() function is not pure as each time it is evaluated it can return different
results. That is, the results are not dependent solely on the input arguments. The strcpy() function is impure as it mutates its arguments.
Question 2
Imagine we had a function adder that added on to a running total each time it was called:
*> adder 7
7
*> adder 10
17
*> adder 0
17
*> adder 7
24
Why is adder impure?
www.cse.unsw.edu.au/~cs3141/20T2/Week 05/Quiz.html
1/7
12/08/2020 Quiz (Week 5)
1. ✗ It performs I/O
2. ✗ It manipulates memory
3. ✔ It does not depend solely on its arguments 4. ✗ It doesn’t indicate effects in its type
The adder function does not perform I/O, it does manipulate memory (but so do pure functions), and its type is neither here nor there. The thing that makes it impure is that the expression adder x does not always mean the same thing for a given x . That is, it depends on some internal state in addition to its argument. Thus option 3 is the correct answer.
Question 3
Which of the following effects is considered an internal effect?
1. ✗ Modifying global variables 2. ✗ Drawing on the screen
3. ✔ Modifying local variables 4. ✔ Allocating a data structure 5. ✗ Throwing an exception
Modifying global variables can have a non-local in uence on other parts of the program, therefore is not internal. Drawing on the screen similarly is not internal as its effect can clearly be observed from outside the function. Modifying local variables is internal as no other part of the program can observe the modi cation (neither can the user). Allocating data structures is also considered internal (under the common abstraction that we have in nite memory) as such an allocation also cannot be observed externally. Throwing an exception can be observed externally, however (by catching it), and thus is not an internal effect.
Question 4
What does the type IO Int signify?
1. ✗ An embedded program that may perform side effects before returning an Int 2. ✗ A function from the abstract state of the RealWorld to a pair of the
RealWorld state and an Int .
3. ✗ An effectful computation that produces an Int . 4. ✔ All of the above views are valid interpretations
www.cse.unsw.edu.au/~cs3141/20T2/Week 05/Quiz.html
2/7
12/08/2020 Quiz (Week 5)
IO and State Question 5
Imagine we had the following IO based API for manipulating a robot:
We wish to write a program that will move forward unless obstructed , in which case the robot should turn towards the L direction.
Which of the following is a type-correct implementation of the above procedure? 1. ✔
data Direction = L | R
forward :: IO ()
obstructed :: IO Bool
turn :: Direction -> IO ()
robot = do
sensed <- obstructed
if sensed
then turn L
else forward
robot
2. ✗
GHC internally models as being the same as a type:
IO a
IO a =~ RealWorld -> (RealWorld, a)
This is a common view of IO and option 2, but perhaps a more common view of is that it denotes embedded programs. For example,
Could be viewed as a type representing an (effectful) program that will produce a Char when executed. This helps us to view IO as a type just like any other, and
one that we can pass into and return from functions just like Maybe Int or [Int] .
IO
getChar :: IO Char
www.cse.unsw.edu.au/~cs3141/20T2/Week 05/Quiz.html
3/7
12/08/2020 Quiz (Week 5)
3. ✗
robot = do
let sensed = obstructed
if sensed
then turn L
else forward
robot
4. ✗
robot = do
sensed <- obstructed
if sensed
then turn L
robot
else forward
robot
Option 1 is correct. Option 2 uses an ( ) where a is required (in the if ). Option 3 uses to bind to . That is,
IO Bool
obstructed
now has type if . Option 4 places the
and forward , but without the Haskell would parse this as
, which once again is incorrectly used within the looping call at the same indentation as turn L
keyword they do not form a block and so which is not well-typed.
let
sensed
obstructed
Bool
sensed
IO Bool
robot
do
turn L robot
Question 6
Check all of the following programs that are equivalent to the IO action a :
1. ✔
2. ✔ a = getLine >>= \x -> putStrLn (filter isDigit x) >>= \_ -> a
a = do x <- getLine
putStrLn (filter isDigit x)
a
a = getLine >>= putStrLn . filter isDigit >> a
robot = do
if obstructed
then turn L
else forward
robot
www.cse.unsw.edu.au/~cs3141/20T2/Week 05/Quiz.html
4/7
a = (getLine >>= \x -> putStrLn (filter isDigit x)) >>= a
a = do getLine >>= \x -> putStrLn . filter isDigit; a
a = do x <- getLine; putStrLn . filter isDigit; a
a = do x <- getLine; putStrLn . filter isDigit $ x; a
a = do getLine >>= \x -> putStrLn (filter isDigit x); a
Options 3,4, and 5 don’t type-check. The others are all equivalent.
Bool -> State String () -> State String ()
State String
State
get :: State String String
put :: String -> State String ()
runState :: State String a -> String -> (String, a)
leftPad :: Int -> State String ()
leftPad l = while ((< l) . length) $ do
str <- get
put (' ':str)
while
State String Bool -> State String () -> State String ()
(Bool -> State String ()) -> State String ()
(String -> Bool) -> State String ()
(String -> Bool) -> State String () -> State String ()
while
Bool
String
State String
()
State String ()
12/08/2020
3. ✗ 4. ✗ 5. ✗ 6. ✔ 7. ✔
Question 7
Below is an example of a small program using basic API for :
Now, our program will repeatedly pad a string with spaces until it reaches a certain length:
What is the type of
in this example?
1. ✗ 2. ✗ 3. ✗ 4. ✗ 5. ✔
The
loop takes a state-dependent conditional, i.e a function that returns a for a given , and a stateful action for the loop body,
Quiz (Week 5)
. As a refresher, here’s the
, nally producing a stateful action that runs the loop, , hence option 5 is correct.
Question 8
www.cse.unsw.edu.au/~cs3141/20T2/Week 05/Quiz.html
5/7
Q
12/08/2020 Quiz (Week 5)
Here is a program to detect if a string has balanced parentheses, ignoring all other characters.
matching :: String -> Int -> Bool
matching [] n = (n == 0)
matching (‘(‘:xs) n = matching xs (n+1)
matching (‘)’:xs) n = n > 0 && matching xs (n-1)
matching (oth:xs) n = matching xs n
Which of the following is an accurate translation of the above program to use the
State type? 1. ✗
matching xs = snd (runState (go xs) 0) == 0
where
go [] = pure True
go (x:xs) | x == ‘(‘ = modify (+1) >> go xs
| x == ‘)’ = modify (-1) >> go xs
| otherwise = go xs
2. ✗
matching xs = snd (runState (go xs) 0) == 0
where
go [] = pure True
go (x:xs) | x == ‘(‘ = modify (+1) >> go xs
|x==’)’ =don<-get
if n > 0 then put (n – 1) >> go xs
| otherwise = go xs
else pure False
3. ✗
matching xs = fst (runState (go xs) 0)
where
go [] = pure True
go (x:xs) | x == ‘(‘ = modify (+1) >> go xs
|x==’)’ =don<-get
if n > 0 then put (n – 1) >> go xs
| otherwise = go xs
else pure False
4. ✗
www.cse.unsw.edu.au/~cs3141/20T2/Week 05/Quiz.html
6/7
12/08/2020 Quiz (Week 5)
5. ✔
matching xs = fst (runState (go xs) 0)
where
go [] = get >>= pure . (== 0)
go (x:xs) | x == ‘(‘ = modify (+1) >> go xs
|x==’)’ =don<-get
if n > 0 then put (n – 1) >> go xs
| otherwise = go xs
else pure False
Option 1 checks if the nal count is zero, but does not check if the count sinks below zero at any point, matching the strings )( for example. Option 2 does check if the count drops below zero, but then doesn’t do anything with that information. Option 3 only checks if the count drops below zero, and not that the count is zero at the end. Option 4 does check both the boolean and the count at the end, however does not set the boolean to false when the count drops below zero. Option 5 does all the required checks and is therefore correct.
Submission is already closed for this quiz. You can click here to check your submission (if any).
matching xs = let (b,n) = runState (go xs) 0
in b && n == 0
where
go [] = pure True
go (x:xs) | x == ‘(‘ = modify (+1) >> go xs
| x == ‘)’ = modify (-1) >> go xs
| otherwise = go xs
www.cse.unsw.edu.au/~cs3141/20T2/Week 05/Quiz.html
7/7