haskell - head.reverse と last のスペースの複雑さ

Question

多くのシステムでは、一定のスペースが必要head.reverseですが、リストのサイズに比例したスペースが必要です。last

そのような変換を実行するシステムはありますか? 同様にreverse.take n.reverse？

編集: 質問を拡張したいと思います: 私は具体的な変換の後ではなく、むしろこの目的のための最適化の後です。

Answer 1

リストを特に鈍い怠惰な自然数として扱うことで変換できreverse . take n . reverseます: 空のリストはゼロであり、cons は成功です。リストとしてエンコードされた怠惰なナチュラルの場合、減算はdrop次のとおりです。

type LazyNat a = [a]

lengthLazy :: [a] -> LazyNat a
lengthLazy = id

dropLazy :: LazyNat a -> [b] -> [b]
dropLazy [] xs = xs
dropLazy (_:n) (_:xs) = dropLazy n xs
dropLazy _ _ = []

-- like Prelude.subtract, this is flip (-)
subtractLazy :: Int -> LazyNat a -> LazyNat a
subtractLazy = drop

nこれで、「最後に取得」機能を簡単に実装できます。

takeLast n xs = dropLazy (subtractLazy n (lengthLazy xs)) xs

n...そして、いつでもコンスだけがメモリ内にある必要があることを知って喜んでいるでしょう。特に、takeLast 1（または実際takeLast Nにはリテラルの場合N）は、定数メモリで実行できます。これは、ghci でtakeLast 5 [1..]実行した場合と実行した場合の結果を比較することで確認できます。(reverse . take 5 . reverse) [1..]

もちろん、上記の非常に示唆に富んだ名前を使用しようとしましたが、実際の実装では、上記のナンセンスをすべてインライン化する可能性があります。

takeLast n xs = go xs (drop n xs) where
    go lastn  []    = lastn
    go (_:xs) (_:n) = go xs n
    go _      _     = []

Answer 2

ドロップとラストを比較すると

>>> last [1..10^5]
100000
(0.01 secs, 10496736 bytes)
>>> last [1..10^6]
1000000
(0.05 secs, 81968856 bytes)
>>> last [1..10^7]
10000000
(0.32 secs, 802137928 bytes)


>>> drop (10^5-1) [1..10^5]
[100000]
(0.01 secs, 10483312 bytes)
>>> drop (10^6-1) [1..10^6]
[1000000]
(0.05 secs, 82525384 bytes)
>>> drop (10^7-1) [1..10^7]
[10000000]
(0.32 secs, 802142096 bytes)

空間と時間で同様のパフォーマンスが得られます。ここではリストの長さを計算する必要がないため、少しごまかしたことを認めなければなりません。とにかく、宇宙では問題にすべきではないと私は信じています。次に、あなたの逆。nを取る。逆は、ドロップと長さを使用して表現できます。

---

補足として、他の回避策をテストしましたが、結果は良くありません。

takeLastN = foldl' (.) id . flip replicate tail 

lastN = foldl' (.) last . flip replicate init

Answer 3

このための簡単な書き換えルールを作成できます。

http://www.haskell.org/haskellwiki/Playing_by_the_rules

リバースがどのようにエンコードされているかによって、融合ルールもそれをキャッチする可能性があります。