dictionary - 用于在 map 上插入和总查找的 Monad 转换器？

Question

我有一个计算，我将值插入到 Map然后再次查找它们。我知道我在插入之前从不使用 key ，而是使用 (!)无论如何，自由地让我紧张。我正在寻找一种方法来获得不返回 Maybe 的总查找函数。 ，并且类型系统可以防止我意外滥用。

我的第一个想法是制作一个类似于 StateT 的单子(monad)转换器。 ，其中状态为 Map并且在 monad 中有用于插入和查找的特殊功能。插入函数返回 Receipt s k新类型，其中 s是 ST 样式的幻像索引类型单子(monad)和 k是键的类型，查找函数采用 Receipt而不是裸 key 。通过隐藏 Receipt构造函数并使用类似于 runST 的量化运行函数，这应该确保仅在插入同一映射后发生查找。 (完整代码如下。)

但我担心我重新发明了一个轮子，或者担心有另一种方法可以安全地进行全 map 查找，并且已经在使用中。在某处的公共(public)包中是否有针对此问题的现有技术？

{-# LANGUAGE DeriveFunctor, LambdaCase, RankNTypes #-}

module KeyedStateT (KeyedStateT, Receipt, insert, lookup, receiptToKey, runKeyedStateT)
where

import Prelude hiding (lookup)
import Control.Arrow ((&&&))
import Control.Monad (ap, (>=>))
import Data.Map (Map)
import qualified Data.Map as Map
import Data.Maybe (fromJust)

newtype KeyedStateT s k v m a = KeyedStateT (Map k v -> m (a, Map k v)) deriving Functor

keyedState :: Applicative m => (Map k v -> (a, Map k v)) -> KeyedStateT s k v m a
keyedState f = KeyedStateT (pure . f)

instance Monad m => Applicative (KeyedStateT s k v m) where
  pure = keyedState . (,)
  (<*>) = ap

instance Monad m => Monad (KeyedStateT s k v m) where
  KeyedStateT m >>= f = KeyedStateT $ m >=> uncurry ((\(KeyedStateT m') -> m') . f)

newtype Receipt s k = Receipt { receiptToKey :: k }

insert :: (Applicative m, Ord k) => k -> v -> KeyedStateT s k v m (Receipt s k)
insert k v = keyedState $ const (Receipt k) &&& Map.insert k v

lookup :: (Applicative m, Ord k) => Receipt s k -> KeyedStateT s k v m v
lookup (Receipt k) = keyedState $ (Map.! k) &&& id

runKeyedStateT :: (forall s. KeyedStateT s k v m a) -> m (a, Map k v)
runKeyedStateT (KeyedStateT m) = m Map.empty

module Main where

import Data.Functor.Identity (runIdentity)
import qualified KeyedStateT as KS

main = putStrLn . fst . runIdentity $ KS.runKeyedStateT $ do
  one <- KS.insert 1 "hello"
  two <- KS.insert 2 " world"
  h <- KS.lookup one
  w <- KS.lookup two
  pure $ h ++ w

编辑:一些评论者问我为什么要坚持 Receipt而不是实际值。我希望能够使用 Receipt在 Set s 和 Map s(我没有在我的 MVCE 中添加 Eq 的 Ord 和 Receipt 实例，但我的项目中有它们)，但是我的 Map 中的值不相等。如果我更换了 Receipt使用键值对新类型，我必须实现不诚实的 Eq例如那对无视值(value)的，然后我会对此感到紧张。 Map是否可以确保在任何给定时间我的任何等效“代理”键都只考虑一个值。

我想一个对我来说很好的替代解决方案是一个单子(monad)变压器，它提供 Ref 的电源。 s，其中 data Ref v = Ref Int v , monad 确保 Ref s 以唯一的 Int 给出ID 和 Eq Ref等只看 Int (现在， Int 的唯一性保证了诚实)。我也会接受指向野外这种变压器的指针。

Answer 1

您的解决方案类似于 justified-containers 使用的技术保证键存在于映射中。但是有一些区别:

justified-containers使用延续传递风格。

inserting justified-containers 中的新键需要“回收”现有收据才能在更新后的 map 中使用。似乎您不需要“回收”收据，因为您永远不会同时拥有多个版本的 map 。

justified-containers支持key deletion .我不确定您的解决方案是否可以扩展以允许相同。

justified-containers 使用的技术的扩展描述可以在功能性珍珠 "Ghosts of departed proofs"中找到.