purescript-catenable-lists icon indicating copy to clipboard operation
purescript-catenable-lists copied to clipboard

Clarification of CatQueue implementation

Open matthewleon opened this issue 7 years ago • 0 comments

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?

matthewleon avatar Feb 12 '18 20:02 matthewleon