haskell - 以有效的方式从列表中获取最后一个元素

Question

在 Haskell 中获取列表最后一个元素的最有效方法是什么？

示例:getLastElement [1,2,3,4]应该返回 4 .

据我所知，last [1,2,3,4]效率不是很高，因为 Haskell 会挖掘列表，导致效率为 O(n)哪里n是列表的长度。

Answer 1

Okasaki 的书教给我们一个很好的技巧，可以为现有数据结构添加高效的 API:将结构包装在一个新的结构中，以缓存 API 调用的结果。如果您只想添加 last对于一组有效的调用，这是执行此操作的简单方法:

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)

现在 last操作是 O(1)，简单粗暴。这是非常有限的:您无法有效地修改列表的末尾，或有效地获取倒数第二个元素，或有效地从列表中构建其中之一(因此您必须将所有基于列表的函数替换为这些人通过您的整个代码来查看好处)或类似的东西，但是您要求提高效率的一个电话是。