具有间隔作为键和类似zip的组合操作的类似地图的容器

Question

我正在寻找一个像Data.Map使用区间作为键的Haskell容器类型,其中最左侧和最右侧的键也可以是无界区间,但在其他方面不重叠.此外,容器应该支持类似于zipWith允许将两个容器合并为一个新容器的函数,使用两个键集的交集作为新键集和两个值集的逐点组合的参数函数.

已有几个包提供基于区间的地图.我看了一下IntervalMap,fingertree和SegmentTree,但这些包装似乎提供所需的组合功能.它们似乎都使用交集函数的间隔,在两个映射中都是相等的,而我需要一个版本,如果需要,可以将间隔分解为较小的间隔.

容器应基本上为表单的键/值系列提供有效且可存储的映射Ord k => k -> Maybe a,即仅在特定间隔上定义的函数或具有映射到相同值的较大间隔的函数.

这是一个展示问题的小例子:

... -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

第一个系列可以通过映射有效表达,[-infinity, -1] -> -1; [0, 0] -> 0; [1, infinity] -> 1第二个系列可以通过映射有效表示[-infinity, infinity] -> 5.现在应用具有(*)as arument函数的组合函数应该给出一个新的系列

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

这里的关键点 - 以及所有上述软件包似乎都无法做到 - 就是说,当组合这两个系列的密钥集时,您还必须考虑不同的值.两个系列都涵盖了整个系列,[-infinity, infinity]但有必要将其分为最终系列的三个部分.

还有用于处理间隔的range包,例如包,其还在间隔列表上提供交叉操作.但是,我没有找到一种方法将其与其中一个Map变体结合使用,因为它在使用它们进行计算时会折叠邻接区间.

注意:这样的容器有点类似于ZipList延伸到两侧的容器,这就是为什么我认为也应该可以Applicative为它定义一个合法的实例,其中<*>对应于上述组合功能.

简而言之,是否已经有提供这种容器的包装？或者是否有一种简单的方法来使用现有的包来构建一个？

Answer 1

从上面的评论中，最好的建议似乎是step-functionB. Mehta 所建议的软件包。我还没有尝试过该包，但看起来围绕该SF类型构建一个包装器正是我正在寻找的。

\n\n\n\n

与此同时，我实现了另一个我想分享的解决方案。组合函数的代码（combineAscListWith在下面的代码中）有点笨拙，因为它比仅仅获取两个映射的交集更通用，所以我将概述这个想法：

\n\n

首先，我们需要一个Interval带有实例的类型Ord，该实例存储值对Val a，这些值可以是-无穷大、某个值 x 或+无穷大。我们可以构建一个将这些间隔映射到最终值的IntervalMap法线。Map

\n\n

当通过交集组合两个这样的映射时IntervalMaps，我们首先将映射转换为键/值对列表。接下来，我们并行遍历两个列表，将两个列表压缩到另一个列表中，该列表对应于最终的交集图。组合列表元素时主要有两种情况：

\n\n

\n
1. 最左边的两个间隔都以相同的值开始。在这种情况下，我们发现了一个实际上重叠/相交的区间。我们将较长的间隔剪裁为较短的间隔，并使用与两个间隔关联的值来获取结果值，现在\xe2\x80\x94 与较短的间隔\xe2\x80\x94 一起进入结果列表。较长间隔的其余部分返回到输入列表。
\n
2. 其中一个间隔的起始值小于另一个间隔的值，这意味着我们发现两个系列的一部分不重叠。所以对于交集来说，区间中所有不重叠的部分（甚至整个区间）都可以被丢弃。其余的（如果有的话）返回到输入列表。
\n

\n\n

为了完整起见，这里是完整的示例代码。同样，代码相当笨拙；基于阶跃函数的实现肯定会更加优雅。

\n\n

