Fall 2013, David Matuszek

# 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`.

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] -> Boo`l
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]"