Assignment 2: Recursion-free Haskell
Due: 5:00pm, Friday, September 7. Value: 30 pts.
As we've seen, using Haskell's built-in list functions often results in simpler, easier-to-understand code than writing recursive versions. Below are recursive implementations for several functions; your job is to develop non-recursive list-based implementations of the functions. Your implementations must maintain the O(n) performance of the originals.
For example, given the following function:
factorial 0 = 1
factorial n = n * factorial (n - 1)
Your solution might be:
factorial n = product [1..n]
You may find the official documentation of list functions helpful.
import Data.List
-- Returns 1/1 + 1/2 + 1/3 + 1/4 + ... + 1/n
harmonic :: Integer -> Double
harmonic 1 = 1
harmonic n = 1.0 / fromInteger n + harmonic (n - 1)
-- Returns an approximation of the integral of f between a and b by
-- dividing the interval (a,b) into n equal-sized portions.
trapezoid :: (Double -> Double) -> Double -> Double -> Integer -> Double
trapezoid f a b 0 = 0
trapezoid f a b n = 0.5 * (f a + f a') * delta + trapezoid f a' b (n - 1)
where delta = (b - a) / fromInteger n
a' = a + delta
-- Returns True if each value in the list is more than the previous value.
-- Ex: increasing [2,3,5,7] is True; increasing [2,3,3,5] is False.
increasing :: Ord a => [a] -> Bool
increasing [] = True
increasing [_] = True
increasing (x0 : x1 : xs) = x1 > x0 && increasing (x1 : xs)
-- Format an integer with commas separating each group of three digits.
-- Ex: fmtCommas 1048576 is "1,048,576"
fmtCommas :: Integer -> [Char]
fmtCommas n = fst (addCommas (show n))
where addCommas [] = ("", 0)
addCommas (c:cs) = if size == 3 then (c : ',' : rest, 1)
else (c : rest, size + 1)
where (rest, size) = addCommas cs