Thursday, April 23, 2009

Solutions to Chapter 2 (p. 39)

For the excercise on page 25, just type each line into ghci.

Page 39:

#1. The function can only select an element from the list: there's no other way it can obtain a value of type a; in particular, it cannot create new values of this "unknown" type.

Thus, possible valid behaviors include returning the first element, returning the second element, etc.; returning the last element, returning the last-but-one element, etc.; returning the middle element; and so on.

Interestingly, a function with this signature in Haskell cannot return a "random" element from the list, because (for functions with no IO) the same value must be returned every time the function is called with the same input.

#2. Using if:

lastButOne :: [a] -> a
lastButOne (x:xs) = if length xs == 1
                    then x
                    else lastButOne xs

With pattern matching (introduced in the following chapter), this can be simplified as:

lastButOne :: [a] -> a
lastButOne (x1:[x2]) = x1
lastButOne (x:xs) = lastButOne xs

#3. For either version, trying this on a too-short list (e.g., lastButOne "no") results in the error message "Non-exhaustive patterns in function".

6 comments:

  1. This is a very interesting approach to the problem! I did not take a recursive approach, but rather:

    lastButOne xs = if length xs > 1
    then take 1 (drop (length(xs) - 2) xs )
    else []

    It does not throw an error if the user does not have more than one element, and is not quite as readable, but may be slightly more efficient.

    ReplyDelete
  2. Hi James,

    Interesting; however, I think it is actually more correct to throw an error if there are less than two elements. Just like "head" throws an error if the list is empty, for example.

    ReplyDelete
  3. I had two versions. Using last of init of xs turned out to be a little more efficient on large lists and had a rather nice syntax.

    lastButOne :: [a] -> a
    lastButOne xs = last $ init xs


    Using head on myDrop 1 of the list reversed was the one I thought of first. It uses a lot of memory on big lists.

    lastButOne xs = head . myDrop 1 $ reverse xs

    ReplyDelete
  4. I'm completely new to Haskell, but tried to do this using only features which had already been introduced and came up with:

    lastButOne :: [a] -> a
    lastButOne xs = head ((drop (length xs - 2)) xs)

    It seems to work, but I haven't done any performance comparisons.

    ReplyDelete
  5. Hello,
    I'm completely new to Haskell and trying write this program. I've come up with that piece of code (which doesn't work):

    lastButOne (xs) = if null(tail xs) || null xs
    then return head xs
    else lastButOne (tail xs)

    What's wrong with it???

    ReplyDelete
  6. Inspired by others.
    Here's my solution and it works.

    lastButOne :: [a] -> a
    lastButOne list@(x:xs)
    | length list < 2 = error "It's too short!"
    | length list ==2 = x
    | otherwise = lastButOne xs

    ReplyDelete