3

Haskellでリストの最後の要素を取得する最も効率的な方法は何ですか?

例:getLastElement [1,2,3,4]を返す必要があり4ます。

私の知る限り、 Haskell がリストを掘り下げてリストの長さをlast [1,2,3,4]効率化するため、あまり効率的ではありませんO(n)。n

4

4 に答える 4

11

岡崎の本は、既存のデータ構造に効率的な 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) になりました。これには非常に制限があります:リストの末尾を効率的に変更したり、最後から 2 番目の要素を効率的に取得したり、リストからこれらの 1 つを効率的に作成したりすることはできません (したがって、すべてのリストベースの関数を次のように置き換える必要があります)。これらの人はあなたのコード全体を通して利益を確認します)、またはそのようなものですが、効率的にするためにあなたが求めた呼び出しは 1 つです。

于 2013-01-11T19:59:57.997 に答える
10

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のボックス化されていないタイプを使用している場合は、 を使用するとさらに良い結果が得られます。/doc/html/Data-Vector-Unboxed.html#g:4DoubleCharData.Vector.UnboxedData.Vector.Unboxed.headData.Vector.Unboxed.last

可能な限りChars use のリストを使用している特別なケースでは、これは強調して「慣用的な」ものです。および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 に答える