Complexité spatiale de la tête.inverse par rapport à la dernière

Question

Dans de nombreux systèmes, head.reverse requiert un espace proportionnel à la taille de la liste, alors que last nécessite un espace constant.

Existe-t-il des systèmes permettant d'effectuer une telle transformation ? De même pour reverse.take n.reverse ?

Edit : Je voudrais étendre ma question : Je ne suis pas à la recherche d'une transformation concrète - je suis plutôt à la recherche de tout l'optimisation à cette fin.

Answer 1

Vous pouvez transformer reverse . take n . reverse en traitant votre liste comme un nombre naturel paresseux particulièrement obtus : les listes vides sont nulles, et les conses sont succés. Pour les nombres naturels paresseux codés comme des listes, la soustraction est 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

Maintenant, nous pouvons facilement mettre en œuvre le "prendre le dernier n fonction " :

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

...et vous serez heureux d'apprendre que seulement n conses doivent être en mémoire à un moment donné. En particulier, takeLast 1 (ou bien takeLast N pour tout littéral N ) peut fonctionner en mémoire constante. Vous pouvez vérifier cela en comparant ce qui se passe lorsque vous exécutez takeLast 5 [1..] avec ce qui se passe lorsque vous exécutez (reverse . take 5 . reverse) [1..] en ghci.

Bien sûr, j'ai essayé d'utiliser des noms très suggestifs ci-dessus, mais dans une implémentation réelle, vous pourriez mettre en ligne toutes les absurdités ci-dessus :

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

Answer 2

Vous pouvez écrire une simple règle de réécriture pour cela.

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

Les règles de fusion peuvent également l'attraper, en fonction de la manière dont le reverse est codé.

Answer 3

Si nous comparons la baisse et la dernière

>>> 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)

On obtient des performances similaires dans l'espace et dans le temps, je dois avouer que j'ai un peu triché car ici on n'a pas besoin de calculer la longueur de la liste. De toute façon je pense que ça ne devrait pas être un problème dans l'espace. Alors votre inverser . prendre n . inverser pourrait être exprimée en utilisant la chute et la longueur.

---

J'ai testé d'autres solutions de contournement et les résultats sont mauvais.

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

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