Using patterns to find the nth element

Question

I'm working through Learn You A Haskell in order to come up to speed with the basics of Haskell. I'm very comfortable with both functional programming and pattern matching, but the latter more so with how Mathematica does it.

In the same spirit as the naïve implementation of head in Chapter 4.1, I proceeded with a naïve implementation of last as:

last1 :: [a] -> a
last1 (_:x:[]) = x

However, calling last1 [1,2,3,4] gave an error Exception: ... Non-exhaustive patterns in function last1. I understand that this error implies that the pattern specified does not cover all possible inputs and usually, a catch-all pattern is necessary (which I've not provided). However, I'm not exactly sure why I get this error for my input.

Question 1: My understanding (of my incorrect approach) is that the first element is captured by _ and the rest get assigned to x, which isn't exactly what I had intended. However, shouldn't this give a type error, because I specified [a] -> a, but x is now a list?

Note that this is not about how to write a working last function — I know I can write it as (among other possibilities)

last2 :: [a] -> a
last2 [x] = x
last2 (_:x) = last2 x

Question 2: Along the same theme of better understanding pattern matching in Haskell, how can I use pattern matching to pick out the last element or more generally, the nth element from a given list, say, [1..10]?

This answer suggests that you can bind the last element using pattern matching with the ViewPatterns extension, but it seems strange that there isn't an analogous "simple" pattern like for head

In Mathematica, I would probably write it as:

Range[10] /. {Repeated[_, {5}], x_, ___} :> x
(* 6 *)

to pick out the 6th element and

Range[10] /. {___, x_} :> x
(* 10 *)

to pick out the last element of a non-empty list.

I apologize if this is covered later in the text, but I'm trying to relate each topic and concept as I come across them, to how it is handled in other languages that I know so that I can appreciate the differences and similarities.

Answer 1

To make sense of the result of your first attempt, you need to see how the list data is defined. Lists enjoy a somewhat special syntax, but you would write it something like this.

data List a = (:) a (List a)
            | []

So, your list [1 .. 10] is actually structured as

(1 : (2 : (3 : (4 : []))))

In addition, due to the right associativity of the (:) operator, your pattern for last1 actually looks like

last1 :: [a] -> a
last1 (_:(x:[])) = x

That is why 'x' has same type as an element of your list; it is the first argument to the (:) constructor.

Pattern matching allows you to deconstruct data structures like lists, but you need to know what "shape" they have to do so. That is why you cannot directly specify a pattern that will extract the last element of a list, because there are an infinite number of lengths a list can have. That is why the working solution (last2) uses recursion to solve the problem. You know what pattern a list of length one has and where to find the final element; for everything else, you can just throw away the first element and extract the last element of the resulting, shorter, list.

If you wanted, you could add more patterns, but it would not prove that helpful. You could write it as

last2 :: [a] -> a
last2 (x:[])     = x
last2 (_:x:[])   = x
last2 (_:_:x:[]) = x
        ...
last2 (x:xs) = last2 xs

But without an infinite number of cases, you could never complete the function for all lengths of input lists. Its even more dubious when you consider the fact that lists can actually be infinitely long; what pattern would you use to match that?

Answer 2

There is no way to have pattern match get the "last" element without using view patterns. That is because there is no way to get the last element of a list without using recursion (at least implicitly), and what is more, there is no decidable way to get the last element.

Your code

last1 (_:x:[]) = x

should be parsed like

last1 (_:(x:[])) = x

which can be de-sugared into

last1 a = case a of
               (_:b) -> case b of
                             (x:c) -> case c of
                                           [] -> x

having completed this exercise we see what your code does: you have written a pattern that will match a list IF the outermost constructor of a list is a cons cell AND the next constructor is a cons AND the third constructor is a nil.

so in the case of

last1 [1,2,3,4]

we have

last1 [1,2,3,4] 
= last1 (1:(2:(3:(4:[]))))
= case (1:(2:(3:(4:[])))) of
       (_:b) -> case b of
                     (x:c) -> case c of
                                   [] -> x
= case (2:(3:(4:[]))) of
       (x:c) -> case c of
                     [] -> x
= let x = 2 in case (3:(4:[])) of
                    [] -> x
= pattern match failure

Answer 3

Your example

last1 (_:x:[]) = x

only matches lists containing two elements i.e. lists of the form a:b:[]. _ matches the head of the list without binding, x matches the following element, and the empty list matches itself.

When pattern matching lists, only the right-most item represents a list - the tail of the matched list.

You can get the nth element from a list with a function like:

getNth :: [a] -> Int -> a
getNth [] _ = error "Out of range"
getNth (h:t) 0 = h
getNth (h:t) n = getNth t (n-1)

This built-in using the !! operator e.g. [1..10] !! 5