Haskell — ошибки типа с IntMap и типом данных

Мы реализуем Tries в Haskell с помощью IntMaps. Однако я не могу понять IntMaps.

Вот что у меня есть:

charMapLookup :: Char -> IntMap a -> Maybe a
charMapLookup c dict = IntMap.lookup (ord c) dict

charMapInsert :: Char -> a -> IntMap a -> IntMap a
charMapInsert c v dict = IntMap.insert (ord c) v dict

-- Question 1.
data Trie a = TrieOf (Maybe a) (IntMap (Trie a))
    deriving Show

trieLookup :: [Char] -> Trie a -> Maybe a
-- My code
trieLookup [] (TrieOf a t) = a
trieLookup (x:xs) (TrieOf _ t) = trieLookup xs (charMapLookup x t)

trieInsert :: [Char] -> a -> Trie a -> Trie a
trieInsert [] a (TrieOf c t)= TrieOf c t
trieInsert (x:xs) a (TrieOf c t) | isNothing (charMapLookup x t) = trieInsert xs a (charMapInsert x Nothing t)
                                 | trieInsert xs a (charMapLookup x t)

Мне кажется, это имеет смысл, поскольку, если в строке ничего не осталось, вы возвращаете значение узла, иначе ищите конец строки в соответствующем поддереве и аналогично для вставки. Однако, когда я пытаюсь запустить его :

 Couldn't match expected type ‘Trie a’
                    with actual type ‘Maybe (Trie a)’
        Relevant bindings include
          t :: IntMap (Trie a)
          trieLookup :: [Char] -> Trie a -> Maybe a 
        In the second argument of ‘trieLookup’, namely
          ‘(charMapLookup x t)’
        In the expression: trieLookup xs (charMapLookup x t)
    Failed, modules loaded: none.   

Couldn't match expected type ‘Trie a’
                with actual type ‘IntMap (Maybe a0)’
    Relevant bindings include
      t :: IntMap (Trie a) 
      c :: Maybe a 
      a :: a 
      trieInsert :: [Char] -> a -> Trie a -> Trie a
    In the third argument of ‘trieInsert’, namely
      ‘(charMapInsert x Nothing t)’
    In the expression: trieInsert xs a (charMapInsert x Nothing t)

Couldn't match type ‘Trie a’ with ‘Maybe a0’
    Expected type: IntMap (Maybe a0)
      Actual type: IntMap (Trie a)
    Relevant bindings include
      t :: IntMap (Trie a) 
      c :: Maybe a 
      a :: a
      trieInsert :: [Char] -> a -> Trie a -> Trie a
    In the third argument of ‘charMapInsert’, namely ‘t’
    In the third argument of ‘trieInsert’, namely
      ‘(charMapInsert x Nothing t)’

Я не уверен, как исправить ошибку, я знаю, что это говорит о несоответствии типов, но t должен быть IntMap of Tries (правильно?), поэтому я не знаю, как еще подойти к этому. Я потратил смущающе много времени, пытаясь понять это, любой код, который мог бы решить проблему, был бы очень признателен. Спасибо!


custom-data-type trie haskell
person Quentin Hughes    schedule 13.02.2018    source источник
comment
Почти идентичный вопрос был опубликован вчера, а затем удален. Пожалуйста, воздержитесь от этого — это не лучший способ привлечь внимание.   -  person duplode    schedule 13.02.2018
comment
charMapLookup возвращает Maybe, но вы передаете его как второй аргумент trieLookup, который объявлен как Trie. Maybe /= Trie, поэтому несоответствие типов. То же самое с двумя другими ошибками.   -  person Fyodor Soikin    schedule 13.02.2018
comment
@FyodorSoikin Я это понимаю, но не знаю, как обойти это. Я попытался добавить проверку на Ничего, но в противном случае, как бы я получил Trie?   -  person Quentin Hughes    schedule 13.02.2018
comment
Пожалуйста, не портите свои посты.   -  person Glorfindel    schedule 13.02.2018
comment
Добро пожаловать в Stack Overflow! Пожалуйста, не портите свои посты. Размещая в сети Stack Exchange, вы предоставляете SE безотзывное право на распространение этого контента (в соответствии с лицензия CC BY-SA 3.0). Согласно политике SE, любой вандализм будет пресекаться.   -  person Suraj Rao    schedule 13.02.2018

Ответы (1)


arrow_upward
2
arrow_downward

Рассмотрим первое сообщение об ошибке. Это происходит в trieLookup, когда вы берете ветку, соответствующую первому символу, и продолжаете искать остальную часть ключа. Проблема в том, что эта ветвь не Trie a, а Maybe (Trie a) (первый символ может быть не отображен в корне). Чтобы продолжить поиск, вам нужно выполнить плоскую карту в этой, возможно, ненайденной ветке:

trieLookup (x:xs) (TrieOf _ t) = (charMapLookup x t) >>= trieLookup xs

(или используйте case вместо >>=, это обработает как Nothing, так и Just branch возможные результаты charMapLookup).

Обратите внимание, что ваш код содержит больше ошибок, помимо несоответствий типов, не перечисленных в выводе компилятора:

  1. В trieInsert вы фактически не сохраняете сопоставленное значение:

trieInsert [] a (Trie c t) = Trie c t

Правая сторона этого совпадения - та же исходная тройка, без изменений.

  1. Предложение else в trieInsert на самом деле должно читаться так:
trieInsert (x:xs) a (TrieOf c t) | isNothing (charMapLookup x t) = trieInsert xs a (charMapInsert x Nothing t)
                                 | otherwise = trieInsert xs a (charMapLookup x t)
person bipll    schedule 13.02.2018
comment
trieLookup (c:cs) t = fmap (trieLookup cs) (charMapLookup c t) не работает, так как он говорит мне, что ожидает «IntMap (Trie a0)» с фактическим типом «Trie a». Я попытался заменить строку на trieLookup (c:cs) (TrieOf b t) = fmap (trieLookup cs) (charMapLookup c t), но это дает ту же ошибку, что и раньше. - person Quentin Hughes; 13.02.2018
comment
Конечно, поиск первого символа должен выполняться в поле IntMap в Trie, очень сложно публиковать ответы из приложения Android, извините. - person bipll; 13.02.2018