purescript-catenable-lists
purescript-catenable-lists copied to clipboard
Clarification of CatQueue implementation
The code for CatQueue cites Okasaki, 1995: https://github.com/purescript/purescript-catenable-lists/blob/da5091b9fcafe46284655336c66ee758e8e0e22c/src/Data/CatQueue.purs#L8
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?