haskell - リストの中間要素を取得するための最も効率的な方法は何ですか？

Question

リストを取得したいのですが、最後と最初の要素です。最も効率的な方法は何ですか？

middle = init . tail

また：

middle = tail . init

そして、n-first要素とn-last要素をドロップする場合は？

Answer 1

どちらにしても（それほど）問題ではありません。tailはO（1）であるのに対し、initはO（n）であることに注意してください。tail最初のコンストラクターを取得する場合は、init（n-1）コンストラクターを調べる必要があり、合計n個のコンストラクターが調べられます。

init最初のコンストラクターを取得してから、initn個のコンストラクターをtail調べ、1個を調べて、合計n+1個のコンストラクターを調べます。

したがって、実行するのは少しずつ効率的init . tailですが、心配する必要があるほど効率的ではありません。

リストの最初と最後から最初のk個の要素を削除する場合も同じですが、違いが大きくなる可能性があります。最初に最初の要素を削除すると、最後の要素を削除するときにそれらを調べる必要がなくなり、少し時間が節約されるため、次のことを行う必要があります。

dropLast k . drop k

これは、ではなく、n個のコンストラクターを調べます

drop k . dropLast k

これはn+kコンストラクターを調べます。

Answer 2

どちらも事実上同じです。間違った位置で最適化しようとしています。コードが本当にその種の最適化を行う必要がある場合は、おそらくリストは必要ありません。Data.SequenceやData.Vectorなどを使用してください。