CIS 554 Haskell 1: Exercises
Fall 2015, 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, preceding each function with the given type declaration. 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. (Hint: Remember that map results in a list of the same length, filter results in a potentially shorter list, and foldl results in a single value.)

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.
first :: (a -> Bool) -> [a] -> Maybe a
Finds the first element of a list that 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.
mostlyTrue :: [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.
majority :: Eq a => [[a] -> Maybe a
Find, in linear time, the majority element in a list (the element that occurs more than half the time), or Nothing if there is no majority element. See http://www.cs.utexas.edu/~moore/best-ideas/mjrty/ for the clever two-pass algorithm to do this.
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.0001.
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 compute the values of each of the listed convergent series. You can stop the summation when the terms become smaller than 0.0001. Name your methods computeLn2,, computeTwo, computeE, computePiSquaredOver6, computeTwoByPowers, computeTwoThirds, and computePhi computePsi. You can use seriesSum, and for some of these you may need to write additional functions.
Lazy sequences in Haskell are powerful, but can be a bit difficult to understand at first The following represents the Fibonacci series:
     *Main> let fibonacci = 1 : 1 : (zipWith (+) fibonacci (tail fibonacci))
     *Main> take 10 fibonacci
     [1,1,2,3,5,8,13,21,34,55]
For an explanation of this function, see http://scienceblogs.com/goodmath/2006/11/28/simple-functions-in-haskell-1/.

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. Tests are required for all the assigned functions.

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 Monday, October 26. Submit via Canvas.