CODEWITHSUNDEEP
haskellpattern-matching
Nicolas Henin
Nicolas Henin

Reputation: 3334

Pattern matching on the last element of a List

we use (x:xs) to pattern match on the first element as in this example :

head' :: [a] -> a  
head' xs = case xs of [] -> error "No head for empty lists!"  
                      (x:_) -> x

is there a way to pattern match on the last element ?

Upvotes: 5

Views: 2399

Answers (6)

Greg Bacon
Greg Bacon

Reputation: 139411

If you have GHC 6.10 or newer, use a view pattern.

View patterns permit calling the view function inside the pattern and matching against the result:

size (view -> Unit) = 1
size (view -> Arrow t1 t2) = size t1 + size t2

That is, we add a new form of pattern, written

expression -> pattern

that means “apply the expression to whatever we're trying to match against, and then match the result of that application against the pattern.” The expression can be any Haskell expression of function type, and view patterns can be used wherever patterns are currently used.

Define head' as

{-# LANGUAGE ViewPatterns #-}

head' :: [a] -> a
head' (last -> l) = l

It works as you expect.

λ> head' [3,5,7]
7
λ> head' []
*** Exception: Prelude.last: empty list

Upvotes: 1

chepner
chepner

Reputation: 530843

No, because there is no constructor of type [a] -> a -> [a] to match.

You can use [] and : for pattern matching because they are, by definition, the building blocks of a list value. [] is the way to create an empty list. : is the way to build a new list from an element and another list. Functions like append do not create new lists by themselves; they return lists created by : and/or [].

The exception is if you happen to know the length of the list in advance, in which case you can match the last element by matching all of the elements explicitly.

lastOfFour :: [a] -> a
lastOfFour (_:_:_:x:[]) = x
lastOfFour (_:_:_:_:_) = error "Too many elements"
lastOfFour _ = error "Too few elements"

The first error message is triggered if you can match at least 4 elements, and the remaining list is not empty; the second by any list that isn't matched by one of the first two.

Upvotes: 6

Jon Purdy
Jon Purdy

Reputation: 54971

You can’t match on the last element directly, since pattern matching only deconstructs things based on the concrete constructors of the type, and lists only have two constructors: [] and (:).

However, you can reverse the list, then match on the head of the reversed list:

last' xs = case reverse xs of
  [] -> error "last' []"
  x : _ -> x

With ViewPatterns you can do that reversal directly in the pattern:

{-# LANGUAGE ViewPatterns #-}

last' (reverse -> xs) = case xs of
  [] -> error "last' []"
  x : _ -> x

Or with PatternGuards you can do the reversal in a guard:

{-# LANGUAGE PatternGuards #-}

last' xs
  | x : _ <- reverse xs = x
  | otherwise = error "last' []"

Finally, with PatternSynonyms you can package this up with a name:

{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE ViewPatterns #-}

pattern Reversed xs x <- (reverse -> x : xs)

  -- This part is optional, but allows writing:
  --
  --   Reversed [3, 2, 1] 0
  --
  -- As a synonym for:
  --
  --   [0, 1, 2, 3]
  --
  where Reversed xs x = x : reverse xs

last' (Reversed _ x) = x
last' _ = error "last' []"

All of these solutions are O(n) (linear) in the length of the list, which is unavoidable. So you might be better off making the traversal as explicit as possible, instead of hiding the linear cost and inadvertently traversing the list more than you intended, or using a different data structure with O(1) (constant) indexing of the last element, such as a Seq or Vector.

Upvotes: 1

Anders Kaseorg
Anders Kaseorg

Reputation: 3875

In GHC, you can define a pattern synonym for this, if you really want to. It will still be O(n), of course.

{-# LANGUAGE PatternSynonyms, ViewPatterns #-}

unsnoc :: [a] -> Maybe ([a], a)
unsnoc [] = Nothing
unsnoc xs = Just (init xs, last xs)

{-# COMPLETE [], (:>) #-}
infixl 5 :>
pattern (:>) :: [a] -> a -> [a]
pattern xs :> x <- (unsnoc -> Just (xs, x))
  where xs :> x = xs ++ [x]

-- example:

last' :: [a] -> a
last' [] = error "last': empty list"
last' (_ :> x) = x

(unsnoc is also in Data.List.Extra.)

Upvotes: 3

Ed&#39;ka
Ed&#39;ka

Reputation: 7130

To get the the last element of list you need to traverse entire list.
If you need to match on the last element you probably need a list-like data structure which makes such match efficient and easy to use, like Sequence (where it is O(1) from both ends):

{-# LANGUAGE OverloadedLists #-}

import Data.Sequence

last' :: Seq a -> a
last' Empty = error "Empty sequence"
last' (_:|>a) = a

test = last' [1..5]

Upvotes: 5

crockeea
crockeea

Reputation: 21811

As chepner pointed out, there is no built-in way to do this, but it's also not hard to write your own:

foo :: [Maybe a] -> a
foo [] = error "empty list"
foo xs =
  case last xs
    (Just a) -> a
    Nothing -> error "last element is a Nothing!"

Another way would be to reverse the list, and then pattern match on the first element!

Upvotes: -2

Related Questions