Test 1 Solutions

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

Problem X1.1.

[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.)

nextHailstone n = if even n then n / 2 else 3 * n + 1

Problem X1.2.

[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.

times2UntilAbove1000 n | n > 1000  = n

                       | otherwise = times2UntilAbove1000 (2 * n)

Problem X1.3.

[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^½)^½)^½ = n^1/8).

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

Problem X1.4.

[6 pts] Without using any identifiers to represent parameters, write a Haskell function getOdd that computes 2 n + 1 for a parameter n.

getOdd = (+ 1) . (2 *)

Problem X1.5.

[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

Ord a => (b -> a) -> a -> a -> a

Problem X1.6.

[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))

evaluate (Const x) = x

evaluate (Add e0 e1) = evaluate e0 + evaluate e1

evaluate (Multiply e0 e1) = evaluate e0 * evaluate e1

Problem X1.7.

[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.

sumDiffs [] = 0

sumDiffs [x] = 0

sumDiffs (x0 : x1 : xs) = abs (x0 - x1) + sumDiffs (x1 : xs)

Problem X1.8.

[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).

sumDists pts = sum (map (\(x, y) -> sqrt (x * x + y * y)) pts)

Problem X1.9.

[8 pts] Without reference to any particular implementation of the abstract data type, how is a persistent stack different from a traditional stack?

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.

Problem X1.10.

[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)

(λ`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

Problem X1.11.

[8 pts] For imperative languages such as Java or Python, why is lazy evaluation order essentially not an option?

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.

Problem X1.12.

[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)

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.