Уберите необходимость в Data.Map в Haskell

Question

Хорошо, я пытаюсь изучить haskell. Несколько раз я публиковал вопросы, которые были проголосованы, потому что я не могу объяснить, чего я пытаюсь достичь, но я снова попытаюсь задать новый вопрос.

Я нахожу фрагмент кода, который я хочу немного изменить. Вот оно:

import qualified Data.Map as M 

type Dict = M.Map String String 

translate :: Dict -> [String] -> [String] 
translate dict words = map trans words 
    where 
    trans :: String -> String 
    trans w = 
     case M.lookup w dict of 
     (Just w') -> w' 
     Nothing -> "whatchamacallit" 

testTranslation :: Dict -> IO() 
testTranslation dict = do 
    print $ translate dict ["where", "is", "the", "colosseum"] 

testInsertion :: Dict -> IO Dict 
testInsertion dict = do 
    return $ M.insert "colosseum" "colosseo" dict 

main = 
    let dict = M.fromList [("where", "dove"), ("is", "e"), ("the", "il")] 
    in do 
      testTranslation dict 
      dict' <- testInsertion dict 
      testTranslation dict' 
      putStrLn "The original dictionary is unchanged:" 
      testTranslation dict 

Короче говоря: Он заменит elems где с нырнул, является с е и т.д., но он использует данных . Карта.

Так что мой вопрос - Есть ли способ сделать то же самое без использования Data.Map

Answer 1

Вы можете использовать списки в качестве словарей. Конечно, это не будет практично для больших словарей, потому что поиск - O (N).

Вот тип подписи поиска списка:

lookup :: Eq α => α -> [(α, β)] -> Maybe β 

Это говорит следующее:

Учитывая некоторый элемент типа А и список кортежей (а, б), то функция вернет Nothing или Just someb, где someb имеет тип b.

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

Следовательно:

lookup 42 [(1, "one"), (42, "it"), (2, "bar")] 

должно быть

Just "it" 

тогда

lookup 77 [(1, "one"), (42, "it"), (2, "bar")] 

должно быть

Nothing 

Вы можете попробовать его в GHCi, и это должно быть слишком сложно, чтобы избавиться от Data.Map в вашей программе. Насколько я вижу, это всего лишь 3 небольших изменения (не считая отбрасывания импорта).