[2009.05.03] The Haskell Road to Logic, Math and Programming [Exercises 1.09 – 1.14]

I started learning Haskell a few weeks ago by reading Real World Haskell and following the examples they have there. However, personally, some of the material was a bit more than I expected, so I decided that I should at least scale back my approach and try to work on some other Haskell type programming problems. As such, I began reading "The Haskell Road to Logic, Math and Programming" by Kees Doets and Jan van Eijck. While I have asked and not yet received the list of solutions to the exercises as of this writing (May 03 2009), I have decided that as I work the exercises, I will post my solutions to the problems. This will help me understand Haskell as well as others who are in my position.

NOTE: I will not post every single exercise, as some may either too trivial or examples stated in the book. Unfortunately, I will not be able to bring in code that is nicely colored as in my F# posts, as I have not yet found a good Eclipse plugin that will export Haskell code to HTML.

Here is the listing for Exercises 1.09 - 1.14.

EXERCISES

Exercise 1.09: Define a function that gives the maximum of a list of integers. Use the predefined function max.

Exercise 1.09 solution:

-- type definition
myMax :: [Int] -> Int
myMax [] = error "empty list"
-- base case for singleton list
myMax [x] = x
-- remove the first element of the list and compare it to
-- the recursive result of the rest of the list
myMax (x:xs) = max x (myMax xs)

Exercise 1.10: Define a function removeFst that removes the first occurrence of an integer m from a list of integers. If m does not occur in the list, the list remains unchanged.
NOTE: After I wrote my version, I remembered that the Haskell library has a similar function in the Data.List module called deleteBy. I liked that version better as it was more flexible than what was asked for so I implemented mine the same way which is basically what is in the module.

Exercise 1.10 solution:

-- eq is a predicate to use to make the comparison
-- in this case, when executing the function,
-- you can use (==) as the predicate
-- Ex: removeFst (==) 2 [1,2,3,4,2] and get [1,3,4,2]

-- type definition
removeFst :: (a -> a -> Bool) -> a -> [a] -> [a]
-- base case, empty list returns empty list
removeFst eq x (y:ys) =
    if x `eq` y
    then ys
    else y : removeFst eq x ys

Example 1.11: We define a function that sorts a list of integers in order of increasing size, by means of the following algorithm:

• an empty list is already sorted.
• if a list is non-empty, we put its minimum in front of the result of sorting the list that results from removing its minimum.

Even though this is given as an example in the book, I have replicated it here with some minor adjustments to highlight some additional features, namely using the built in minimum function and replacing parenthesis with point-free programming style.

Example 1.11 solution:

-- Find the minimum of the list, remove it and
-- append it to the result of recursively calling
-- the rest of the list members

-- type definition
srtInts :: [Int] -> [Int]
srtInts [] = [] -- base case
srtInts xs =
    let m = minimum xs
    in m : (srtInts . removeFst (==) m) xs -- [1]
   
-- NOTE: [1] can be traditionally be written as:
    m : (srtInts (removeFst (==) m xs))

Example 1.12: Here is a function that calculates the average of a list of integers. The average of m and n is given by (m + n) / 2, the average of a list of k integers n₁ , ..., n_k is given by (n₁ + ... + n_k) / k.
Again here I have my own implementation, using the built in foldl function rather than sum and using realToFrac to convert from Int to Float.

Example 1.12 solution:

-- type definition
myAvg :: [Int] -> Float
myAvg [] = error "empty list"
myAvg xs =
    realToFrac (foldl (+) 0 xs) / realToFrac (length xs)

Exercise 1.13: Write a function count for counting the number of occurrences of a character in a string. In Haskell, a character is an object of type Char, and a string an object of type String, so the type declaration should run:
count :: Char -> String -> Int.

Exercise 1.13 solution:

-- define an auxiliary function to get a list
-- of similar characters
count' :: Char -> String -> [Char]
count' _ "" = []
count' x (y:ys) =
    if x == y
    then y : count' x ys
    else count' x ys

-- use our main function to get the length
-- of the list returned by the auxiliary function
count :: Char -> String -> Int
count x = (length . count' x) -- point free style

Exercise 1.14: A function for transforming strings into strings is of type String -> String. Write a function blowup that converts a string a₁a₂a₃ ... to a₁a₂a₂a₃a₃a₃ ....
blowup "bang!" should yield "baannngggg!!!!!". (Hint: use ++ for string concatenation.)

Haskell has its own replicate function but for my own benefit, I decided to write my own (and no I didn't peek at the source code at all), called myReplicate which takes an integer and a type of object and creates a list of objects based on the input integer. In addition, I have added an auxiliary function called blowup' which is used to abstract additional computations required to make the function work correctly.

Exercise 1.14 solution:

-- type definiton
blowup :: [a] -> [a]
blowup xs = blowup' 1 xs

-- type definition
myReplicate :: Int -> a -> [a]
myReplicate 0 _ = [] -- no replication
myReplicate n x = x : myReplicate (n-1) x

-- type defintion
blowup' :: Int -> [a] -> [a]
blowup' _ [] = []
blowup' n (x:xs) =
    myReplicate n x ++ blowup' (n+1) xs

This was a complete and utter pain to format and try to colorize even a little bit. But the fact that I am taking the time to make this look more appealing should indicate my passion for this stuff.