O (1) tampon circulaire en haskell?

Question

Je travaille sur un petit projet de Haskell qui nécessite un tampon circulaire. J'ai réussi à créer une mémoire tampon en utilisant des tableaux qui ont une rotation O (1), mais qui nécessite bien sûr O (N) pour l'insertion/la suppression. J'ai trouvé une implémentation en utilisant des listes qui semblent prendre O (1) pour l'insertion et la suppression, mais comme elle maintient une liste gauche et droite, croiser une certaine frontière quand la rotation prendra le temps O (N). Dans un langage impératif, je pourrais implémenter un tampon circulaire doublement lié avec O (1) insertion, suppression et rotation. Je pense que ce n'est pas possible dans un langage purement fonctionnel comme Haskell, mais j'aimerais savoir si je me trompe.

Answer 1

La monade ST permet de décrire et d'exécuter des algorithmes impératifs dans Haskell. Vous pouvez utiliser STRefs pour les pointeurs modifiables de votre liste doublement chaînée.

Les algorithmes autonomes décrits à l'aide de ST sont exécutés à l'aide de runST. Différentes exécutions runST peuvent ne pas partager ST structures de données (STRef, STArray, ..).

Si l'algorithme n'est pas "autonome" et que la structure de données doit être maintenue avec les opérations d'E/S effectuées entre ses utilisations, vous pouvez utiliser stToIO pour y accéder dans la monade IO.

En ce qui concerne si c'est purement fonctionnel ou non - je suppose que ce n'est pas?

Answer 2

Si vous pouvez traiter amorti O (1) opérations, vous pouvez probablement utiliser soit Data.Sequence de l'emballage conteneurs ou Data.Dequeue du paquet dequeue. Le premier utilise finger trees, tandis que le second utilise la "Dequeue du banquier" du Purely Functional Data Structures d'Okasaki (une version antérieure en ligne here).

Answer 3

Il semble que vous ayez besoin de quelque chose d'un peu plus compliqué que cela (puisque vous avez mentionné des listes à double liaison), mais peut-être que cela vous aidera. Cette fonction agit comme map sur une liste cyclique mutable:

mapOnCycling f = concat . tail . iterate (map f) 

utilisation comme:

*Main> (+1) `mapOnCycling` [3,2,1] 

[4,3,2,5,4,3,6,5,4,7,6,5,8,7,6,9,8,7,10,9...] 

Et voici celui qui agit comme mapAccumL:

mapAccumLOnCycling f acc xs = 
    let (acc', xs') = mapAccumL f acc xs 
    in xs' ++ mapAccumLOnCycling f acc' xs' 

Quoi qu'il en soit, si vous vous souciez d'élaborer encore plus sur ce que votre structure de données doit être capable de "faire", je serais vraiment intéressé à en entendre parler.

EDIT: comme camccann mentionné, vous pouvez utiliser Data.Sequence pour ce qui, selon la documentation devrait vous donner de la complexité de temps O1 (est-il une telle chose comme O1 amorti le temps?) Pour l'affichage ou l'ajout d'éléments à la fois aux côtés gauche et droit de la séquence, ainsi que de modifier les extrémités le long du chemin. Si cela aura la performance dont vous avez besoin, je ne suis pas sûr.

Vous pouvez traiter "l'emplacement actuel" comme l'extrémité gauche de la séquence. Ici nous naviguons d'avant en arrière le long d'une séquence, produisant une liste infinie de valeurs.Désolé si elle ne compile pas, je n'ai pas GHC au moment:

shuttle (viewl-> a <: as) = a : shuttle $ rotate (a+1 <| as) 
    where rotate | even a = rotateForward 
       | otherwise = rotateBack 
      rotateBack (viewr-> as' :> a') = a' <| as' 
      rotateForward (viewl-> a' <: as') = as' |> a'