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

现在我们可以轻松实现"take last n"功能:

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

......你会很高兴知道n在任何特定时间都只需要记忆.特别是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

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