How do I take the last n elements of a list

From what I can tell you can use something like

lastN :: Int -> [a] -> [a]
lastN n xs = drop (length xs - n) xs

But with any implementation on inbuilt list you can not perform better than O(length of list - n).

It looks like you are trying to use list for something it was not meant to perform efficiently. Use Data.Sequence or some other implementation of list which allows operations to be performed at the end of the list efficiently.

---

Edit:

Davorak's implementation looks like to be the most efficient implementation you can get from inbuilt list. But remember there are intricacies other than just the running time of a single function like whether it fuse well with other functions etc.

Daniel's solution uses inbuilt functions and has the same complexity as of Davorak's and I think has better chances to fuse with other functions.

Not sure whether it's terribly fast, but it's easy:

lastR n xs = snd $ dropWhile (not . null . fst) $ zip (tails $ drop n xs) (tails xs)

This should have the property of only iterating the length of the list once. N for drop n and n - 1 for zipLeftover.

zipLeftover :: [a] -> [a] -> [a]
zipLeftover []     []     = []
zipLeftover xs     []     = xs
zipLeftover []     ys     = ys
zipLeftover (x:xs) (y:ys) = zipLeftover xs ys

lastN :: Int -> [a] -> [a]
lastN n xs = zipLeftover (drop n xs) xs

Here is an alternative shorter and perhaps better since as Satvik pointed out it is often better to use recursion operators then explicit recursion.

import Data.Foldable

takeLeftover :: [a] -> t -> [a]
takeLeftover [] _ = []
takeLeftover (x:xss) _ = xss

lastN' :: Int -> [a] -> [a]
lastN' n xs = foldl' takeLeftover xs (drop n xs)

Also note Will Ness's comment below that takeLeftover is just:

takeLeftover == const . drop 1

Which makes things rather tidy:

lastN' :: Int -> [a] -> [a]
lastN' n xs = foldl' (const . drop 1) xs (drop n xs)
-- or
-- lastN' n xs = foldl' (const . drop 1) <*> drop n