File d'attente efficace dans Haskell

Question

Comment puis-je implémenter efficacement une structure de données de liste où je peux avoir 2 vues en tête et en fin de liste, qui pointent toujours en tête d'une liste sans appels onéreux à inverser. i.e.:

start x = [] 
end x = reverse start -- [] 
start1 = [1,2,3] ++ start 
end start1 -- [3,2,1] 

fin devrait être en mesure de le faire sans invoquer « inverse », mais regardant simplement la liste donnée dans la perspective de la liste étant en sens inverse automatiquement. La même chose devrait se produire si je crée de nouvelles listes à partir de concaténations pour commencer.

Answer 1

Vous pouvez toujours utiliser simplement Data.Sequence.

Une implémentation bien connue d'une file d'attente purement fonctionnelle consiste à utiliser deux listes. Un pour enqueue et un autre pour dequeue. Enqueue serait simplement contre avec la liste de mise en file d'attente. Dequeue prend la tête de la liste dequeue. Lorsque la liste dequeue est vide, remplissez-la en inversant la liste de mise en file d'attente. Voir Purely Functional Datastructures. de

de

Même si cette implémentation utilise reverse, le coût en temps amorti de ce dernier est insignifiant asymptotiquement Cela fonctionne de sorte que pour chaque mise en file d'attente, vous encourez une dette de temps de Θ (1) pour la recharge de la liste de dequeue. L'heure prévue d'une file d'attente est donc le double de celle d'une mise en file d'attente. C'est un facteur constant, donc le coût des deux opérations est Θ (1).

Answer 2

Je ne suis pas vraiment un utilisateur de Haskell, mais j'ai trouvé a blog post qui prétend décrire une file d'attente Haskell qui peut être utilisée en temps constant amorti. Il est basé sur une conception des excellentes structures de données purement fonctionnelles de Chris Okasaki.

Answer 3

Est-ce que Data.Dequeue est ce que vous cherchez?

(Il n'a pas reverse mais vous pouvez l'ajouter assez facilement et envoyer un patch à l'auteur.)