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

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),容易俗气.这是非常有限的:您无法有效地修改列表的末尾,或者无法有效地获取倒数第二个元素,或者有效地从列表中构建其中一个(因此您必须替换所有基于列表的函数这些人通过你的整个代码看到了好处),或类似的东西,但你被要求高效的一个电话是.

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"列表和其他语言中的"列表"之间的对比,那么一方面可能是"Haskell"列表与另一方面的矢量和数组之间的对比; 后者和列表中的'Haskelly'一样.

Answer 3

那就是列表数据结构对吗？如果你想要最后一个元素,你就会有O(n)复杂性.没有解决这个问题.

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