[FP] Functionele constant-time queue

[Soultaker]

Onlangs vroeg iemand mij of het mogelijk was om in de taal Clean een queue te maken, waarmee in constante tijd items kunnen worden toegevoegd en opgevraagd. Hoewel het hier over Clean ging, lijkt het probleem me een universeel functioneel programmeerprobleem.

Zelf heb ik al de suggestie gedaan, dat wanneer at runtime een upper bound bekend is, gebruik kan worden gemaakt van een array (waarvan het bijwerken en uitlezen in constante tijd gebeurd).

Ik heb echter geen concreet idee hoe het algemene geval (waarin de queue dus echt dynamisch groeit en krimpt) opgelost zou kunnen worden. Iemand hints of suggesties?

[Soultaker]

Ok, ik ben nu tot de volgende constructie gekomen.

Een stack implementeren in een functionele programmeertaal is eenvoudig, dat werkt gewoon met een list:

code:

Stack a :== [a]

push :: (Stack a) a -> a
push stack item = [ item : stack ]

pop :: (Stack a) -> (Stack a, a)
pop [item : stack] = (item, stack)

Lists zijn geimplementeerd als single linked lists in Clean (en andere functionele programmeertalen, gok ik). Bovenstaande functies hebben dus een constante worst-case-complexiteit. Dat is natuurlijk ideaal.

Met wat gezoek ben ik de volgende implementatie van een queue met behulp van twee stacks tegengekomen:

code:

Queue a :== (Stack a, Stack a)

push :: (Queue a) a -> a
push (A, B) item = (push A item, B)

pop :: (Queue a) -> (Queue a, a)
pop (A, []) = pop ([], reverse A)
pop (A, B ) = ((A, C), item) where (C, item) = pop B item

Het idee is hierbij dus dat we een stack hebben waar we alle elementen die in de queue komen op gooien. Als we een element uit de queue moeten halen, moet die van onderop de stack komen. We keren de stack dan in één keer om met reverse (dat kost O(n) voor n elementen in de lijst) zodat we voortaan alle tot dan toe ingevoerde elementen in constante tijd kunnen benaderen.

Het komt er dus op neer, dat elk element dat toegevoegd wordt, precies één keer een iteratie in reverse oplevert. De worst-case complexiteit van pop is weliswaar O(n), maar wanneer de queue leeg begint en eindigt, zal na X push/pop-combinates ook X keer een iteratie van reverse (en push en pop) uitgevoerd zijn. De 'amortized complexity' (wat is de Nederlandse term hiervoor?) van deze implementatie is dus wel O(1).

Natuurlijk is dit niet hetzelfde als échte constante worst-case complexiteit, maar het komt in de buurt. In de praktijk is het doorgaans zelfs goed genoeg; ik kan er in ieder geval mee leven.

[Soultaker]

For future reference; mijn uiteindelijke implementatie ziet er zo uit:

code:

::Queue t  :== ([t], [t])
EmptyQueue :== ([ ], [ ])

push :: (Queue t) t -> (Queue t)
push (a, b) x = ([x:a], b)

pop :: (Queue t) -> (Queue t, t)
pop (a, [x:b]) = ((a,b),   x)
pop (a, _    ) = (([], b), x) where [x:b] = reverse a

Leuk, zo'n topic helemaal voor jezelf.