haskell - head.reverse 与 last 的空间复杂度

Question

在许多系统中，head.reverse需要与列表大小成比例的空间，而last需要恒定空间。

是否有系统来执行这样的转变？同样对于reverse.take n.reverse?

编辑：我想扩展我的问题：我不是在进行具体的改造——我更愿意为此进行任何优化。

Answer 1

您可以reverse . take n . reverse通过将列表视为一个特别钝的惰性自然数来进行转换：空列表为零，而 conses 为 succ。对于编码为列表的惰性自然数，减法是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在任何给定时间只有 conses 需要在内存中。特别是takeLast 1（或者实际上takeLast N对于任何文字N）可以在常量内存中运行。您可以通过比较运行takeLast 5 [1..]时发生的情况与(reverse . take 5 . reverse) [1..]在 ghci 中运行时发生的情况来验证这一点。

当然，我尝试在上面使用非常具有暗示性的名称，但在实际实现中，您可能会内联上面所有的废话：

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

Answer 2

您可以为此编写一个简单的重写规则。

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

融合规则也可能会捕获它，这取决于反向编码的方式。

Answer 3

如果我们比较 drop 和 last

>>> 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 。reverse可以使用 drop 和 length 来表示。

---

作为旁注，我已经测试了其他解决方法，结果很糟糕。

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

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