In Haskell we can easily create a list and then access its elements using the (!!) function, which is defined in the Prelude. Here is a very brief GHCi session:
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 [1], which is phrased as follows:
Write (!!), a function that takes a natural number 
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) !! [9] =
= (-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 = [9] !! 0 = Just 9
What if the index is too large? Let’s compute xs !! 4 then:
[7,8,9] !! 4 = [8,9] !! 3 = [9] !! 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 
__________
References
[1] John O’Donnell, Cordelia Hall, Rex Page, Discrete Mathematics using a Computer (2nd edition), Springer, 2006.
