CODEWITHSUNDEEP
haskell
Patrick
Patrick

Reputation: 3111

Get last element from a list in an efficient way

What is the most efficient way to get the last element of a list in Haskell?

Example: getLastElement [1,2,3,4]should return 4.

As far as I know, last [1,2,3,4] is not very efficient as Haskell digs through the list which results in an efficiency of O(n) where nis the length of the list.

Upvotes: 3

Views: 2143

Answers (4)

applicative
applicative

Reputation: 8199

Note first that last is not particularly great on other grounds, since it is a partial function like head. If you are constantly using the tail end of the list, scrap it for Data.Sequence or Data.Vector.Unboxed:

import Data.Sequence

firstThing seq = case viewl seq of
   EmptyL -> error "no beginning"
   a :< as -> a

lastThing seq = case viewr seq of
   EmptyR -> error "no end"
   as :> a -> a

-- > lastThing (fromList "abc")
-- 'c'
-- > firstThing (fromList "abc")
-- 'a'

If you are using an unboxed type like Int, Double, Char etc. then you will get still better results with Data.Vector.Unboxed , see the documentation for remarks about the efficiency of Data.Vector.Unboxed.head and Data.Vector.Unboxed.last http://hackage.haskell.org/packages/archive/vector/0.10.0.1/doc/html/Data-Vector-Unboxed.html#g:4

In the special case where you are using lists of Chars use Data.Text wherever possible, this is emphatically the 'idiomatic' thing. Again see the documentation for head and last http://hackage.haskell.org/packages/archive/text/0.11.2.3/doc/html/Data-Text.html

If you are imagining a contrast between 'Haskell' lists and 'lists' in other languages, it is probably the contrast between 'Haskell' lists on the one hand, and vectors and arrays on the other; the latter are just as 'Haskelly' as lists.

Upvotes: 9

Daniel Wagner
Daniel Wagner

Reputation: 152737

Okasaki's book teaches us a nice trick for adding efficient APIs to existing data structures: wrap up the structure in a new one that caches the result of the API calls. If you only want to add last to the set of efficient calls, here's the simple way to do that:

import Control.Monad -- mplus is a convenient spell

data LastList a = LastList
    { forget :: [a]
    , last   :: Maybe a
    }

nil = LastList [] Nothing
cons x l = LastList (x : forget l) (last l `mplus` Just x)

Now the last operation is O(1), easy-cheesy. This is very limited: you can't modify the end of the list efficiently, or get the second-to-last element efficiently, or build one of these out of a list efficiently (so you have to replace all list-based functions with these guys through your whole code to see the benefit), or anything like that, but the one call you asked to be efficient is.

Upvotes: 11

NominSim
NominSim

Reputation: 8511

With the built in list there is no way around O(n) complexity (you can only get the first element, and the rest of the list every time so you can't get to the end without going through all n elements).

Upvotes: 1

manojlds
manojlds

Reputation: 301147

That is it with the list data structure right? If you want the last element, you will have O(n) complexity. There is no going around that.

You will have to consider a different data structure like Data.Sequence

Upvotes: 9

Related Questions