CIS 554 Haskell 1: Exercises
Fall 2013, David Matuszek

Purpose of this assignment

To help you understand functional programming languages

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.