Sunday, May 10, 2009

[2009.05.10] The Haskell Road to Logic, Math and Programming [Exercises 1.15 – 1.21]

Listing for Exercises 1.15, 1.16, 1.17, 1.20, 1.21

Exercise 1.15: Write a function srtString :: [String] -> [String] that sorts a list of strings in alphabetical order.

Exercise 1.15 solution:
Actually this is a pretty simple solution which could have been realized from Example 1.11. All I have to do is modify the type signature to make it a generalized/ polymorphic type that derives from the Ord class. In addition, this function uses the removeFst function from Exercise 1.10.
-- type definition
srtStrings :: (Ord a) => [a] -> [a]
srtStrings [] = [] -- base case
srtStrings xs =
    let m = minimum xs
    in m : (srtStrings . removeFst (==) m) xs -- [1]
-- NOTE: [1] can be traditionally be written as:
-- m : (srtInts (removeFst (==) m xs))

Example of Use:
*Main> (srtStrings . words) "this will be a sorted line"
--NOTE: I used the words function to split the line at whitespaces to create the array of Strings.

Example 1.16: Suppose we want to check whether a string str1 is a prefix of a string str2. Then the answer to the question prefix str1 str2 should be either yes (true) or no (false), i.e., the type declaration for prefix should run:
prefix :: String -> String -> Bool.
Prefixes of a string ys are defined as follows:

  1. [] is a prefix of ys,
  2. if xs is a prefix of ys, then x:xs is a prefix of x:ys,
  3. nothing else is a prefix of ys.
Exercise 1.16 solution:
My implementation is a bit different than what was asked for as it is more generalized and as such, can be used for other types, not just strings. In addition, the predicate is used to describe the comparison function being used to test the prefix and the rest of the list.
prefix :: (a -> a -> Bool) -> [a] -> [a] -> Bool
prefix _ xs [] = False -- 2nd list cannot be empty
prefix _ [] ys = True -- [] is prefix of a non-empty one
prefix eq (x:xs) (y:ys) = (x `eq` y) && prefix eq xs ys

Example of Use:
*Main> prefix (==) "this" "this is cool"

*Main> prefix (==) "this" "that is not"

*Main> prefix (==) [1,2,3] [1..10]

Exercise 1.17: Write a function substring :: String -> String -> Bool that checks whether str1 is a substring of str2.
The substrings of an arbitrary string ys are given by:

  1. if xs is a prefix of ys, xs is a substring of ys ,
  2. if ys equals y:ys' and xs is a substring of ys', xs is a substring of ys,
  3. nothing else is a substring of ys.
Exercise 1.17 solution:
First, I will change the parameters of the problem a little bit to make the function more generic, so it can work on arbitrary lists, rather than just list of string.

Then, I will use the sliding window approach here and will make use of the prefix function from Exercise 1.16. Basically, at each iteration, call prefix which will test elements in the corresponding lists to see if there is a match. If there is not a match, that is, the first string is not a prefix of the second string then simply remove the first element from the second string, and apply prefix to the remainder of the second list. However, the first list that must be passed to the prefix function has to be the original one.
subString :: (Eq a) => [a] -> [a] -> Bool
subString [] _ = True
subString _ [] = False
subString (x:xs) (y:ys) =
    if prefix (==) (x:xs) (y:ys)
    then True
    else subString (x:xs) ys

Example of Use:
*Main> subString "true" "true"

*Main> subString "true" "false"

*Main> subString "true" "falsetruefalse"

*Main> subString [1,2,3] [1..10]

*Main> subString [] [1]

*Main> subString ['a','b'] "my abcs"

Exercise 1.20: Use map to write a function lengths that takes a list of lists and returns a list of the corresponding list lengths.

Exercise 1.20 solution:
This is a very simple solution actually. Note the use of point-free style as the argument is implied.
lengths :: [[a]] -> [Int]
lengths = map length

Example of Use:
*Main> lengths [[1..10],[2,3]]

Exercise 1.21:
Use map to write a function sumLengths that takes a list of lists and returns the sum of their lengths.

Exercise 1.21 solution:
Again, another simple solution using the lengths function from Exercise 1.20.
sumLengths :: [[a]] -> Int
sumLengths xs = foldl (+) 0 (lengths xs)

Example of Use:
*Main> sumLengths [[1..10],[2,3]]


Juan Maiz said...

Hi Sparky,

I'm having trouble with exercise 1.21 because it is clear in the book that you should use the MAP function and not a FOLD. But i think it is impossible, because map always "returns" a list and the exercise clearly asks to return an Int. Any thoughts?

Matt said...

@Juan Maiz - I came up with these:

-- Ex 1.20
-- Return a list of lengths of lists

lengths :: [[a]] -> [Int]
lengths = map length

-- Ex 1.21
-- Return the sum of the lengths of a list of lists

sumLengths :: [[a]] -> Int
sumLengths = sum . lengths

Matt said...

For Example 1.16 (there is no exercise),

"this" should return True as a prefix of "this is cool", not False as you have listed.

Anonymous said...

I think your prefix function checks for proper prefix instead of prefix. I.e. prefix "hello" "hello" will return False.

Also, you probably want to use foldr or foldl' so as to not have large stack usage.

Sparky Dasrath said...

Ah yes, I am sure you are right. It has been forever and a day since I first did this and I hope to revisit it again soon with some improvements. Thanks for the suggestions.