How do I take the last n elements of a list

Question

To obtain the last n elements of a list xs, I can use reverse (take n (reverse xs)), but that is not very good code (it keeps the complete list in memory before returning anything, and the result is not shared with the original list).

How do I implement this lastR function in Haskell?

Answer 1

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