Связанные семейства данных и перекрывающиеся экземпляры


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

{-# LANGUAGE FlexibleInstances    #-}
{-# LANGUAGE TypeFamilies         #-}
{-# LANGUAGE UndecidableInstances #-}

module MapKey where

import           Data.Map.Strict    (Map)
import qualified Data.Map.Strict    as Map

class MapKey k where
  data MMap k :: * -> *

instance {-# OVERLAPPING #-} MapKey () where
  newtype MMap () v = UnitMap (Maybe v)

instance {-# OVERLAPPABLE #-} Ord k => MapKey k where
  newtype MMap k v = OrdMap (Map k v)

К сожалению, это не работает. GHC (8.2.1) жалуется:

    Conflicting family instance declarations:
      MMap () = UnitMap (Maybe v)
      MMap = OrdMap (Map k v)
   |
14 |   newtype MMap () v = UnitMap (Maybe v)
   |

Есть ли какое-то расширение языка, которое позволяет это? В противном случае есть ли другой способ упростить для пользователей определение экземпляра по умолчанию для Ord?

1 3

1 ответ:

Одно решение, которое освобождает перекрывающиеся экземпляры, заключается в использовании ассоциированного по умолчанию семейства инъективных типов (довольно много). Я также прикрепил некоторые методы с реализациями по умолчанию для синонима default MMap:

{-# LANGUAGE DefaultSignatures      #-}
{-# LANGUAGE TypeFamilies           #-}
{-# LANGUAGE TypeFamilyDependencies #-}

module MapKey where

import           Data.Map.Strict    (Map)
import qualified Data.Map.Strict    as Map

class MapKey k where
  type MMap k v = r | r -> k v
  type MMap k v = Map k v
  empty :: MMap k v
  default empty :: (MMap k v ~ Map k v) => MMap k v
  empty = Map.empty
  insert :: k -> v -> MMap k v -> MMap k v
  default insert :: (MMap k v ~ Map k v, Ord k) => k -> v -> MMap k v -> MMap k v
  insert = Map.insert
  lookupLE :: k -> MMap k v -> [(k, v)]
  default lookupLE :: (MMap k v ~ Map k v, Ord k) => k -> MMap k v -> [(k, v)]
  lookupLE k m =
    case Map.lookupLE k m of
      Nothing -> []
      Just e -> [e]

instance MapKey () where
  type MMap () v = Maybe v
  empty = Nothing
  insert _ v _ = Just v
  lookupLE _ m =
    case m of
      Nothing  -> []
      (Just v) -> [((), v)]

Это означает, что клиентский код все еще должен определять шаблонные сиротские экземпляры, такие как

instance MapKey Int

Я предпочел бы видеть решение, которое использует перекрывающиеся экземпляры вместо этого.