相关数据族和重叠实例

我想要一个'通用'地图数据结构，它可以通过提供自定义实例来高效地进行专门化，就像在the GHC manual section on type families中一样。相关数据族和重叠实例

{-# 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定义一个'默认'实例吗？

来源

2017-09-13 Sebastian Graf

数据族_必须不重叠。类型安全不再持有其他...有趣的想法，但。 – Alec

这是为什么？在重叠方法本身仍然安全的情况下，是否存在与相关类型重叠的情况是不安全的？ I.o.w.何时重叠类型族比重叠类型类更“不安全”？ –

重叠相关的_type_家庭很好，只是不_data_家庭。多态性与重叠的数据族有关。 [这里是一个草图。]（https://gist.github.com/harpocrates/8e9c5d693f312e39fff4c7ae1df09f41） – Alec

放弃重叠实例的一个解决方案是使用默认的相关内射类型（相当一口）。我还附加了一些方法与默认实现默认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

我宁愿看到一个解决方案，使用样板孤儿实例重叠的实例。

来源

2017-09-13 20:22:04

相关数据族和重叠实例

回答

相关问题