The code for CatQueue cites Okasaki, 1995:
|
-- | See [Simple and Efficient Purely Functional Queues and Dequeues](http://www.westpoint.edu/eecs/SiteAssets/SitePages/Faculty%20Publication%20Documents/Okasaki/jfp95queue.pdf) (Okasaki 1995) |
This is a bit puzzling, as the actual implementation is not the lazy-list based one proposed in that paper, but rather the more "traditional" implementation that Okasaki attributes to other authors:
The standard trick, reinvented many times (Hood and Melville, 1981; Gries, 1981;
Burton, 1982), is to represent the queue as a pair of lists hL, Ri where L is the front
portion of the queue and R is the rear portion of the queue in reverse order...
Perhaps it is worth amending that comment?
The code for
CatQueuecites Okasaki, 1995:purescript-catenable-lists/src/Data/CatQueue.purs
Line 8 in da5091b
This is a bit puzzling, as the actual implementation is not the lazy-list based one proposed in that paper, but rather the more "traditional" implementation that Okasaki attributes to other authors:
Perhaps it is worth amending that comment?