Космическая сложность head.reverse vs. last

Ответ 1

Вы можете преобразовать reverse . take n . reverse, рассматривая свой список как особенно тупые ленивые натуральные числа: пустые списки равны нулю, а conses - succ. Для ленивых naturals, закодированных как списки, вычитание 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) может работать в постоянной памяти. Вы можете проверить это, сравнив, что происходит, когда вы запускаете 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 _      _     = []

Ответ 2

Для этого вы можете написать простое правило перезаписи.

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

Правила Fusion также могут ловить его, в зависимости от того, как закодировано обратное.

Ответ 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 может быть выражено с использованием капли и длины.

В качестве побочного примечания я проверил другое обходное решение, и результат плох.

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

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