Make the Foldable/Traversable order meaningful

[treeowl]

Currently, we traverse the tree in pre-order, using the derived Foldable and Traversable. This order has no semantic significance whatsoever. The obvious thing, IMO, is to traverse in key order. Additionally, we should offer functions to fold/traverse with access to the keys and priorities.

[treeowl]

I think these do the trick, but I haven't written any tests yet:

traverseWithKP :: Applicative f => (k -> p -> v -> f w) -> OrdPSQ k p v -> f (OrdPSQ k p w)
traverseWithKP f = start
  where
    start Void = pure Void
    start (Winner (E k p v) Start m) = (\w -> Winner (E k p w) Start m) <$> f k p v
    start (Winner e (RLoser s e' tl m tr) m')
      = liftA2
           (\(Wonder eP tlP) (Wonder e'P trP) ->
               Winner eP (RLoser s e'P tlP m trP) m')
           (go (Wonder e tl)) (go (Wonder e' tr))
    start (Winner e (LLoser s e' tl m tr) m')
      = liftA2
           (\(Wonder e'P tlP) (Wonder eP trP) ->
               Winner eP (LLoser s e'P tlP m trP) m')
           (go (Wonder e' tl)) (go (Wonder e tr))

    go (Wonder (E k p v) Start) = (\w -> Wonder (E k p w) Start) <$> f k p v
    go (Wonder e (RLoser s e' tl m tr))
      = liftA2 (\(Wonder eP tlP) (Wonder e'P trP)
          -> Wonder eP (RLoser s e'P tlP m trP))
        (go (Wonder e tl)) (go (Wonder e' tr))
    go (Wonder e (LLoser s e' tl m tr))
      = liftA2
           (\(Wonder e'P tlP) (Wonder eP trP) ->
               Wonder eP (LLoser s e'P tlP m trP))
           (go (Wonder e' tl)) (go (Wonder e tr))

data Wonder k p v
  = Wonder !(Elem k p v)
           !(LTree k p v)

foldMapWithKP :: Monoid m => (k -> p -> v -> m) -> OrdPSQ k p v -> m
foldMapWithKP f = getConst . traverseWithKP (coerce f)

[treeowl]

That seems like overkill for the fold, though it will work. We can write it thus:

foldMapWithKP f = go
  where
    go Void = mempty
    go (Winner (E k p v) Start _m) = f k p v
    go (Winner e (RLoser _s e' tl m tr) m')
      = go (Winner e tl m) `mappend` go (Winner e' tr m')
    go (Winner e (LLoser _s e' tl m tr) m')
      = go (Winner e' tl m) `mappend` go (Winner e tr m')

I'm not sure which is better for performance; the difference likely isn't huge.

[treeowl]

We can write similar things for both left and right folds, lazy and strict.

[jaspervdj]

I actually like that the derived fold has no obvious meaning -- this prevents users from relying on it which would allow us to change out the implementation. If there is a good use case for having a key-order fold, I would suggest adding this as fold{l,r}Xyz rather than foldXyz, if that makes sense?

[treeowl]

I disagree. When there's one "most natural" order of traversal, I believe that's the one that should get the TraversableWithIndex instance. FWIW, that's how pqueue does it: the instances are nicely ordered, but there are also functions for folding/traversing in an unspecified order.

[jaspervdj]

I agree with the statement that if there's a most natural order of traversal, this should be picked for Foldable / Traversable (leaving WithIndex out of this for now).

In this case, however, I think if the user is unfamiliar with the implementation, both key-order and priority-order could be considered very natural, so I don't think there is a "most natural" one here?

(FWIW, I think this answer would be different if the type was called something like FingerTreeQueue rather than OrdPSQ, since then it would be more obvious that there is a natural order.)

[treeowl]

There are two possible "natural" orders: key, and (priority, key). Key order is linear time; (priority, key) is linearithmic. I also feel (and this is somewhat subjective) like this data structure is much more map-like than heap-like. Almost like maps with a bit of priority queue bolted on. I think this is mostly down to the fact that keys are required to be unique.