hub.darcs.net :: ross -> fingertree -> issue

treeowl

The priority queues in this package are implemented essentially as annotated deques. Their documentation doesn't make this structure as clear as it could be, and there aren't enough operations available to take full advantage. I propose adding the following operations, with approximately the following documentation:

-- | A `PQueue k v` represents a mapping between priorities
-- and ordered sequences of values.
data PQueue p v

-- | \( O(1) \) Insert a priority and value into a 'PQueue'. If the priority
-- is already present, this adds the value to the /left/ of its
-- value sequence.
insertL :: Ord p => p -> v -> PQueue p v -> PQueue p v

-- | \( O(1) \) Insert a priority and value into a 'PQueue'. If the priority
-- is already present, this adds the value to the /right/ of
-- its value sequence.
insertR :: Ord p => PQueue p v -> p -> v -> PQueue p v

-- | \( O(\log n) \) Delete and view the /leftmost/ value associated with the
-- /minimal/ key. If there is only one value associated with
-- the key, this deletes the key.
minViewL :: Ord p => PQueue p v -> MinView p v

-- | \( O(\log n) \) Delete and view the /rightmost/ value associated with the
-- /minimal/ key. If there is only one value associated with
-- the key, this deletes the key.
minViewR :: Ord p => PQueue p v -> MinView p v

data MinView p v
  = MinView !p v (PQueue p v)
  | EmptyPQ

-- | Adjust the first/last value associated with the minimal key. These
-- avoid any tree restructuring and also avoid rebuilding the annotations.
adjustMinValueL, adjustMinValueL', adjustMinValueR, adjustMinValueR'
  :: Ord p => (p -> v -> v) -> PQueue p v -> PQueue p v

Why don't I propose viewl and viewr, and documenting this structure as representing an /association list/? That's certainly possible too. However, I'd like to leave open the option of replacing the Entry leaves of the structure with this type:

data Leaf p v
    -- Assume UNPACK pragmas on all the entries.
    -- Invariant: the entries are sorted by key.
  = Leaf2 !(Entry p v) !(Entry p v)
  | Leaf3 !(Entry p v) !(Entry p v) !(Entry p v)

This change in representation makes each tree one level shorter (less indirection), reduces memory residency per entry by over 2 words, and reduces allocation slightly when changes are made.