Map-like container with intervals as keys and zip-like combining operation

Question

I'm looking for a Haskell container type like Data.Map that uses intervals as keys, where the left-most and right-most keys may also be unbounded intervals, but are otherwise non-overlapping. Additionally, the container should support a function similar to zipWith that allows to merge two containers into a new one, using the intersection of both key sets as the new key set and the argument function for a pointwise combination of both value sets.

There already are several packages that provide interval-based maps. I've had a look at IntervalMap, fingertree and SegmentTree, but none of these packages seem to provide the desired combination function. They all seem to use intervals for the intersection functions, that are equal in both maps, while I need a version that breaks intervals down into smaller ones if necessary.

The container should basically provide an efficient and storable mapping for key/value series of the form Ord k => k -> Maybe a, i.e. functions only defined on specific intervals or having larger intervals mapping to the same value.

Here is a small example to demonstrate the issue:

... -4 -3 -2 -1  0  1  2  3  4  ...  -- key set
-----------------------------------
... -1 -1 -1 -1  0  1  1  1  1  ...  -- series corresponding to signum
...  5  5  5  5  5  5  5  5  5  ...  -- series corresponding to const 5

The first series could be efficiently expressed by a mapping [-infinity, -1] -> -1; [0, 0] -> 0; [1, infinity] -> 1 and the second one by [-infinity, infinity] -> 5. Now applying a combination function with (*) as arument function should give a new series

... -4 -3 -2 -1  0  1  2  3  4  ...  -- key set
-----------------------------------
... -5 -5 -5 -5  0  5  5  5  5  ...  -- combined series

The crucial point here—and all of the afore-mentioned packages don't seem to be able to do that—is that, when combining the key sets for these two series, you have to take the different values also into account. Both series span the full range of [-infinity, infinity] but it's necessary to break it into three parts for the final series.

There are also packages for working with intervals, e.g. the range package, which also provides an intersection operation on lists of intervals. However, I didn't found a way to use that in combination with one of the Map variants because it collapses adjacents intervals when doing calculations with them.

NB: Such a container is somewhat similar to a ZipList that extends to both sides, which is why I think it should also be possible to define a lawful Applicative instance for it, where <*> corresponds to the above-mentioned combining function.

To cut a long story short, is there already a package that provides such a container? Or is there an easy way to use the existing packages to build one?

Bozuwa

I'm not sure which use cases of yours I'm missing, but why would functions of the type Ord k => k -> Maybe a be a bad solution? – Coheir

@Coheir The series should be defined dynamically and be stored in a file eventually. While the former would be doable with a function (not sure how efficiently), I see no way for the latter. – Bozuwa

Can the intervals within one container overlap? – Garlinda

I think scalendar does essentially what you're asking for. A bit stupidly, it's not at all set up as a container though but... well, as a calendar, totally domain-specific. – Garlinda

@Bozuwa How do you expect to store the series in a file if the series can be unbounded? – Transferor

@Garlinda They do not need to overlap for my use case, though it wouldn't hurt if the implementation allows for it – Bozuwa

@4castle The infinite parts may only occur at the left-most or right-most side of the series, so they would fit into a single interval [-infinity, x] or [x, infinity]. The representation of the series will always be finite – Bozuwa

Does step-function meet your requirements? In particular, the Applicative instance for merging appears appropriate. Perhaps SF k (Maybe a) with k an instance of Ord for partial functions, and the show function for storage. – Pail

Answer 1

The best suggestion from the comments above seems to be the step-function package, as suggested by B. Mehta. I haven't tried that package yet, but it looks like building a wrapper around that SF type is what I was looking for.

---

Meanwhile, I implemented another solution which I'd like to share. The code for the combining function (combineAscListWith in the code below) is a bit clumsy as it's more general than for just getting the intersection of both maps, so I'll sketch the idea:

First we need an Interval type with an Ord instance which stores pairs of Val a values which can either be -infinity, some value x or +infinity. Form that we can build an IntervalMap which is just a normal Map that maps these intervals to the final values.

When combining two such IntervalMaps by intersection, we first convert the maps into lists of key/value pairs. Next we traverse both lists in parallel to zip both lists into another one which corresponds to the final intersection map. There are two main cases when combining the list elements:

1. Both left-most intervals start at the same value. In that case we found an interval that actually overlaps/intersects. We clip the longer interval to the shorter one, and use the values associated with the two intervals to get the result value, which now—together with the shorter interval—goes into the result list. The rest of the longer interval goes back to the input lists.
2. One of the intervals starts at a smaller value than the other, which means we found a part of the two series that do not overlap. So for the intersection, all of the non-overlapping part of the interval (or even the whole interval) can be discared. The rest (if any) goes back to the input list.

For completeness, here's the full example code. Again, the code is rather clumsy; a step-function-based implementation would certainly be more elegant.

