Haskellでリストの最後の要素を取得する最速の方法

Question

Haskellでリストの最後の要素を取得する最も速い方法は何ですか？また、次の反復では、リストの最初と最後の要素を削除したいと思います。それを行う最もエレガントな方法は何ですか？私はリストの理解をしようとしていますが、それは非常に効率的に見えません！

Answer 1

lastとinitは、1回限りの処理で問題なく動作します。しかし、両方ともO（n）ですので、リストの両端を頻繁に操作する必要がある場合は、Data.Sequenceを代わりに使用することをお勧めします。O（1）挿入と削除両端の品目の

Answer 2

the last functionを使用すると、リストの最後の要素を取得できます。

最初の要素と最後の要素を削除する方法については、(init . tail)を使用できますが、それがどれほど効率的かはわかりません。

私はLearn You A Haskellからこのイメージはかなりよく、リスト機能を示し思う：

Answer 3

を削除するには、最初と最後：

take (len(l)-2) (drop 1 l) 

またはこれも

init (drop 1 l) 

多分

ほぼ最適なコードになります。

Answer 4

それはまだ投稿されていないので、私はプレリュードの実装を投稿します：それは通常の前奏曲と競合することなく実行できるように、私はlistLastに関数名を変更し

listLast :: [a] -> a 
listLast [x] = x --base case is when there's just one element remaining 
listLast (_:xs) = listLast xs --if there's anything in the head, continue until there's one element left 
listLast [] = error "Can't do last of an empty list!" 

注意を。もちろん、import Prelude hiding(last)を行うこともできます。

Answer 5

(head.reverse) [1..100] 

最後の要素を取得するためのlastの代替品です。

drop 1 (take (length [1..100] - 1) [1..100]) 

は、最初と最後のリスト要素を削除します。 dropとtakeのソースは、(init . tail)より速いかもしれません。

(reverse.drop 1) ((reverse.drop 1) [1..100]) 

は、別の変形である。しかし、私はダブル反転のために遅くなると思う。

Answer 6

この答えは、空のリストのような奇妙な条件を最大限に柔軟に扱い、小さな関数から大きな関数をいくつかのライブラリ関数を使って構築することに重点を置いています。それはではありません。誰かが最初にリストについて学ぶのに最適な答えですが、その前にいくつかのステップがあります。

以下の場合、あなたは

import Control.Monad ((>=>)) 

が必要になりますし、あなたはGHC 7を使用するのいずれかが必要になります。

init' :: [x] -> Maybe [x] 
init' = foldr go Nothing 
    where 
    go x mxs = Just (maybe [] (x:) mxs) 

tailのバージョンがそれでは

tail' :: [a] -> Maybe [a] 
tail' = fmap snd . uncons 

を書き込むことができ

あなたが得ることができる：10とData.List (uncons)をインポートしたり、

uncons :: [a] -> Maybe (a, [a]) 
uncons [] = Nothing 
uncons (x:xs) = Just (x,xs) 

を定義しますが、このようなinitの安全なフォームを書くことができますa maybefied

trim' :: [a] -> Maybe [a] 
trim' = init' >=> tail' 

>=>は、一種の後方モナド構成です。 init' >=> tail'は、その引数にinit'を適用してMaybe [a]を取得する関数です。 Nothingを取得した場合は、それを返します。 Just xsを取得した場合はtail'をxsに適用し、それを返します。このことから

、あなたは簡単にダウン空のリストに0、1、または2つの要素でリストをトリミングトリマーを行うことができます。私は取得すると思い

trim :: [a] -> [a] 
trim = maybe [] id . trim'