6

我有一个计算，我将值插入到 a 中Map，然后再次查找它们。我知道在插入之前我从来没有使用过钥匙，但(!)随意使用会让我感到紧张。我正在寻找一种方法来获得一个不返回 a 的总查找函数，Maybe并且类型系统可以防止我意外滥用。

我的第一个想法是制作一个类似于 的 monad 转换器StateT，其中状态为 aMap并且在 monad 中有用于插入和查找的特殊功能。insert 函数返回一个Receipt s knewtype，其中s是STmonad风格的幻象索引类型，k是 key 的类型，lookup 函数采用 aReceipt而不是裸 key。通过隐藏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

编辑：一些评论者问我为什么要保留 aReceipt而不是实际值。我希望能够使用Receiptin Sets 和Maps （我没有在我的 MVCE 中添加EqandOrd实例Receipt，但我的项目中有它们），但我的值Map是不相等的。如果我Receipt用键值对 newtype 替换，我将不得不Eq为该对实现一个不诚实的实例，而忽略该值，然后我会对此感到紧张。这Map是为了确保在任何给定时间我的任何等效“代理”键都只考虑一个值。

我想一个对我来说很好的替代解决方案是一个 monad 转换器，它提供Refs 的供应，其中data Ref v = Ref Int vmonad 确保Refs 以唯一的IntID 给出，Eq Ref等等。只看Int（现在诚实由Ints) 的唯一性保证。我也会接受指向野外这种变压器的指针。

4

1 回答 1

3

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

可以在功能性明珠“已故证明的幽灵”中找到对合理容器使用的技术的扩展描述。

于 2019-05-16T16:49:54.510 回答