Prelude> let xs = [7,8,9] Prelude> xs !! 0 7 Prelude> xs !! 1 8 Prelude> xs !! 2 9
So far, so good. What if the index is negative or equals / exceeds the list’s length? Let’s see what happens in those cases:
Prelude> xs !! (-1) *** Exception: Prelude.(!!): negative index Prelude> xs !! 3 *** Exception: Prelude.(!!): index too large
As expected, we get error messages. What if we used the Maybe data type to avoid exceptions? This is exercise 4 in chapter 3 of O’Donnell & Hall & Page , which is phrased as follows:
Write (!!), a function that takes a natural number and a list and selects the th element of the list. List elements are indexed from , not , and since the type of the incoming number does not prevent it from being out of range, the result should be a Maybe type.
The aforementioned authors propose the following implementation:
import Prelude hiding ((!!)) (!!) :: Int -> [a] -> Maybe a (!!) n  = Nothing (!!) 0 (x:xs) = Just x (!!) n (x:xs) = (!!) (n-1) xs
where I added the import line to hide the standard (!!) function that is defined in the Prelude. My first thought was that the authors switched the function arguments, which makes the function look silly. Let’s give it a try. Here’s another GHCi session:
*Main> let xs = [7,8,9] *Main> 0 !! xs Just 7 *Main> 1 !! xs Just 8 *Main> 2 !! xs Just 9 *Main> (-1) !! xs Nothing *Main> 3 !! xs Nothing
It appears to be working, but specifying the index before the list looks rather ugly. Wait, what if the index is negative? For example, why does (-3) !! xs return Nothing? Let’s use equational reasoning to find out:
(-3) !! [7,8,9] = (-4) !! [8,9] = = (-5) !!  = = (-6) !!  = = Nothing
This reveals a fatal flaw in the authors’ implementation: if the list is infinite, then the recursion will never terminate. For example, (-1) !! [0..] will never terminate, because when the initial index is negative, decrementing the index will never get us to the zero index.
Therefore, I propose the following implementation:
import Prelude hiding ((!!)) (!!) :: [a] -> Integer -> Maybe a (!!)  n = Nothing (!!) (x:xs) n | n > 0 = (!!) xs (n-1) | n == 0 = Just x | n < 0 = Nothing
where the first argument is now a list, and the second argument an integer. Note that I used indices of type Integer (“mathematical integers”), instead of type Int (“computer integers”). Let’s see if this implementation works:
*Main> let xs = [7,8,9] *Main> xs !! 0 Just 7 *Main> xs !! 1 Just 8 *Main> xs !! 2 Just 9 *Main> xs !! (-1) Nothing *Main> xs !! 3 Nothing
It appears to be working. No errors. No exceptions. If you, dear reader, happen to be acquainted with Haskell you will almost certainly be shocked (!!!), for this function is trivial! Well, that is true, but I allow myself to be intrigued by trivialities. Moreover, this function is simple enough to allow us to use equational reasoning. For example, let’s compute xs !! 2 using equational reasoning:
[7,8,9] !! 2 = [8,9] !! 1 =  !! 0 = Just 9
What if the index is too large? Let’s compute xs !! 4 then:
[7,8,9] !! 4 = [8,9] !! 3 =  !! 2 =  !! 1 = Nothing
Step by step, by successively removing the head of the list, we get where we want to. Unfortunately, this suggests that accessing an arbitrary element of the list will not be .
 John O’Donnell, Cordelia Hall, Rex Page, Discrete Mathematics using a Computer (2nd edition), Springer, 2006.