import           Control.Applicative
import           Data.List
import qualified Data.Map as Map


data Val a = NegInf | Val a | Inf deriving (Show, Read, Eq, Ord)

instance Enum a => Enum (Val a) where
    succ v = case v of
        NegInf -> NegInf
        Val x  -> Val $ succ x
        Inf    -> Inf
    pred v = case v of
        NegInf -> NegInf
        Val x  -> Val $ pred x
        Inf    -> Inf
    toEnum = Val . toEnum
    fromEnum (Val x) = fromEnum x


data Interval a = Interval { lowerBound :: Val a, upperBound :: Val a } deriving (Show, Read, Eq)

instance Ord a => Ord (Interval a) where
    compare ia ib = let (a, a') = (lowerBound ia, upperBound ia)
                        (b, b') = (lowerBound ib, upperBound ib)
                    in  case () of
                            _ | a' < b             -> LT
                            _ | b' < a             -> GT
                            _ | a == b && a' == b' -> EQ
                            _ -> error "Ord.Interval.compare: undefined for overlapping intervals"


newtype IntervalMap i a = IntervalMap { unIntervalMap :: Map.Map (Interval i) a }
                          deriving (Show, Read)

instance Functor (IntervalMap i) where
    fmap f = IntervalMap . fmap f . unIntervalMap

instance (Ord i, Enum i) => Applicative (IntervalMap i) where
    pure = IntervalMap . Map.singleton (Interval NegInf Inf)
    (<*>) = intersectionWith ($)


intersectionWith :: (Ord i, Enum i) => (a -> b -> c)
                 -> IntervalMap i a -> IntervalMap i b -> IntervalMap i c
intersectionWith f = combineWith (liftA2 f)

combineWith :: (Ord i, Enum i) => (Maybe a -> Maybe b -> Maybe c)
            -> IntervalMap i a -> IntervalMap i b -> IntervalMap i c
combineWith f (IntervalMap mpA) (IntervalMap mpB) =
    let cs = combineAscListWith f (Map.toAscList mpA) (Map.toAscList mpB)
    in IntervalMap $ Map.fromList [ (i, v) | (i, Just v) <- cs ]

combineAscListWith :: (Ord i, Enum i) => (Maybe a -> Maybe b -> c)
            -> [(Interval i, a)] -> [(Interval i, b)] -> [(Interval i, c)]
combineAscListWith f as bs = case (as, bs) of
    ([], _) -> map (\(i, v) -> (i, f Nothing (Just v))) bs
    (_, []) -> map (\(i, v) -> (i, f (Just v) Nothing)) as
    ((Interval a a', va) : as', (Interval b b', vb) : bs')
        | a == b -> case () of
            _ | a' == b' -> (Interval a a', f (Just va) (Just vb)) : combineAscListWith f as' bs'
            _ | a' < b'  -> (Interval a a', f (Just va) (Just vb)) : combineAscListWith f as' ((Interval (succ a') b', vb) : bs')
            _ | a' > b'  -> (Interval a b', f (Just va) (Just vb)) : combineAscListWith f ((Interval (succ b') a', va) : as') bs'
        | a < b  -> case () of
            _ | a' < b   -> ((Interval a a', f (Just va) Nothing)) :
                (if succ a' == b then id else ((Interval (succ a') (pred b), f Nothing Nothing) :)) (combineAscListWith f as' bs)
            _ | True     -> (Interval a (pred b), f (Just va) Nothing) : combineAscListWith f ((Interval b a', va) : as') bs
        | a > b  -> case () of
            _ | b' < a   -> ((Interval b b', f Nothing (Just vb))) :
                (if succ b' == a then id else ((Interval (succ b') (pred a), f Nothing Nothing) :)) (combineAscListWith f as bs')
            _ | True     -> (Interval b (pred a), f Nothing (Just vb)) : combineAscListWith f as ((Interval a b', vb) : bs')


showIntervalMap :: (Show i, Show a, Eq i) => IntervalMap i a -> String
showIntervalMap = intercalate "; " . map (\(i, v) -> showInterval i ++ " -> " ++ show v)
    . Map.toAscList . unIntervalMap
    where
        showInterval (Interval (Val a) (Val b)) | a == b = "[" ++ show a ++ "]"
        showInterval (Interval a b) = "[" ++ showVal a ++ " .. " ++ showVal b ++ "]"
        showVal NegInf  = "-inf"
        showVal (Val x) = show x
        showVal Inf     = "inf"

main :: IO ()
main = do
    let signumMap = IntervalMap $ Map.fromList [(Interval NegInf (Val $ -1), -1),
            (Interval (Val 0) (Val 0), 0), (Interval (Val 1) Inf, 1)]
    putStrLn $ showIntervalMap $ (*) <$> signumMap <*> pure 5

Bozuwa