CODEWITHSUNDEEP
haskelllist-comprehension
Dilawar
Dilawar

Reputation: 5645

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 iteration, 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!

Upvotes: 41

Views: 105557

Answers (7)

icktoofay
icktoofay

Reputation: 129011

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:

illustration of list functions

Upvotes: 134

Abhijit Gupta
Abhijit Gupta

Reputation: 21

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

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

Upvotes: 1

dfeuer
dfeuer

Reputation: 48591

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'

Upvotes: 1

hammar
hammar

Reputation: 139840

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.

Upvotes: 52

orkoden
orkoden

Reputation: 19996

(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.

Upvotes: -2

user1429980
user1429980

Reputation: 7148

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).

Upvotes: 8

nulvinge
nulvinge

Reputation: 1598

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.

Upvotes: 1

Related Questions