search

lspitzner / pqueue

Haskell priority queue package
Other
15 stars 13 forks source link

Strict folds #21

Open konsumlamm opened 4 years ago

konsumlamm commented 4 years ago

There are currently no strict fold operations (except for the Foldable instances ofc) in this package. Would it be worthwhile to add strict variants of the different folds that are provided (like foldrU, foldlU)? Or is there any particular reason to not include them?

Regarding the implementation, they could just be implemented like the default definitions of foldr' and foldl'.

treeowl commented 2 years ago

Yes. For min-queues, we want foldlAsc' and foldrDesc'. For max-queues, we want foldlDesc' and foldrAsc'. For all queues, we want foldlU' and possibly foldrU'. (Of course, we'll also want the WithKey versions.)

The current documentation for the unordered folds makes it pretty silly to have both left and right-handed versions. Obeying the documentation, we could define foldlWithKeyU f = foldrWithKeyU (\k a b -> f b k a). We really should either:

  1. Have foldrU and foldlU' only, or
  2. Have all the unordered folds, but document a specific relationship between the orderings they use. For example, we might want to specify that reverse . foldrU (:) [] = foldlU (flip (:)) []. I think I prefer this option.
konsumlamm commented 2 years ago

foldlU' was added in #59, so for unordered folds, this now has been addressed.