mapEither 同时插入 Left 和 Right

Question

对多重集使用函数 mapEither 我可以将 MultiSet 变成一对两个多重集。当 f 返回 Left 时，元素被插入对的第一个 Multiset，如果 f 返回 Right，则元素被插入第二个MultiSet 对。

如何将相同的元素同时插入到两个 MultiSet 中，就像 f 同时返回 Right 和 Left 一样？

f:: LocalType -> Either LocalType LocalType
f (Sometype lt) = Left lt -- And Right lt
f lt = Left lt

parRule :: (MultiSet LocalType) -> (MultiSet LocalType)
parRule sequent = do 
    let list = MultiSet.mapEither f sequent

作为参考，我使用 Data.Multiset 包，https://hackage.haskell.org/package/multiset-0.3.4.3/docs/Data-MultiSet.html。

Answer 1

您可以使用类似 These to capture the ability to return both. You can then use toAscOccurList 和 fromOccurList 的类型（如果您的函数是单调的，则可以使用 fromAscOccurList）来计算新的 MultiSet.

Answer 2

您可以按照 Daniel Wagner 的建议使用 These，但我会使用稍微不同的函数开始，这似乎与库 API 的匹配稍微好一些。此外，我会推荐一种不同的性能实施策略。

data SP a b = SP !a !b
toPair :: SP a b -> (a, b)
toPair (SP a b) = (a, b)

mapPairOcc :: (Ord b, Ord c) => (a -> Occur -> ((b, Occur), (c, Occur))) -> MultiSet a -> (MultiSet b, MultiSet c)
mapPairOcc f = toPair . mapPairOcc' f

mapPairOcc' :: (Ord b, Ord c) => (a -> Occur -> ((b, Occur), (c, Occur))) -> MultiSet a -> SP (MultiSet b) (MultiSet c)
mapPairOcc' f = foldl' go (SP empty empty) . toAscOccurList
  where
    go (SP bs cs) a
      | ((b, bn), (c, cn)) <- f a
      = SP (insertMany b bn bs) (insertMany c cn cs)

当您知道 f 在

的意义上是严格单调的

a < a' ==> fst (f a) < fst (f a') /\ snd (f a) < snd (f a')

可以做得更好，在 O(n) 时间内构建结果。执行此操作的最佳方法似乎是使用 Data.Map 内部构件。我将重复使用上面的 SP 类型。

import Data.Map.Lazy (Map)
import Data.MultiSet (MultiSet, Occur)
import qualified Data.MultiSet as MS
import qualified Data.Map.Internal as M
import Control.Monad (guard)

-- | Map over the keys and values in a map, producing
-- two maps with new keys and values. The passed function
-- must be strictly monotone in the keys in the sense
-- described above.
mapMaybeWithKey2Mono :: (k -> a -> (Maybe (l,b), Maybe (m,c))) -> Map k a -> (Map l b, Map m c)
mapMaybeWithKey2Mono f = toPair . mapMaybeWithKey2Mono' f

mapMaybeWithKey2Mono' :: (k -> a -> (Maybe (l,b), Maybe (m,c))) -> Map k a -> SP (Map l b) (Map m c)
mapMaybeWithKey2Mono' _ M.Tip = SP M.Tip M.Tip
mapMaybeWithKey2Mono' f (M.Bin _ kx x l r)
  | (fl, fr) <- f kx x
  = SP (groink fl mfl1 mfr1) (groink fr mfl2 mfr2)
  where
    groink :: Maybe (q, x) -> Map q x -> Map q x -> Map q x
    groink m n o = case m of
      Just (k', y) -> M.link k' y n o
      Nothing -> M.link2 n o
    SP mfl1 mfl2 = mapMaybeWithKey2Mono' f l
    SP mfr1 mfr2 = mapMaybeWithKey2Mono' f r

使用这个新的通用 Map 函数，我们可以在多重集上定义我们想要的函数：

mapPairAscOcc :: (a -> Occur -> ((b, Occur), (c, Occur))) -> MultiSet a -> (MultiSet b, MultiSet c)
mapPairAscOcc f m
  | (p, q) <- mapMaybeWithKey2Mono go . MS.toMap $ m
  = (MS.fromOccurMap p, MS.fromOccurMap q)
  where
     -- a -> Occur -> (Maybe (b, Occur), Maybe (c, Occur))
    go a aocc
      | ((b, bocc), (c, cocc)) <- f a aocc
      = ( (b, bocc) <$ guard (bocc > 0)
        , (c, cocc) <$ guard (cocc > 0) )

Answer 3

我从 Data.MultiSet 中提取了函数 mapEither 并对其进行了修改，使其支持 These 类型。

-- | /O(n)/. Map and separate the 'This' and 'That' or 'These' results 
-- modified function of mapEither to map both cases in case f return These
-- code of mapEither found in source code, 
mapThese :: (Ord b, Ord c) => (a -> These b c) -> MultiSet a -> (MultiSet b, MultiSet c)
mapThese f = (\(ls,rs) -> (MultiSet.fromOccurList ls, MultiSet.fromOccurList rs)) . mapThese' . MultiSet.toOccurList
  where mapThese' [] = ([],[])
        mapThese' ((x,n):xs) = case f x of
           This  l -> let (ls,rs) = mapThese' xs in ((l,n):ls, rs)
           That r -> let (ls,rs) = mapThese' xs in (ls, (r,n):rs)
           These u i -> let (ls,rs) = mapThese' xs in ((u,n):ls, (i,n):rs)

在 f returns These 的情况下，两个 MultiSet 都有一个添加的元素。

mapEither 同时插入 Left 和 Right

mapEither inserting both Left and Right

haskell

multiset