For this exercise, put all of your function definitions in a file exer5.hs. You must include an appropriate type declaration (::) for each function you define in your exer5.hs.

Built-In Functions

There are many useful functions that come with the language, but most of them are actually fairly simple to implement recursively. Let's prove that by doing a few.

Write a recursive function myWords that behaves identically to the built-in words.

• Write a recursive function myIterate that behaves identically to the built-in iterate.
• Write a recursive function mySplitAt that behaves identically to the built-in splitAt (except don't worry about the position<0 case).

Rational Numbers

In the Haskell standard library, there is a module Data.Ratio that can be used to be represent rational numbers with the type Ratio Int. A Ratio Int value can be constructed with the % operator: 2%7 represents the fraction 2/7.

Write a function rationalSum that produces a list of all rational numbers whose numerator and denominator add to the given argument.

ghci> rationalSum 5
[1 % 4,2 % 3,3 % 2,4 % 1]
ghci> rationalSum 8
[1 % 7,1 % 3,3 % 5,1 % 1,5 % 3,3 % 1,7 % 1]
ghci> rationalSum 1
[]

Note that rational values are displayed in lowest-terms. The values displayed in the above example for rationalSum 8 are \(\frac{1}{7}\), \(\frac{2}{6}=\frac{1}{3}\), \(\frac{3}{5}\), \(\frac{4}{4}=\frac{1}{1}\), \(\frac{5}{3}\), \(\frac{6}{2}=\frac{3}{1}\), \(\frac{7}{1}\).

Your implementation should be \(O(n)\), not \(O(n^2)\).

Lowest Terms Only

Make another version of the above function called rationalSumLowest that produces the same fractions, but only the values are are already in lowest-terms.

ghci> rationalSumLowest 5
[1 % 4,2 % 3,3 % 2,4 % 1]
ghci> rationalSumLowest 8
[1 % 7,3 % 5,5 % 3,7 % 1]
ghci> rationalSumLowest 12
[1 % 11,5 % 7,7 % 5,11 % 1]

Hint: there is a built-in function gcd that calculates the greatest common divisor of its arguments.

All Rational Numbers

Use the rationalSumLowest function to construct a list rationals that contains all positive rational numbers exactly once.

ghci> take 20 rationals
[1 % 1,1 % 2,2 % 1,1 % 3,3 % 1,1 % 4,2 % 3,3 % 2,4 % 1,1 % 5,5 % 1,1 % 6,2 % 5,3 % 4,4 % 3,5 % 2,6 % 1,1 % 7,3 % 5,5 % 3]
ghci> elem (8%7) rationals
True
ghci> elem (8%16) rationals
True
ghci> elem (251%1237) rationals  -- make take a few seconds
True
ghci> elem (-1%2) rationals
-- infinite loop

If you actually do something infinite, you can press control-C to stop a runaway calculation.

[With any luck, you are now convinced that the set of integers and set of rational numbers have the same cardinality, but that's another course.]

Input/Output

Write a function sumFile :: IO () that reads a file input.txt. The file will contain integers, one per line. You should add up the numbers and print the result. Use my sample input.txt if you like.

ghci> sumFile 
164

[I know that returning and printing look the same in GHCi, but trust me: this prints.]

Hints: readFile; write a function that splits a string into lines (around the '\n' character); the function read will convert a string to an integer as long as you're explicit about the type you want returned; as said in lecture, keep as much logic as possible away from the monad.

Here are some hints that may be useful:

-- split a list around a given separator value
splitAtSeparator :: Eq a => a -> [a] -> [[a]]
splitAtSeparator sep [] = []
splitAtSeparator sep content = first : splitAtSeparator sep rest
    where
    first = takeWhile (/= sep) content
    firstlen = length first
    rest = drop (firstlen+1) content

-- convert an integer-like string to an integer
readInt :: String -> Int
readInt = read

Submitting

Submit your files through CourSys for Exercise 5.