3

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

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

据我所知，last [1,2,3,4]当 Haskell 挖掘列表时效率不高，这导致列表长度在O(n)哪里的效率。n

4

4 回答 4

11

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)，很简单。这是非常有限的：您不能有效地修改列表的末尾，或者有效地获取倒数第二个元素，或者有效地从列表中构建其中一个（因此您必须将所有基于列表的函数替换为这些人通过您的整个代码来查看好处）或类似的东西，但是您要求高效的一个电话是。

于 2013-01-11T19:59:57.997 回答
10

首先请注意，这last在其他方面并不是特别好，因为它是一个像head. 如果您经常使用列表的尾部，请将其废弃为Data.Sequenceor 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，那么您将获得更好的结果，请参阅文档以了解有关效率的说明和http://hackage.haskell.org/packages/archive/vector/0.10.0.1 /doc/html/Data-Vector-Unboxed.html#g:4DoubleCharData.Vector.UnboxedData.Vector.Unboxed.headData.Vector.Unboxed.last

在您尽可能使用Chars列表的特殊情况下，这显然是“惯用的”事情。再次查看http://hackage.haskell.org/packages/archive/text/0.11.2.3/doc/html/Data-Text.html的文档Data.Textheadlast

如果您想象“Haskell”列表和其他语言中的“列表”之间的对比，那么可能一方面是“Haskell”列表，另一方面是向量和数组之间的对比；后者就像列表一样“Haskelly”。

于 2013-01-11T18:49:40.357 回答
9

那是列表数据结构吗？如果你想要最后一个元素，你将有O(n)复杂性。没有办法解决这个问题。

您将不得不考虑不同的数据结构，例如Data.Sequence

于 2013-01-11T18:31:02.283 回答
1

使用内置列表，无法绕过 O(n) 复杂度（每次只能获取第一个元素和列表的其余部分，因此如果不遍历所有 n 个元素就无法到达末尾）。

于 2013-01-11T18:32:59.727 回答