Существует ли какая-либо «обратимая хеш-таблица», подобная структуре данных?

Question

Представьте массив, который связывает числа и слова. Ровно одно число за одно слово и наоборот.

dic = [0: 'food', 
 1: 'dinner',
 2.5: 'breakfast',
  ...]

Теперь я хочу получить доступ к dic[0] и получить food и something['food'] и получить 0. Есть ли какой-либо вид обратимой хэш-таблицы в дикой природе? Насколько я знаю, только дублирование может решить эту проблему.

Answer 1

Да, это обычно делается путем объединения двух карт. Модификации немного сложнее, потому что они должны поддерживать однозначное правило.

Давайте начнем с класса для конечных карт и пары примеров для containers типов:

{-# LANGUAGE
      FunctionalDependencies
    , FlexibleInstances
    , UndecidableInstances
    , GeneralizedNewtypeDeriving #-}

module Mappy where
import Prelude hiding (lookup)
-- Example base maps
import qualified Data.Map.Strict as M
import Data.Map (Map)
import qualified Data.IntMap.Strict as IM
import Data.IntMap (IntMap)

class Mappy k v m | m -> k v where
  empty :: m
  insert :: k -> v -> m -> m
  delete :: k -> m -> m
  lookup :: k -> m -> Maybe v

instance Ord k => Mappy k a (Map k a) where
  empty = M.empty
  insert = M.insert
  delete = M.delete
  lookup = M.lookup

instance Mappy Int a (IntMap a) where
  empty = IM.empty
  insert = IM.insert
  delete = IM.delete
  lookup = IM.lookup

Теперь мы можем построить наш тип для двунаправленных карт:

data Bimap m n = Bimap !m !n
instance Show m => Show (Bimap m n) where
  showsPrec p (Bimap m _) = showParen (p > 10) $
    showString "Bimap " . showsPrec 11 m

invert :: Bimap m n -> Bimap n m
invert (Bimap m n) = Bimap n m

instance (Mappy k v kv, Mappy v k vk) => Mappy k v (Bimap kv vk) where
  empty = Bimap empty empty
  insert k v (Bimap kv vk)
    | Just k' <- lookup v vk
    = Bimap (insert k v $ delete k' kv) (insert v k vk)
    | otherwise
    = Bimap (insert k v kv) (insert v k vk)
  delete k m@(Bimap kv vk)
    | Just v <- lookup k kv
    = Bimap (delete k kv) (delete v vk)
    | otherwise
    = m
  lookup k (Bimap kv _) = lookup k kv

Мы также можем определить некоторые оболочки, чтобы упростить написание желаемых типов карт.

newtype MapMap k v = MapMap (Bimap (Map k v) (Map v k)) deriving (Show, Mappy k v)
newtype IMM v = IMM (Bimap (IntMap v) (Map v Int)) deriving (Show, Mappy Int v)