Монадный трансформатор для вставок и полных поисков на карте? - PullRequest
Новая
       60

Монадный трансформатор для вставок и полных поисков на карте?

6 голосов
/ 16 мая 2019

У меня есть вычисление, в котором я вставляю значения в Map, а затем снова их ищу. Я знаю, что никогда не использую ключ перед тем, как вставить его, но использование (!) в любом случае заставляет меня нервничать. Я ищу способ получить функцию полного поиска, которая не возвращает Maybe и которую система типов предотвращает от случайного злоупотребления.

Моей первой мыслью было создать монадный преобразователь, подобный StateT, где состояние равно Map и в монаде есть специальные функции для вставок и поиска. Функция вставки возвращает Receipt s k newtype, где s - это тип фантомного индекса в стиле монады ST, k - тип ключа, а функция поиска принимает 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

Редактировать: Несколько комментаторов спросили, почему я хочу удерживать Receipt вместо действительного значения. Я хочу использовать Receipt в Set s и Map s (я не добавил экземпляры Eq и Ord для Receipt в моем MVCE, но у меня они есть в моем проект), но значения в моем Map не равны. Если бы я заменил Receipt на новый тип пары ключ-значение, мне пришлось бы реализовать нечестный экземпляр Eq для этой пары, который игнорировал бы значение, и тогда я был бы обеспокоен этим. Map предназначен для того, чтобы в любой момент времени можно было рассмотреть только одно значение для любого из моих уравновешенных «прокси» ключей.

Я полагаю, что альтернативное решение, которое будет работать нормально для меня, - это монадный трансформатор, обеспечивающий питание Ref с, где data Ref v = Ref Int v, с монадой, обеспечивающей выдачу Ref с уникальным Int идентификаторов и Eq Ref и т. Д. Только с учетом Int (и теперь честность гарантируется уникальностью Int с). Я бы согласился и с указателями на такой трансформатор в дикой природе.

1 Ответ

3 голосов
/ 16 мая 2019

Ваше решение напоминает методику, используемую justify-container , чтобы гарантировать наличие ключей на карте. Но есть некоторые отличия:

  • выровненные контейнеры использует стиль продолжения.

  • вставка нового ключа в justeed-container требует "повторного использования" существующих квитанций для работы на обновленной карте. Похоже, вам не нужно «переписывать» квитанции, потому что у вас никогда не бывает нескольких версий карты одновременно.

  • justeed-container поддерживает удаление ключа . Я не уверен, что ваше решение может быть расширено, чтобы разрешить то же самое.

Расширенное описание техники, используемой оправданных контейнеров , можно найти в функциональной жемчужине "Призраки умерших доказательств" .

...