Haskell: Why does my implementation of last work for an empty list?

2
votes

I'm working through exercises in Graham Hutton's book "Programming in Haskell" and as part of one exercise I've re-implemented Haskell's last function like so:

lasst xs = drop (length xs - 1) xs

Now this works nicely for a non-empty list:

> lasst [1,2,3,4,5]
[5]

But, surprisingly to me, for an empty list it returns an empty list:

> lasst []
[]

I'm surprised by this because I would expect (length []) - 1 to be evaluated into -1 and the subsequent evaluation of drop -1 [] to throw.

Why does my implementation return an empty list for an empty list, rather than throw an exception?

2
haskell
You should use brackets for -1, so drop (-1) [], since otherwise you perform a drop - 1 [], which does not make much sense. - Willem Van Onsem
If the index is negative, then it drops no elements. This is covered in the Haskell report as well. - Willem Van Onsem
Thanks @willem-van-onsem. Indeed the exception I saw coming from drop -1 [] was due to the missing parentheses. When I add them, drop (-1) [] returns [] as per spec. - urig
That's not an exception. - Thomas M. DuBuisson
BTW drop (length xs - 1) xs is horribly inefficient: it will walk the list once to get its length; then again to drop the prefix. Better is to code lasst directly using pattern matching. (You could then code it to throw an exception on an empty list.) - AntC

2 Answers

5
votes

The Haskell report '10 specifies the the standard Prelude. In this section, we see:

drop                   :: Int -> [a] -> [a]  
drop n xs     | n <= 0 =  xs  
drop _ []              =  []  
drop n (_:xs)          =  drop (n-1) xs

So for a negative n, it will return the entire list. This makes sense with respect to the documentation of drop:

drop n xs returns the suffix of xs after the first n elements, or [] if n > length xs.

So the first -1 elements of a list, are no elements at all.

This is further covered in one of the examples of drop:

drop (-1) [1,2] == [1,2]
2
votes

drop and take are total functions: they always return something without causing a runtime error, no matter what the (total) arguments are. Their definition makes it so that

take k xs ++ drop k xs == xs

holds for every k and (finite) xs. Note that k can be negative, or even larger than the length of xs, and the above is still guaranteed.

It might be surprising at first, but they have the following behavior. Assume xs = [1,2,3]. Then

 k      take     drop
==========================
 ...
 -2     []       [1,2,3]
 -1     []       [1,2,3]
 0      []       [1,2,3]
 1      [1]      [2,3]
 2      [1,2]    [3]
 3      [1,2,3]  []
 4      [1,2,3]  []
 5      [1,2,3]  []
 ...

Personally, I'm unsure about whether their totality is a good idea. It would make sense for them to cause a runtime error for negative k, or for k larger than the length. Still, that's what Haskell does.

(Note in passing that tail xs and drop 1 xs differ when xs=[], because tail is not total.)