如何获取列表的最后n个元素

Question

要获取n列表的最后一个元素xs,我可以使用reverse (take n (reverse xs)),但这不是很好的代码(它在返回任何内容之前将完整列表保留在内存中,并且结果不与原始列表共享).

如何lastR在Haskell中实现此功能？

Answer 1

这应该具有仅迭代列表长度一次的属性.drop n对于zipLeftover,N for 和n - 1.

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

这是一个更短的选择,也许更好,因为Satvik指出使用递归运算符然后显式递归通常更好.

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)

另请注意Will Ness的评论如下takeLeftover:

takeLeftover == const . drop 1

这让事情变得相当整洁:

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

Answer 2

据我所知,你可以使用类似的东西

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

但是对于内置列表中的任何实现,您的表现都不能比O(length of list - n).

看起来你正在尝试使用list来表示它本身无法有效执行的操作.使用Data.Sequence或其他一些列表实现,允许在列表末尾有效地执行操作.

编辑:

Davorak的实现看起来是内置列表中最有效的实现.但请记住,除了单个函数的运行时间之外,还有复杂性,例如它是否与其他函数融合等.

Daniel的解决方案使用内置功能,并且具有与Davorak相同的复杂性,我认为有更好的机会融合其他功能.

Answer 3

不确定它是否非常快，但是很简单：

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