CIS 554 Haskell 1: Exercises
Fall 2013, David Matuszek

Purpose of this assignment

Details

How to read type declarations

In the Haskell REPL, :t thing will tell you the type of thing. Here are some examples:

Type Interpretation
not :: Bool -> Bool not is a function that, given a boolean value, returns a boolean value.
head :: [a] -> a head takes a list of some arbitrary type a, and returns a value of type a.
mod :: Integral a => a -> a -> a mod takes two values of type a, which must be an Integral type, and returns a value of type a.
map :: (a -> b) -> [a] -> [b] map takes a function from a to b, and a list of a, and returns a list of b.

Haskell exercises

Write the following functions. Where built-in equivalents exist, do not define a function in terms of the equivalent built-in function. For example, don't say let member = elem. (You can use elem in other definitions, though.)

The following functions can all be defined in a single line, so try to do so. They do not need to work for infinite lists.

member :: Eq a => a -> [a] -> Bool
Returns True if the element occurs in the list.
count :: (Num a, Eq a1) => a1 -> [a1] -> a
Counts the number of times a value occurs in a list.
forall :: (a -> Bool) -> [a] -> Bool
Tests whether all elements of a list satisfy a given condition.
exists :: (a -> Bool) -> [a] -> Bool
Tests whether any element of a list satisfies a given condition.
single :: (a -> Bool) -> [a] -> Bool
Tests whether exactly one element of a list satisfies a given condition.
mostly :: (a -> Bool) -> [a] -> Bool
True if there are more elements in the list that satisfy the predicate than elements that fail to satisfy the predicate.
majority :: [Bool] -> Bool
True if the list contains more Trues than Falses (if equal, result is False).
The following functions vary in length and difficulty, but are grouped together because they almost all deal, in one way or another, with series.
collatz1 :: Int -> Int
Make one step in the Collatz sequence. Collatz1 of 1 is 1; collatz1 of an even number is half that number; and collatz1 of an odd number is three times the number plus one.
collatz :: Int -> Int
Collatz of 1 is 1; collatz of any other number is the collatz of the collatz1 of that number.
isFixpoint :: (Eq a) => (a -> a) -> a -> Bool
A fixpoint of a function f is a value x such that f x = x. This function should return True if its second argument is a fixpoint of its first argument.
findFixpoint :: (Eq a) => (a -> a) -> a -> Int -> Maybe a
For some functions (e.g. collatz), repeated application of the function (that is, f(f(f(...x...))) ) will yield a fixpoint. Integer divide by 2 is another such function. findFixpoint f x limit will try to find a fixpoint of f, starting with x. If it succeeds, it will return Just y, where y is the fixpoint. If it fails to find a fixpoint after limit applications of f, it will return Nothing.
tooBig :: Float -> Bool
Returns True if the given argument is greater than 0.00001.
nearlyEqual :: Float -> Float -> Bool
Returns True if the given values are nearly equal. Do this by dividing one number by the other and checking if the result is in the range 0.9999 to 1.0001. Beware of division by zero.
series :: (Int -> Float) -> Int -> [Float]
Given a function f and an initial value i, return the infinite series [f(i), f(i+1), f(i+2), f(i+3), ...].
seriesSum :: (Int -> Float) -> Int -> [Float]
Given a function f and an initial value i, return the infinite series [f(i), f(i)+f(i+1), f(i)+f(i+1)+f(i+2), f(i)+f(i+1)+f(i+2)+f(i+3), ...].
On Wikipedia, http://en.wikipedia.org/wiki/Convergent_series, you will find "Examples of convergent and divergent series." Write functions that use seriesSum to compute the values of each of the listed convergent series. You can stop the summation when the terms become smaller than 0.00001. Name your methods computeLn2, computePiOver4, computeTwo, computeE, computePiSquaredOver6, computeTwoByPowers, computeTwoThirds, and computePhi. For many of these you will need to write additional functions.

Testing

Provide tests for the above functions. Haskell does not come with a testing framework, and I would rather not ask you to download and install one, so here's a very small framework for you to use.

assertTrue :: Bool -> String -> IO ()
assertTrue x claim = if x
                       then putStrLn claim
                       else putStrLn $ "*** Untrue: " ++ claim   

assertFalse :: Bool -> String -> IO ()
assertFalse x claim = assertTrue (not x) claim  

assertEqual :: (Eq a, Show a) => a -> a -> IO ()
assertEqual x y = if x == y
                    then putStrLn $ (show x) ++ " equals " ++ (show y)
                    else putStrLn $ "*** " ++ (show x) ++ " does not equal " ++ (show y)
And here is a brief example of its use:
main = do
  assertTrue (member 3 [1, 2, 3, 4]) "3 is in the list [1, 2, 3, 4]"
  assertFalse (member 7 [1, 2, 3, 4]) "7 is not in the list [1, 2, 3, 4]"
  assertEqual 3 (count 'a' "abracadabra")

Due date

Your program is due before 6am Wednesday, October 16. Submit via Canvas.