[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"
["a","be","line","sorted","this","will"]
--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"
False

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

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

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"
True

*Main> subString "true" "false"
False

*Main> subString "true" "falsetruefalse"
True

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

*Main> subString [] [1]
True

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

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]]
[10,2]

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]]
12