Familles de données associées et instances chevauchantes

Je voudrais une structure de données de carte «générique» qui peut être efficacement spécialisée en fournissant des instances personnalisées, un peu comme dans the GHC manual section on type families.Familles de données associées et instances chevauchantes

{-# 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)

Malheureusement, cela ne fonctionne pas. GHC (8.2.1) se plaint:

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

Y a-t-il une extension de langage qui le permet? Sinon, existe-t-il un autre moyen de permettre aux utilisateurs de définir une instance par défaut pour Ord?

Source

2017-09-13 Sebastian Graf

Les familles de données ne doivent pas chevaucher. Le type de sécurité ne tient plus autrement ... Idée intéressante cependant. – Alec

Pourquoi? Existe-t-il des situations dans lesquelles les chevauchements avec les types associés sont dangereux lorsque les méthodes de chevauchement sont toujours sans danger? I.o.w. Quand les familles de types qui se chevauchent sont-elles plus dangereuses que les classes de types qui se chevauchent? –

Les familles _type_ associées qui se chevauchent sont correctes, mais pas les familles _data_. Le polymorphisme se décompose avec des familles de données qui se chevauchent. [Voici un croquis.] (Https://gist.github.com/harpocrates/8e9c5d693f312e39fff4c7ae1df09f41) – Alec

Une solution qui abandonne les instances qui se chevauchent consiste à utiliser une famille de types injective associée par défaut (tout à fait une bouchée). J'ai aussi attaché certaines méthodes avec des implémentations par défaut pour la valeur par défaut MMap synonyme:

{-# 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)]

Cela signifie que le code client doit encore définir les instances orphelines boilerplate comme

instance MapKey Int

Je préfère voir une solution qui utilise chevauchement d'instances à la place.

Source

2017-09-13 20:22:04

Familles de données associées et instances chevauchantes

Répondre

Questions connexes