Sunday, May 3, 2009

[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 n1 , ..., nk is given by (n1 + ... + nk) / 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 a1a2a3 ... to a1a2a2a3a3a3 ....
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.

6 comments:

Anonymous said...

The path you have taken -- Practical Haskell to Logic Maths Programming -- is exactly what I have done! I couldn't restrain myself from remarking as much.

Best,

G-man

Sparky said...

Well in all honesty it is not my first choice.
Actually I started out with Real World Haskell (RWH), but after two chapters I switched to Yet Another Haskell Tutorial since it compressed most of the Haskell concepts. I did this because RWH used some constructs in the beginning and didn't explain them as well, but after YAHT, I was able to wade through it a lot easier.

I started working with HRtLMaP a few days ago since it has a lot more exercises that slowly build up rather than whole programs with too many ideas all squashed together.

Finally, thanks for the comment and all the best to you too. My hope is to learn enough so one day I can collaborate with other functional programmers and do bigger, better and more fun things!

Anonymous said...

Sparky,

As you have been developing your solutions to the HRtLMaP in EclipseFP, do you put each in it's own project? In other words what does your navigator look like for the HRtLMaP solution workspace?

Best,

G-Man

Sparky said...

G-Man:
Here is a pic on how I have things currently set up in Eclipse. I usually go one project per chapter and split the chapter files up. If the code is simple, I don't bother creating modules just for that. In addition, I am having difficulty linking modules within Eclipse. Not sure if it's a bug or there is some setting I am missing. I will try to look into that some more.

Where are you on reading? I just finished Ch2. But I have to go and redo it all over again, this time with some headache pills next to me :-)

Hope the pic answered your question, if not feel free to drop me a line and I will see what I can do to help.
~spk

Eric said...

To get the full benefit of studying Haskell, it is necessary to embrace both the functional and the lazy aspects of Haskell. A couple of your solutions miss opportunities to embrace those features.

Consider your solution to exercise 1.10. Your enhanced function signature is removeFst :: (a -> a -> Bool) -> a -> [a] -> [a]. Notice that the second argument is always used as an argument to the first argument (function). That is overly restrictive. Contrast it with this signature, removeFst :: (a->Bool) -> [a] -> [a]. This allows me to say "removeFst (==2) [1,2,3,1,2,3]". Notice that the first argument demonstrates the notion of a "computed" function (in this case "curried"). This new signature is also more flexible. Consider this call:

removeFst ((==4).length) $ words "Now is the time for all good men".

Your version can't do this because, when you supplied your own currying, you ended up placing unnecessary restrictions on the interface.

RWH also suggests that writing recursive functions should only be done as a last resort as they tend to be difficult to understand. Coming from the imperative world, this has been difficult for me as recursion was one of the few familiar ideas in the functional world. It has been worth the effort.

Consider exercise 1.14. It can be solved with basic function composition as follows:

blowup = concat . map rep . zip [1..]
where rep (i,c) = replicate i c

This takes advantage of an infinite list knowing that laziness saves me from nontermination. Coding in terms of infinite structures and function composition provides implicit decision points for your code and a cleaner result. I have found this one of the hardest lessons to learn in my Haskell journey (so far), but also one of the most valuable.

Good luck with your studies!

Anonymous said...

Currently reading through HRtLMP, The first, at least through ex 1.17, doesn't mention anything about map or zip. I'm assuming the author means for you to use recursion to solve these exercises, even if there are alternative solutions.