Lazy binomial versions
- Dominant language
- Haskell
- Stars
- 34
- Forks
- 9
- PR merge metrics
- No merged PRs in 30d
Description
The lazy binomial version should be rather simpler and more compact. I suspect it will be more efficient in practice too. Does it belong in this package or elsewhere? I don't want the nasty `Foldable` trick.
```haskell
module Plain where
-- Binomial queues strict in both key and value
-- These support:
-- insertion in amortized O(1) time, worst case O(log n) time
-- deletion in O(log n) (amortized and worst case) time
-- merge in amortized O(log (min (m, n))) time and worst case O(log (max (m, n))) time
newtype Plain k a = Plain (Forest Zero k a)
data Forest rk k a
= Nil
| Skip (Forest (Succ rk) k a)
| Cons {-# UNPACK #-} !(Tree rk k a) (Forest (Succ rk) k a)
-- Note: Cons is allowed to be strict in its second field, but
-- I don't think that's actually good in practice
-- A binomial tree. The value associated with the key is
-- stored as its rightmost child.
data Tree rk k a = Tree !k !(rk k a)
newtype Zero k a = Zero a
data Succ rk k a = Succ {-# UNPACK #-} !(Tree rk k a) !(rk k a)
tip :: k -> a -> Tree Zero k a
tip k a = Tree k (Zero a)
mergeTrees :: Ord k => Tree rk k a -> Tree rk k a -> Tree (Succ rk) k a
mergeTrees t1@(Tree k1 ts1) t2@(Tree k2 ts2)
| k1 <= k2
= Tree k1 (Succ t2 ts1)
| otherwise
= Tree k2 (Succ t1 ts2)
incr :: Ord k => Tree rk k a -> Forest rk k a -> Forest rk k a
incr t Nil = Cons t Nil
incr t (Skip ts) = Cons t ts
-- force ts when cascading to
-- maintain worst-case bounds
incr t1 (Cons t2 !ts) = Skip $ incr t ts
where
!t = mergeTrees t1 t2
-- ----
module Bootstrapped where
import qualified Plain as P
import Plain (Plain)
newtype Loop a = Loop (Plain a (Loop a))
data Queue a
= Empty
| Queue !Int !a !(Plain a (Loop a))
merge (Queue sz1 a1 qs1) (Queue sz2 a2 qs2)
| a1 <= a2 = Queue (sz1 + sz2) a1 $ P.insert a2 (Loop qs2) qs1
...
```
Contributor guide
No contributing guide indexed for this repository
Research direction
Start with the Plain and Bootstrapped module sketches in the issue and inspect the existing heaps package to determine where a lazy binomial implementation could fit. Compare the proposed representation and strictness choices with current APIs and benchmarks; done means an agreed package location and a complete, validated implementation without the Foldable trick.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100