2009-06-19 20 views
7

deseo de definir la siguiente clase de tipos Mapping:Haskell: clases tipo de pregunta

{-# LANGUAGE MultiParamTypeClasses #-} 

class Mapping k v m where 
    empty :: m v 
    insert :: k -> v -> m v -> m v 
    search :: k -> m v -> Maybe v 
    delete :: k -> m v -> m v 

Un ejemplo de Mapping es Data.Map.Map

{-# LANGUAGE ..., FlexibleInstances #-} 

instance Ord k => Mapping k v (Map.Map k) where 
    empty = Map.empty 
    search = Map.lookup 
    insert = Map.insert 
    delete = Map.delete 

Y ahora quiero crear un tipo de Trie :: * -> * -> * -> * como

{-# LANGUAGE ..., UndecidableInstances #-} 

data Trie m k v = Trie { 
    trValue :: Maybe v, 
    trChildren :: m (Trie m k v) 
} 

instance Mapping k (Trie m k v) m => Mapping [k] v (Trie m k) where 
    search [] tree = trValue tree 
    search (x:xs) tree = 
    search xs =<< search x (trChildren tree) 

Hasta ahora todo bien, ahora también quiero definir Trie 's insert y empty, y ahí es donde me meto en problemas.

voy a discutir empty porque es más simple y insert necesita de todos modos .. Si intento esto:

instance Mapping k (Trie m k v) m => Mapping [k] v (Trie m k) where 
    empty = Trie { trValue = Nothing, trChildren = empty } 
    ... 

y eso me sale el siguiente error:

Could not deduce (Mapping k (Trie m k1 v) (m k1)) 
    from the context (Mapping [k1] v (Trie m k1), 
        Mapping k1 (Trie m k1 v) (m k1)) 
    arising from a use of `empty' at test.hs:27:49-53 
Possible fix: 
    add (Mapping k (Trie m k1 v) (m k1)) to the context of 
    the instance declaration 
    or add an instance declaration for (Mapping k (Trie m k1 v) (m k1)) 
In the `trChildren' field of a record 
In the expression: Trie {trValue = Nothing, trChildren = empty} 
In the definition of `empty': 
    empty = Trie {trValue = Nothing, trChildren = empty} 

tengo intenté y traté de resolverlo pero fallé.

¿Alguien sabe cómo hacerlo funcionar? ¿Es posible?

+3

BTW, sugiero eliminar el 'v' de la definición de clase de tipo (pero déjelo en las firmas de los métodos). No lo necesita, al menos para todas las estructuras que ha dado hasta ahora, ya que todas tomarán cualquier tipo de contenido, y todo se simplifica. –

Respuesta

14

añadir un functional dependency:

{-# LANGUAGE ..., FunctionalDependencies #-} 

class Mapping k v m | m -> k where 
    ... 

Los errores que recibió antes de que se debido a que el programa era ambigua sobre qué tipo de clave a utilizar en ciertos lugares, por lo tanto los errores sobre el tipo de variable k1. La dependencia funcional permite que el tipo de clave se deduzca del tipo de mapa (declarando que solo hay una respuesta posible), que trata este problema.

+0

¡Gracias! Lo codifiqué (ver a continuación) y salió bastante claro gracias a su sugerencia de eliminar v de la definición de clase de tipo. – yairchu

7

Código para demostrar la respuesta de Ganesh:

{-# LANGUAGE FlexibleInstances, FunctionalDependencies, MultiParamTypeClasses, StandaloneDeriving, UndecidableInstances #-} 

import qualified Data.Map as Map 
import Data.Maybe (fromMaybe) 

class Mapping k m | m -> k where    
    empty :: m v 
    insert :: k -> v -> m v -> m v 
    search :: k -> m v -> Maybe v 
    delete :: k -> m v -> m v 

instance Ord k => Mapping k (Map.Map k) where 
    empty = Map.empty 
    search = Map.lookup 
    insert = Map.insert 
    delete = Map.delete 

data Trie m v = Trie { 
    trValue :: Maybe v, 
    trChildren :: m (Trie m v) 
} 

deriving instance (Show v, Show (m (Trie m v))) => Show (Trie m v) 

trieMod :: Mapping k m => Maybe v -> [k] -> Trie m v -> Trie m v 
trieMod val [] trie = trie { trValue = val } 
trieMod val (x:xs) trie = 
    trie { trChildren = insert x newChild children } 
    where 
    children = trChildren trie 
    newChild = trieMod val xs prevChild 
    prevChild = fromMaybe empty . search x $ children 

instance Mapping k m => Mapping [k] (Trie m) where 
    empty = Trie { trValue = Nothing, trChildren = empty } 
    search [] trie = trValue trie 
    search (x:xs) trie = 
    search xs =<< search x (trChildren trie) 
    insert key val = trieMod (Just val) key 
    delete = trieMod Nothing 

type TernarySearchTree a = Trie (Map.Map a) 

Por cierto: ¿Había dependencias funcionales no existía, probablemente tenga que ceder en una interfaz molesto y utilizar tablas de funciones en lugar de clases de tipos.

+0

@Titou: En cuanto a su edición, consulte la discusión anterior con @GaneshSittampalam sobre cómo eliminar 'v' de la definición de clase de tipo. http://stackoverflow.com/questions/1019928/haskell-type-classes-question/1020264#comment829685_1019928 http://stackoverflow.com/questions/1019928/haskell-type-classes-question/1020264#comment829844_1020134 – yairchu

+0

sorry - corrected . – Titou

+0

Gracias por tomarse el tiempo para señalar el error, porque era una creencia falsa que no habría cuestionado sin su mensaje. – Titou

Cuestiones relacionadas