Thursday, April 23, 2009

Solutions to Chapter 3 (p. 69), questions 1-5

#1. I prefer starting with the simple case (here, an empty list) and moving up to the more complex cases. So:

myLength :: [a] -> Int
myLength [] = 0
myLength (_:xs) = 1 + myLength xs

Because have patterns for both possible list constructors, we can be assured that our pattern covers all possible lists.

#2. The signature appears as the first line above. I never write a function without writing its signature first, and I recommend this to you, too.

#3. The mean of a list is the sum of its elements, divided by its length. There actually is a sum function in Prelude, but let's assume there isn't, and define our own, calling it total:

total :: [Double] -> Double
total [] = 0.0
total (x:xs) = x + total xs

mean :: [Double] -> Double
mean xs = (total xs) / fromIntegral (length xs)

But why not make total a local function?

mean :: [Double] -> Double
mean xs = (total xs) / fromIntegral (length xs)
          where total :: [Double] -> Double
                total [] = 0.0
                total (x:xs) = x + total xs

Both length and total iterate over the list; so we have two iterations, which can be wasteful. Can we optimize this by computing both the sum and the length in parallel, using a single iteration? Here goes:

mean :: [Double] -> Double
mean xs = let (len, sum) = lengthAndSum xs
          in sum / fromIntegral len
          where lenAndSum :: [Double] -> (Int, Double)
                lenAndSum [] = (0, 0.0)
                lenAndSum (x:xs) = (1+fst(lenAndSum xs), x+snd(lenAndsum xs))

It's certainly less readable. But... is it faster? In non-methodic testing I did with GHC 6.10.2, the answer is a resounding no: the "optimized" version is actually noticeably slower. (You can test it on lists such as [0, 0.01 .. 1000].) The main lesson is that in Haskell, in most cases, you should write straightforward, readable code, and let the compiler handle the optimizations. (This is true in most programming languages, in fact, especially when only learning the language. We all know the old maxims about premature optimizations.)

You might suspect that the performance hit comes from invoking lenAndSum twice at each recursive iteration, but this isn't the case; Haskell easily optimizes this part away (it's easy to write a single-invocation version and verify that).

BTW, when using the simple

mean xs = (sum xs) / fromIntegral (length xs)

the results are far faster than either approach outlined above. It's not that the built-in sum has some dark magic or hard-coded optimizations: it's just implemented differently than our taken on it (total). You can find the source code here, and it looks like this:

sum     l       = sum' l 0
  where
    sum' []     a = a
    sum' (x:xs) a = sum' xs (a+x)

It doesn't use anything that wasn't presented so far. This specific style of using recursion is discussed in detail in Chapter 4 of the book.

#4. Using ++ for list-concatanation, we get:

pali :: [a] -> [a]
pali [] = []
pali (x:xs) = [x] ++ pali xs ++ [x]

#5. Let's start by thinking about the signature of isPali. At first, it looks like what we need is:

isPali :: [a] -> Bool

so that it works with any list (just like pali works with any type). However, once we begin implementing it we realize that we must be able to compare list members (e.g., the first element must equal the last). And we can't use comparisons if we know nothing about the type! (The equality relation is not defined for all data types.)

Later on, we shall see how to overcome this by limiting the type parameter to "comparable types". For now, let us limit the solution to lists of Char (so we could test it on strings):

isPali :: [Char] -> Bool
isPali xs = (xs == reverse xs)

The reverse function is part of the Prelude (and it's very easy to define by yourself, anyway).

Note the format used for computing a boolean value: I've seen too many expressions like if pred true else false, especially in procedural languages (e.g., if (pred) return true; else return false;). This is very sad -- you can just use the predicate value directly, e.g., return pred;. I've used the same approach in the definition of isPali above.

BTW, the book's definition of a palindrome seems to require it to be of even length. It's easy to "upgrade" the function to meet this requirement, like this:

isPali :: [Char] -> Bool
isPali xs = (xs == reverse xs) && (even (length xs))

6 comments:

  1. Thank you for posting this. I'm a Haskell newbie and this was very helpful to me.

    ReplyDelete
  2. First of all, thanks for posting and explaining your solutions! I'm currently reading the book and doing the exercises - your articles have been very helpful and thought-inspiring!

    That said, I wanted to share another solution to the 'isPali' function. I felt that it's suboptimal to reverse the whole string and then compare all characters (effectively doing each comparison twice). My idea was to reverse just one half of the list and then compare that reversed half with the non-reversed other half. Here is my solution:

    ispalindrome [] = True
    ispalindrome x = go [] 0 x (length x)
    where go left_reversed leftlen (z:right) rightlen
    | lendiff > 1 = go (z:left_reversed) (leftlen+1) right (rightlen-1)
    | lendiff == 1 = left_reversed == right
    | lendiff == 0 = left_reversed == (z:right)
    | otherwise = error "Left list larger than right list"
    where
    lendiff = rightlen - leftlen

    ReplyDelete
  3. Here is a solution without using reverse which wasn't yet introduced:

    -- file isPal - determine whether input list is a palindrome

    isPal :: [Int] -> Bool
    isPal [] = True
    isPal (x:xs) = if length(xs) > 0 && x == last(xs)
    then isPal(take (length(xs)-1) xs)
    else False

    ReplyDelete
  4. How about this isPal without using reverse. Switch the second definition between False and True to allow list of odd length.

    myIsPal [] = True
    myIsPal (x:[]) = False
    myIsPal (x:xs) = x == last xs && myIsPal (init xs)

    ReplyDelete
  5. This is my solution with condition guards:

    isPalindrome :: Eq a => [a] -> Bool
    isPalindrome [] = True
    isPalindrome [x] = False
    isPalindrome (x:xs)
    | x == last xs = isPalindrome (init xs)
    | otherwise = False

    ReplyDelete
  6. pali_check :: [Char] -> Bool
    pali_check [] = True
    pali_check (x:xs)
    | length(x:xs) == 1 = True
    | x == (last xs) = True && (pali_check (init xs))
    | otherwise = False

    ReplyDelete