**#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 (`). This is very sad -- you can just use the predicate value directly, e.g.,

*pred*) return true; else return false;`return`. I've used the same approach in the definition of

*pred*;`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))

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

ReplyDeleteFirst 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!

ReplyDeleteThat 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

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

ReplyDelete-- 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

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

ReplyDeletemyIsPal [] = True

myIsPal (x:[]) = False

myIsPal (x:xs) = x == last xs && myIsPal (init xs)

This is my solution with condition guards:

ReplyDeleteisPalindrome :: Eq a => [a] -> Bool

isPalindrome [] = True

isPalindrome [x] = False

isPalindrome (x:xs)

| x == last xs = isPalindrome (init xs)

| otherwise = False

pali_check :: [Char] -> Bool

ReplyDeletepali_check [] = True

pali_check (x:xs)

| length(x:xs) == 1 = True

| x == (last xs) = True && (pali_check (init xs))

| otherwise = False