Test 1 Solutions: Questions
[6 pts]
Write a Haskell function nextHailstone
that takes an
integer parameter n and returns 3 n + 1 if n is odd
and n / 2 if n is even. (You can use Haskell's built-in
function even
that takes an integer parameter and returns
a Boolean reflecting whether the parameter is even.)
[8 pts]
Write a Haskell function times2UntilAbove1000
that takes
a parameter n and returns the first number above 1000 reached
as a result of doubling n repeatedly.
For example, given the parameter 400, your function should
return 1600, since 400 doubles once to arrive at 800 and a
second time to arrive at 1600.
Given the parameter 1001, your function should return simply
1001.
[10 pts]
Write a Haskell function iterateFunc
that, given
a one-parameter numeric functions f and an integer n as
parameters,
computes the numeric function which
applies f for n times to its parameter.
For example, iterateFunc sqrt 3
returns a function that computes the 8th root of its parameter
(since ((n½)½)½ = n1/8).
[6 pts]
Without using any identifiers to represent parameters,
write a Haskell function getOdd
that computes 2 n + 1
for a parameter n.
[8 pts] What is the most general possible type for the following Haskell function? Describe the type using Haskell syntax.
getFuncMin f x y = if f x < f y then x else y
[8 pts] Suppose we have the following data type.
data Expr = Const Integer | Add Expr Expr | Multiply Expr Expr
Write a function evaluate
that takes an Expr
parameter and evaluates the represented function.
For instance, in the following example calling the function,
we pass an argument representing the expression 2 ⋅ 3 + 5
so the function should return 11.
evaluate (Add (Multiply (Const 2) (Const 3)) (Const 5))
[10 pts]
Write a Haskell function sumDiffs
that takes a list of integers as a parameter
and returns the sum of absolute values of adjacent pairs in the list.
For instance, sumDiffs [1, 5, 3]
should return
|1 − 5| + |5 − 3| = 4 + 2 = 6.
[8 pts]
Without using recursion explicitly (instead relying on Haskell's built-in
list functions),
write a Haskell function sumDists
that, given a list of
pairs of real numbers representing points in the 2D plane,
returns the total of the points' distances from the origin.
For example, given the argument [(3,4), (0,3), (-2,0)]
,
the function should return 5 + 3 + 2 = 10
(since (3, 4) is (3² + 4²)½ = 5 units from the origin,
while (0, 3) is (0² + 3²)½ = 3 units away
and (−2, 0) is ((−2)² + 0²)½ = 2 units
away).
[8 pts] Without reference to any particular implementation of the abstract data type, how is a persistent stack different from a traditional stack?
[8 pts] Using applicative evaluation order, reduce the following lambda expression to irreducible form, showing every intermediate step.
(λf.λy.f (y + 1)) (λz.z²) ((λx.x + x) 3)
[8 pts] For imperative languages such as Java or Python, why is lazy evaluation order essentially not an option?
[12 pts] Which parameters of the following function are strict? Explain why or why not for each of the five parameters.
join f g h x0 x = if x < x0 then f (h x) else g (h x)
Test 1 Solutions: Solutions
nextHailstone n = if even n then n / 2 else 3 * n + 1
times2UntilAbove1000 n | n > 1000 = n
| otherwise = times2UntilAbove1000 (2 * n)
iterateFunc f 0 = \x -> x -- one solution
iterateFunc f n = \x -> (iterateFunc f (n - 1)) (f x)
iterateFunc f 0 = \x -> x -- another solution
iterateFunc f n = f . iterateFunc f (n - 1)
iterateFunc f n = foldl (.) (\x -> x) (map f [1..n]) -- another
getOdd = (+ 1) . (2 *)
Ord a => (b -> a) -> a -> a -> a
evaluate (Const x) = x
evaluate (Add e0 e1) = evaluate e0 + evaluate e1
evaluate (Multiply e0 e1) = evaluate e0 * evaluate e1
sumDiffs [] = 0
sumDiffs [x] = 0
sumDiffs (x0 : x1 : xs) = abs (x0 - x1) + sumDiffs (x1 : xs)
sumDists pts = sum (map (\(x, y) -> sqrt (x * x + y * y)) pts)
For a persistent stack, pushing or popping a value does not alter the existing stack but rather creates a pointer to a different stack with the values changed. However, the “new” stack may actually have a pointer into the “old” version where the structure is bound to be identical, in order to avoid the cost of copying values around.
(λf.λy.f (y + 1)) (λz.z²) ((λx.x + x) 3) | |
⇒ | (λy.(λz.z²) (y + 1)) ((λx.x + x) 3) |
⇒ | (λy.(λz.z²) (y + 1)) (3 + 3) |
⇒ | (λy.(λz.z²) (y + 1)) 6 |
⇒ | (λz.z²) (6 + 1) |
⇒ | (λz.z²) 7 |
⇒ | 7² |
⇒ | 49 |
Lazy evaluation renders it difficult to predict when a function call will actually be evaluated. Consider code like f(g(x)). In a lazy-evaluation language, g(x) will not actually be computed until f requires its parameter value. If f and g both have side effects (like displaying to the screen or changing some memory), then you could have some side effects of f occurring before the side effects of g and some after. Being able to understand the order in which side effects occur is essential to imperative programming.
Both x
and x0
are strict because the function must
first evaluate the x < x0
condition, which requires
both x
and x0
to be evaluated.
Both f
and g
are not strict because each may
be untouched depending on whether x < x0
. (If x < x0
,
g
is untouched; if not, then f
is untouched.)
Least obviously, h
is not strict, even though it
appears in both the then
and the else
.
Because Haskell is lazy, h
is not
actually used in the expression f (h x)
until f
actually needs it — but it could be that f
is a
function like \x -> 1
, which does not actually touch its
parameter at all, in which case h
would be untouched.