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