import           Control.Applicative\nimport           Data.List\nimport qualified Data.Map as Map\n\n\ndata Val a = NegInf | Val a | Inf deriving (Show, Read, Eq, Ord)\n\ninstance Enum a => Enum (Val a) where\n    succ v = case v of\n        NegInf -> NegInf\n        Val x  -> Val $ succ x\n        Inf    -> Inf\n    pred v = case v of\n        NegInf -> NegInf\n        Val x  -> Val $ pred x\n        Inf    -> Inf\n    toEnum = Val . toEnum\n    fromEnum (Val x) = fromEnum x\n\n\ndata Interval a = Interval { lowerBound :: Val a, upperBound :: Val a } deriving (Show, Read, Eq)\n\ninstance Ord a => Ord (Interval a) where\n    compare ia ib = let (a, a\') = (lowerBound ia, upperBound ia)\n                        (b, b\') = (lowerBound ib, upperBound ib)\n                    in  case () of\n                            _ | a\' < b             -> LT\n                            _ | b\' < a             -> GT\n                            _ | a == b && a\' == b\' -> EQ\n                            _ -> error "Ord.Interval.compare: undefined for overlapping intervals"\n\n\nnewtype IntervalMap i a = IntervalMap { unIntervalMap :: Map.Map (Interval i) a }\n                          deriving (Show, Read)\n\ninstance Functor (IntervalMap i) where\n    fmap f = IntervalMap . fmap f . unIntervalMap\n\ninstance (Ord i, Enum i) => Applicative (IntervalMap i) where\n    pure = IntervalMap . Map.singleton (Interval NegInf Inf)\n    (<*>) = intersectionWith ($)\n\n\nintersectionWith :: (Ord i, Enum i) => (a -> b -> c)\n                 -> IntervalMap i a -> IntervalMap i b -> IntervalMap i c\nintersectionWith f = combineWith (liftA2 f)\n\ncombineWith :: (Ord i, Enum i) => (Maybe a -> Maybe b -> Maybe c)\n            -> IntervalMap i a -> IntervalMap i b -> IntervalMap i c\ncombineWith f (IntervalMap mpA) (IntervalMap mpB) =\n    let cs = combineAscListWith f (Map.toAscList mpA) (Map.toAscList mpB)\n    in IntervalMap $ Map.fromList [ (i, v) | (i, Just v) <- cs ]\n\ncombineAscListWith :: (Ord i, Enum i) => (Maybe a -> Maybe b -> c)\n            -> [(Interval i, a)] -> [(Interval i, b)] -> [(Interval i, c)]\ncombineAscListWith f as bs = case (as, bs) of\n    ([], _) -> map (\\(i, v) -> (i, f Nothing (Just v))) bs\n    (_, []) -> map (\\(i, v) -> (i, f (Just v) Nothing)) as\n    ((Interval a a\', va) : as\', (Interval b b\', vb) : bs\')\n        | a == b -> case () of\n            _ | a\' == b\' -> (Interval a a\', f (Just va) (Just vb)) : combineAscListWith f as\' bs\'\n            _ | a\' < b\'  -> (Interval a a\', f (Just va) (Just vb)) : combineAscListWith f as\' ((Interval (succ a\') b\', vb) : bs\')\n            _ | a\' > b\'  -> (Interval a b\', f (Just va) (Just vb)) : combineAscListWith f ((Interval (succ b\') a\', va) : as\') bs\'\n        | a < b  -> case () of\n            _ | a\' < b   -> ((Interval a a\', f (Just va) Nothing)) :\n                (if succ a\' == b then id else ((Interval (succ a\') (pred b), f Nothing Nothing) :)) (combineAscListWith f as\' bs)\n            _ | True     -> (Interval a (pred b), f (Just va) Nothing) : combineAscListWith f ((Interval b a\', va) : as\') bs\n        | a > b  -> case () of\n            _ | b\' < a   -> ((Interval b b\', f Nothing (Just vb))) :\n                (if succ b\' == a then id else ((Interval (succ b\') (pred a), f Nothing Nothing) :)) (combineAscListWith f as bs\')\n            _ | True     -> (Interval b (pred a), f Nothing (Just vb)) : combineAscListWith f as ((Interval a b\', vb) : bs\')\n\n\nshowIntervalMap :: (Show i, Show a, Eq i) => IntervalMap i a -> String\nshowIntervalMap = intercalate "; " . map (\\(i, v) -> showInterval i ++ " -> " ++ show v)\n    . Map.toAscList . unIntervalMap\n    where\n        showInterval (Interval (Val a) (Val b)) | a == b = "[" ++ show a ++ "]"\n        showInterval (Interval a b) = "[" ++ showVal a ++ " .. " ++ showVal b ++ "]"\n        showVal NegInf  = "-inf"\n        showVal (Val x) = show x\n        showVal Inf     = "inf"\n\nmain :: IO ()\nmain = do\n    let signumMap = IntervalMap $ Map.fromList [(Interval NegInf (Val $ -1), -1),\n            (Interval (Val 0) (Val 0), 0), (Interval (Val 1) Inf, 1)]\n    putStrLn $ showIntervalMap $ (*) <$> signumMap <*> pure 5\n

\n