purescript / purescript-catenable-lists Goto Github PK

Hi Guys
Just wondering if you've considered adding double endedness to CatQueue?
I see the papers mention it as a dequeue, and @MonoidMusician speculated it was absent just for time?

Thanks
Alex

I'd be interested to see a benchmark for, say, N cons operations followed by N uncons operations, or snoc-then-uncons, etc.

When we make the next round of breaking changes (e.g. v0.15.0 of PureScript), this is a reminder to remove all MonadZero instances. Relates to #42, which censors user-defined warnings due to the MonadZero instance. The build command should be updated to fail on any warning once we've removed the instance.

For now I've updated the tests and whatnot to use the RCs, but once everything is properly released and we start updating dependants we can put the benchmarks back in too.

Missing TC instances for CatList.

The code for CatQueue cites 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?

Is there a fundamental reason for the lack of Functor, etc other than need and the will to implement them?

• Eq
• Ord
• Semigroup
• Monoid
• Foldable
• Unfoldable
• Traversable
• Functor
• Apply
• Applicative
• Bind
• Monad
• Alt
• Plus
• Alternative
• MonadZero
• MonadPlus

The Semigroup instance and append in #30 are implemented as foldl snoc that appends successive elements from the CatQueue on the right. In most cases, that's probably what you'd want. One could also implement a prepend as a reverse and foldl cons of elements from the left CatQueue.

foldMap and foldl on CatList are not stack-safe. They could be.

There seems to be nothing particularly "Catty" about CatQueue. Perhaps, with the additional PRs I've made, it could live in its own lib, and get pulled in here?