Skip to content

Clarification of CatQueue implementation #22

@matthewleon

Description

@matthewleon

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?

Metadata

Metadata

Assignees

No one assigned

    Labels

    status: needs more infoThis issue needs more info before any action can be done.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions