mapEither插入Left和Right

使用mapEithermultiset 的函式，我可以將 aMultiSet變成一對兩個 multiset。當f回傳時Left，元素被插入到對的第一個Multiset中，如果f回傳Right，元素被插入到對中的第二個MultiSet中。

我怎樣才能插入相同的元素都將MultiSet在同一時間s，仿佛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 。

uj5u.com熱心網友回復：

您可以使用型別 likeThese來捕獲回傳兩者的能力。然后您可以使用toAscOccurListand fromOccurList（或者fromAscOccurList如果您的函式是單調的）來計算新的MultiSet.

uj5u.com熱心網友回復：

您可以These按照 Daniel Wagner 的建議使用，但我會使用稍微不同的函式作為開始，這似乎與庫 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) )

uj5u.com熱心網友回復：

我mapEither從 中獲取了該函式Data.MultiSet并對其進行了修改以使其支持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 回傳的情況下These，兩個 MultiSet 都有一個添加的元素。

標籤：哈斯克尔 多集

上一篇：如何使用show列印沒有單引號的字符？

下一篇：理解擴展歐幾里得演算法的實作