Fastest way to get the last element of a list in Haskell

What is the fastest way to get the last element of a list in Haskell. Also in next iterati开发者_JAVA百科on, I want to remove first and last element of the list. What is the most elegant way to do it? I am trying list comprehension, but that does not look very efficient!

You can use the last function to get the last element of a list.

As for how to remove the first and last elements, you could use (init . tail), but I don't know how efficient that is.

I think this image from Learn You A Haskell shows the list functions fairly well:

last and init will do the job just fine for a one-off. However they are both O(n), so if you need to manipulate both ends of a list often, as you seem to imply, you might want to consider using Data.Sequence instead, which supports O(1) insertion and removal of items at both ends.

I'll post the Prelude implementation since it hasn't been posted yet:

listLast :: [a] -> a
listLast [x] = x --base case is when there's just one element remaining
listLast (_:xs) = listLast xs --if there's anything in the head, continue until there's one element left
listLast [] = error "Can't do last of an empty list!"

Note that I changed the function name to listLast so that it can be run without conflicting with normal Prelude. You could, of course, do import Prelude hiding(last).

To remove first and last:

take (len(l)-2) (drop 1 l)

or maybe

init (drop 1 l)

This also results in almost optimal code.

This answer focuses on dealing with weird conditions (like empty lists) in a maximally flexible way, and on building up bigger functions from smaller ones using some library functions. It's not the best answer for someone first learning about lists, but rather a couple steps past that.

For the following, you will need

import Control.Monad ((>=>))

and you will need to either use GHC 7.10 and import Data.List (uncons) or define

uncons :: [a] -> Maybe (a, [a])
uncons [] = Nothing
uncons (x:xs) = Just (x,xs)

You can write a safe form of init like this:

init' :: [x] -> Maybe [x]
init' = foldr go Nothing
  where
    go x mxs = Just (maybe [] (x:) mxs)

A version of tail can be written

tail' :: [a] -> Maybe [a]
tail' = fmap snd . uncons

So then you can get a maybefied

trim' :: [a] -> Maybe [a]
trim' = init' >=> tail'

The >=> is a sort of backwards monadic composition. init' >=> tail' is a function that applies init' to its argument to get a Maybe [a]. If it gets Nothing, it returns that. If it gets Just xs, it applies tail' to xs and returns that.

From this, you can easily make a trimmer that trims lists with 0, 1, or 2 elements down to empty lists:

trim :: [a] -> [a]
trim = maybe [] id . trim'

last' :: [a] -> a
last' ys = foldl1 (\_ -> \x -> x) ys

It is O(n), just like the built in library function list.

(head.reverse) [1..100]

Is an alternative to last to get the last element.

drop 1 (take (length [1..100] - 1) [1..100])

removes the first and last list element. The source for drop and take look like it might be faster than (init . tail).

(reverse.drop 1) ((reverse.drop 1) [1..100])

is another variant. But I guess slower because of the double reversal.