Consider a finger tree-based implementation

[treeowl]

For performance reasons, this should probably copy ideas and some (modified) code from the fingertree package, but not use its actual FingerTree type. Here's the general idea:

data MinMax k = MinMax
  { smallest :: !k
  , largest :: !k }

instance Ord k => Semigroup (MinMax k) where
  MinMax min1 max1 <> MinMax min2 max2
    = MinMax (min min1 min2) (max max1 max2)

data Entry k v = Entry !k v

data Digit a = One !a | Two !a !a | Three !a !a !a | Four !a !a !a !a
data Node k a
  = Node2 {-# UNPACK #-} !(MinMax k) !a !a
  | Node3 {-# UNPACK #-} !(MinMax k) !a !a !a
data FingerTree k a
  = Single !a
  | Deep {-# UNPACK #-} !(MinMax k) !(Digit a) (FingerTree k (Node k a)) !(Digit a)

-- Cache the values associated with the smallest
-- and largest keys so the smallest and largest entries
-- can be viewed in constant time. This is optional.
data DEPQ k v
  = Empty
  | DEPQ
      { valMin :: v
      , valMax :: v
      , FingerTree k (Entry k v) }

The code for meld can be copied from the code for >< in fingertree, but using <> instead of mappend and being stricter in the spine than what that package currently does (it will probably be fixed soon). The code for minView and maxView should be similar to the code for Data.Sequence.deleteAt, but using the search procedure in fingertree.

This implementation should offer:

• insert: persistently amortized O(1); worst-case O(log n).
• minView, maxView: O(log n)
• meld: O(log n)

[treeowl]

Aha! We can actually do something simpler. We should only need a one-fingered tree. Moreover, we don't need to be able to pop off the entry by the finger particularly quickly, so we can reduce the number of digits without deepening the trees (1 digits can be considered "safe"). So using most of the definitions above, I think we can write

data Tree k a
  = Single !a
  | One {-# UNPACK #-} !(MinMax k) !a (Tree k (Node a))
  | Two {-# UNPACK #-} !(MinMax k) !a !a (Tree k (Node a))
  | Three {-# UNPACK #-} !(MinMax k) !a !a !a (Tree k (Node a))

This needs a whole custom meld, but that's just tedious, not hard.