用于在地图上进行插入和总查找的Monad转换器？

Question

我有一个计算，我在其中将值插入Map，然后再次查找它们。我知道我从来没有在插入密钥之前使用过密钥，但是(!)无论如何随意使用都会使我感到紧张。我正在寻找一种获取总查询功能的方法，该方法不会返回Maybe，并且类型系统可以防止我意外滥用。

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

但是我担心我已经重新发明了轮子，或者担心有另外一种获取安全的总地图查找的方法。在某个地方的公共包装中是否存在针对此问题的任何现有技术？

{-# 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

---

编辑：一些评论者问我为什么要保留a Receipt而不是实际值。我希望能够使用Receiptin Set和Maps（我没有在MVCE中添加Eq和Ord实例Receipt，但是我在项目中添加了它们），但是我的值Map不相等。如果Receipt用新的键值对替换，则必须Eq为该对实现一个不诚实的实例，而忽略该值，然后对此我会感到不安。该Map有保证，只有一个在任何给定的时间考虑值任我equatable“代理”键。

我想一个替代的解决方案，将工作就好了，我会是一个单子转换提供的供应Refs，其中data Ref v = Ref Int v，与单子确保Refs的给出了独特Int的ID，和Eq Ref等仅看Int（现在诚实由Ints 的唯一性保证。我也会在野外接受指向这种转换器的指针。

Answer 1

您的解决方案类似于合理容器使用的技术来保证键存在于映射中。但也存在一些差异：

• justified-containers使用连续传递风格。

• 在合理容器中插入新密钥需要“回收”现有收据以在更新的地图中工作。似乎您不需要“回收”收据，因为您永远不会同时拥有多个版本的地图。

• justified-containers支持键删除。我不确定您的解决方案是否可以扩展以允许相同的操作。

合理容器所使用的技术的扩展描述可以在功能性珍珠“Ghosts of Dedeed Pros”中找到。