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

#20IntervalMap almost admits an applicative instance

isovector

IntervalMap very nearly has an applicative instance:

getIntersection :: Ord a => Interval a -> Interval a -> Maybe (Interval a)
getIntersection (Interval a1 a2) (Interval b1 b2) = do
  let lo = max a1 b1
      hi = min a2 b2
  case lo < hi of
    True -> Just $ Interval lo hi
    False -> Nothing

instance Applicative IntervalMap where
  pure = IM.singleton everywhere
  liftA2 f ma mb = mconcat $ do
    (ai, a) <- IM.toList ma
    (bi, b) <- IM.intersections ai mb
    i <- maybeToList $ getIntersection ai bi
    pure $ IM.singleton i $ f a b

where everywhere :: Interval k. Of course, everywhere is currently impossible to implement forall k, but the near existence of this instance makes me think the articulation of IntervalMap is not quite right.

There are a few solutions here. We could stick everywhere in a typeclass and require it for the Applicative instance. This has the advantage of being backwards compatible, but it's not beautiful.

Better, I think, would be to change Interval:

data Interval v
  = Everywhere
  | OpenStart v
  | OpenEnd v
  | Interval v v 

• Ross PatersonWed Jun 10 23:54:08 UTC 2026

  We could also define everywhere as

  everywhere :: (Bounded v) => Interval v 
  everywhere = Interval minBound maxBound

  That seems less general, but if we define

  data WithBounds a = Bottom | Middle a | Top
      deriving (Eq, Ord, Read, Show)
  
  instance Bounded (WithBounds a) where
      minBound = Bottom
      maxBound = Top

  then your Interval v is Interval (WithBounds v), so the existing definition subsumes it.

  I also suspect there may be more efficient approaches than using toList, but I haven't looked too closely.

• isovectorThu Jun 11 00:52:08 UTC 2026

  Right, sorry, yeah! I thought about using Bounded, but Bounded requires Enum and most of the types I want to use this for are not Enum :)

• isovectorThu Jun 11 02:43:23 UTC 2026

  I just looked and apparently Enum is not a superclass of Bounded? Have I been taking crazy pills all these years??? In that case, yes, I agree that taking on the bounded constraint is a good solution, and that we can use WithBounds to get it for free.

• Ross PatersonThu Jun 11 05:44:36 UTC 2026
  • status set to closed

  Enum is a superclass of Integral, but hasn't been a superclass of Bounded, at least since Haskell 98.

• Ross PatersonThu Jun 11 10:37:02 UTC 2026
  • status set to open

  Reopening this because there is still the first part. It might be useful to have an efficient implementation of

  intersectionWith :: (Ord v) => (a -> b -> c) -> IntervalMap v a -> IntervalMap v b -> IntervalMap v c

  if that were possible. It would then be easy to define an Applicative instance with a Bounded constraint.

• Ross PatersonThu Jun 11 22:54:43 UTC 2026

  It's even a monad:

  instance (Bounded v, Ord v) => Monad (IntervalMap v) where
      ma >>= k =
          fromList [(Interval (max lo_a lo_b) (min hi_a hi_b), b) |
              (ia@(Interval lo_a hi_a), a) <- assocs ma,
              (Interval lo_b hi_b, b) <- intersections ia (k a)]