haskell - 以区间为键的类地图容器和类 zip 组合操作
问题描述
我正在寻找像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 变体结合使用的方法,因为在使用它们进行计算时它会折叠相邻的间隔。
NB:这样的容器有点类似于向ZipList
两边延伸的a,这就是为什么我认为也应该可以Applicative
为它定义一个合法的实例,其中<*>
对应于上面提到的组合功能。
长话短说,是否已经有提供这种容器的包?或者有没有一种简单的方法可以使用现有的包来构建一个?
解决方案
step-function
正如 B. Mehta 所建议的,上述评论中最好的建议似乎是包装。我还没有尝试过那个包,但看起来SF
我正在寻找围绕该类型构建一个包装器。
同时,我实施了另一个我想分享的解决方案。组合函数的代码(combineAscListWith
在下面的代码中)有点笨拙,因为它比仅获取两个地图的交集更通用,所以我将概述这个想法:
首先,我们需要一个Interval
带有Ord
实例的类型,该实例存储Val a
可以是-infinity、某个值x 或+infinity 的值对。我们可以构建的IntervalMap
形式只是Map
将这些间隔映射到最终值的法线。
当通过交集组合两个这样IntervalMaps
的时,我们首先将映射转换为键/值对列表。接下来,我们并行遍历两个列表,将两个列表压缩到另一个对应于最终交集图的列表中。组合列表元素时主要有两种情况:
- 两个最左边的间隔都以相同的值开始。在那种情况下,我们发现了一个实际上重叠/相交的区间。我们将较长的区间裁剪为较短的区间,并使用与这两个区间相关的值来获得结果值,现在该值与较短的区间一起进入结果列表。较长时间间隔的其余部分返回输入列表。
- 其中一个区间的起始值小于另一个区间,这意味着我们发现了两个系列中不重叠的部分。所以对于交集,区间内所有不重叠的部分(甚至整个区间)都可以舍弃。其余的(如果有的话)返回输入列表。
为了完整起见,这里是完整的示例代码。同样,代码相当笨拙。基于步进函数的实现肯定会更优雅。
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
推荐阅读
- r - 根据 r 中的条件拆分字符串
- reactjs - 在 React Native (expo) 中获取实际的设备方向锁定
- android - 华为 AR 引擎 .obj 文件无法正确渲染
- php - 如果选中“运送到不同地址”
- xamarin.forms - 从相机拍摄的照片的相对布局
- google-sheets - 在 Google 电子表格中汇总经过的小时数和分钟数
- swift - 如何在 struct 函数中重新加载 CollectionView 数据?
- ag-grid - 使用企业版时浮动过滤器变灰
- c# - 如何不阻止用户界面
- angular - 带有 ID 的动态路由不呈现最近的 Angular 组件