lookup value and the/a piece-wise constant component around it

[tilowiklundSensmetry]

I am sampling sections of a piece-wise constant function encoded as an IntervalMap, and for efficiency reasons it would be useful to have a lookup function that also reported the maximal (or just some non-trivial) interval around the query point on which the IntervalMap is constant. There is a quickly cooked up prototype here: tilowiklundSensmetry@8e0d144 that I am guessing would give a (not necessarily maximal) such interval, but I am not certain enough about the semantics of IntervalMap to say whether it is correct.

[Bodigrim]

It's hard to specify the semantics of this function without refering to internal implementation details. E. g., the following function satisfies properties described in your haddock:

lookupAround :: Ord k => k -> IntervalMap k a -> Maybe (Interval k, a)
lookupAround k m = case lookup k m of 
  Nothing -> Nothing 
  Just a -> Just (Interval.singleton k, a)

[tilowiklundSensmetry]

I don't think the ideal semantics are difficult to specify (the maximal interval containing the point on which the function is constant). For performance reasons this might be a bit tricky with the current implementation. Adding something like the following might be sufficient:

If m was created by at most n insertions to an empty map, then the cardinality of Set.fromList [ fst (lookAround x1 m), ..., fst (lookAround xk m) ] is O(n).

[Bodigrim]

I think returning the maximal interval is a better semantics, even if implementation is not straightforward.

[msakai]

It is documented that IntervalMap keeps adjacent mappings unmerged even though they ​are connected and mapped to the same value, and toList already returns the result that depends on such representation.

data-interval/src/Data/IntervalMap/Base.hs

Lines 121 to 126 in 6b62faf

	-- | A Map from non-empty, disjoint intervals over k to values a.
	--
	-- Unlike 'IntervalSet', 'IntervalMap' never merge adjacent mappings,
	-- even if adjacent intervals are connected and mapped to the same value.
	newtype IntervalMap r a = IntervalMap (Map (LB r) (Interval r, a))
	deriving (Eq, Typeable)

Therefore I feel it is okay for lookupAround to return the result that depends on such representation.

Also, if we implement a function that merges such adjacent mappings (which requires Eq constraint to the value type), returning the maximal interval can be achieved by simply combining the function and lookupAround.