Strict evaluation
Considering the function call
f a b, how would you force the strict evaluation ofa only,b only, andboth a and b?
- a only
f !a b
- b only
f a !b
- a and b
f !a !b
power
Computing the power of a number x can be achieved using the following function:
power :: (Integral a1, Num a) => a -> a1 -> a power x k = if k == 0 then 1 else if (k `mod` 2) == 0 then power (x*x) (k `div` 2) else x * power (x*x) (k `div` 2)
Perform a simple time and space efficiency analysis of the function.
First a rewriting which does not impact the analysis asked for.
power' :: (Integral a1, Num a) => a -> a1 -> a power' _ 0 = 1 power' x k | (k `mod` 2) == 0 = power' (x*x) (k `div` 2) | otherwise = x * power' (x*x) (k `div` 2)
Example of strict resolution:
- 23:
power 2 3 = 2 * power' (2*2) (3 `div` 2) -- 3 `mod` 2 /= 0 = 2 * power' 4 1 = 2 * 4 * power' (4*4) (1 `div` 2) = 2 * 4 * power' 16 0 = 2 * 4 * 1 -- by definition = 8
- 102
power 10 2 = power' (10*10) (2 `div` 2) -- 2 `mod` 2 == 0 = power' 100 1 = 100 * power' (100*100) (1 `div` 2) = 100 * power' 10000 0 = 100 * 1 -- by definition = 100
- time efficiency analysis
Step counting analysis:
Tpower _ 0 = 1 Tpower x k | (k `mod` 2) == 0 = 1 + T_x*x + T_kdiv2 + T_power(x*x) (k `div` 2) = 1 + 1 + 1 + Tpower | otherwise = T_x*x + T_kdiv2 + T_power(x*x) (k `div` 2) + Tx*power(x*x) (k `div` 2) = 1 + 1 + 1 + Tpower
O(k), with k the exponent
- space efficiency analysis
steps
Assume a list of length n in which every item requires O(m) steps to be computed. Suppose that the functions
length,headandsumneed to be applied to this list. How many steps would they take (in asymptotic terms) in each of the following cases:a) a lazy list,
b) a list in which all tails are strictly evaluated.
c) a list in which all heads and all tails are strictly evaluated.
tail-recursion
Consider the following program:
prodsum :: (Eq a, Num a) => a -> a prodsum x = prod x + sum x prod :: (Eq a, Num a) => a -> a prod 0 = 1 prod n = n * prod (n-1) sum :: (Eq a, Num a) => a -> a sum 0 = 0 sum n = n + sum (n-1)
a) Change the definition of
sumandprodinto tail-recursive ones.b) Using the Burstall-Darlington transformation system, write a new definition of
prodsum(using tuples) such that the result is computed in one pass.c) Change this definition into one that avoids using tuples and which is tail-recursive.