Haskell: тип классов вопрос - PullRequest
Новая
       9

Haskell: тип классов вопрос

7 голосов
/ 20 июня 2009

Я хочу определить следующий класс типов Mapping: 

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

Один экземпляр Mapping равен 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

А теперь я хочу создать тип Trie :: * -> * -> * -> *, такой как 

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

Пока все хорошо, теперь я также хочу определить Trie insert и empty, и вот тут у меня возникают проблемы.

Я буду обсуждать empty, потому что это проще и insert все равно это нужно .. Если я попробую это: 

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

и я получаю следующую ошибку: 

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}

Я пытался решить эту проблему, но не смог.

Кто-нибудь знает, как заставить это работать? Это вообще возможно?

Ответы [ 2 ]

14 голосов
/ 20 июня 2009

Добавить функциональную зависимость : 

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

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

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

7 голосов
/ 20 июня 2009

Код для демонстрации ответа Ганеша: 

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

Кстати: если бы функциональных зависимостей не существовало, нам, вероятно, пришлось бы пойти на компромисс с раздражающим интерфейсом и использовать таблицы функций вместо классов типов.

...