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

Question

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

示例：getLastElement [1,2,3,4]应返回4。

据我所知，当Haskell挖掘列表时，last [1,2,3,4]的效率不是很高，这导致了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)，非常简单。这是非常有限的:你不能有效地修改列表的末尾，或者有效地获取倒数第二个元素，或者高效地从列表中构建其中一个(所以你必须在整个代码中用这些人替换所有基于列表的函数才能看到好处)，或者任何类似的东西，但是你要求高效的调用是有效的。

Answer 2

首先要注意的是，last在其他方面并不是特别好，因为它像head一样是一个部分函数。如果您经常使用列表的末尾，请在Data.Sequence或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'

如果您使用未装箱的类型，如Int、Double、Char等，则使用Data.Vector.Unboxed会获得更好的结果，有关Data.Vector.Unboxed.head和Data.Vector.Unboxed.last http://hackage.haskell.org/packages/archive/vector/0.10.0.1/doc/html/Data-Vector-Unboxed.html#g:4效率的说明，请参阅文档

在使用Char列表的特殊情况下，尽可能地使用Data.Text，这是非常“惯用”的事情。再次参阅head和last http://hackage.haskell.org/packages/archive/text/0.11.2.3/doc/html/Data-Text.html的文档

如果你想象一下'Haskell‘列表和其他语言中的’list‘之间的对比，这可能是'Haskell’列表和向量和数组之间的对比；后者和列表一样是'Haskelly‘。

Answer 3

这就是列表数据结构，对吗？如果你想要最后一个元素，你就会有O(n)的复杂性。这是绕不开的。

您必须考虑一种不同的数据结构，如Data.Sequence