Haskell: тип классов вопрос
Вопрос
Я хочу определить следующий класс типов 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}
Я пытался решить эту проблему, но не смог.
Кто-нибудь знает, как заставить это работать? Это вообще возможно?
Решение
Добавьте функциональную зависимость :
{-# LANGUAGE ..., FunctionalDependencies #-}
class Mapping k v m | m -> k where
...
Ошибки, которые вы получили раньше, были вызваны тем, что программа неоднозначно указала, какой тип ключа использовать в определенных местах, а следовательно, и ошибки в переменной типа k1
. Функциональная зависимость позволяет определить тип ключа из типа карты (объявив, что существует только один возможный ответ), что решает эту проблему.
Другие советы
Код для демонстрации ответа Ганеша:
{-# 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)
Кстати: если бы функциональных зависимостей не существовало, нам, вероятно, пришлось бы пойти на компромисс с раздражающим интерфейсом и использовать таблицы функций вместо классов типов.