Haskell: Как использовать HashMap в главной функции

Question

Я прошу вашей помощи, форсирование следующую программу: (!)

main = do 
    jobsToProcess <- fmap read getLine 
    forM_ [1..jobsToProcess] $ \_ -> do 
    [r, k] <- fmap (map read . words) getLine :: IO [Int] 
    putStrLn $ doSomeReallyLongWorkingJob r k 

Там может быть много одинаковых рабочих мест, чтобы сделать, но это не так до меня, изменяя входные данные, поэтому я попытался использовать Data.HashMap для резервного копирования уже обработанных заданий. Я уже оптимизировал алгоритмы в функции doSomeReallyLongWorkingJob, но теперь кажется, что это довольно быстро, как C.

Но, к сожалению, похоже, что я не могу реализовать простой кеш, не создавая много ошибок. Мне нужен простой кеш типа HashMap (Int, Int) Int, но каждый раз у меня слишком много или слишком мало скобок. И если мне удастся определить кеш, я застрял в деле ввода данных или извлечения данных из кеша из-за большого количества ошибок.

Я уже несколько часов смотрел в Google, но, похоже, я застрял. BTW: Результат longrunner также является Int.

Answer 1

Это довольно просто сделать действие с состоянием, которое кэширует операции. Во-первых некоторые шаблонные:

{-# LANGUAGE FlexibleContexts #-} 
import Control.Monad.State 
import Data.Map (Map) 
import qualified Data.Map as M 
import Debug.Trace 

Я буду использовать Data.Map, но, конечно, вы можете заменить в хэш-карте или любой другой аналогичной структуры данных без особых проблем. Мое длительное вычисление просто добавит свои аргументы. Я буду использовать trace, чтобы показать, когда это вычисление выполнено; мы будем надеяться не видеть вывод trace при вводе двойного ввода.

reallyLongRunningComputation :: [Int] -> Int 
reallyLongRunningComputation args = traceShow args $ sum args 

Теперь операция кэширования будет просто искать, видели ли мы данный вход раньше. Если у нас есть, мы вернем предварительно вычисленный ответ; иначе мы вычислим ответ и сохраним его.

cache :: (MonadState (Map a b) m, Ord a) => (a -> b) -> a -> m b 
cache f x = do 
    mCached <- gets (M.lookup x) 
    case mCached of 
     -- depending on your goals, you may wish to force `result` here 
     Nothing -> modify (M.insert x result) >> return result 
     Just cached -> return cached 
    where 
    result = f x 

main функция теперь просто состоит из вызова cache reallyLongRunningComputation на соответствующих входах.

main = do 
    iterations <- readLn 
    flip evalStateT M.empty . replicateM_ iterations 
     $ liftIO getLine 
     >>= liftIO . mapM readIO . words 
     >>= cache reallyLongRunningComputation 
     >>= liftIO . print 

Давайте попробуем его в ghci!

> main 
5 
1 2 3 
[1,2,3] 
6 
4 5 
[4,5] 
9 
1 2 
[1,2] 
3 
1 2 
3 
1 2 3 
6 

Как вы можете видеть в квадратные скобки выходов, reallyLongRunningComputation был назван первый раз, когда мы вошли 1 2 3 и первый раз, когда мы вошли 1 2, но не второй раз, когда мы вышли на эти входы.

Answer 2

Надеюсь, я не слишком далек от базы, но сначала вам нужен способ носить с собой прошлые задания. Проще всего было бы использовать foldM вместо forM.

import Control.Monad 
import Data.Maybe 

main = do 
    jobsToProcess <- fmap read getLine 
    foldM doJobAcc acc0 [1..jobsToProcess] 
    where 
    acc0 = --initial value of some type of accumulator, i.e. hash map 
    doJobAcc acc _ = do 
     [r, k] <- fmap (map read . words) getLine :: IO [Int] 
     case getFromHash acc (r,k) of 
     Nothing -> do 
      i <- doSomeReallyLongWorkingJob r k 
      return $ insertNew acc (r,k) i 
     Just i -> do 
      return acc 

Обратите внимание: на самом деле я не использую интерфейс для ввода и получения ключа хеш-таблицы. Фактически это не должно быть хеш-таблицей, Data.Map из контейнеров может работать. Или даже список, если он будет небольшим.

Другим способом переноса вокруг хэш-таблицы будет использование монады-трансформатора состояния.

Answer 3

Я просто добавляю этот ответ, так как я чувствую, что другие ответы немного расходятся с исходным вопросом, а именно с использованием конструкций hashtable в главной функции (внутри IO monad).

Вот минимальный пример хеш-таблицы с использованием модуля hashtables. Чтобы установить модуль с интригой, просто используйте

междусобойчик установить HashTables

В этом примере, мы просто поставить некоторые значения в хэш-таблицу и использовать поиск, чтобы напечатать значение, полученное из таблицы.

import qualified Data.HashTable.IO as H 

main :: IO() 
main = do 
     t <- H.new :: IO (H.CuckooHashTable Int String) 
     H.insert t 22 "Hello world" 
     H.insert t 5 "No problem" 
     msg <- H.lookup t 5 
     print msg 

Обратите внимание, что нам нужно использовать явные аннотации типов, чтобы указать, какую реализацию хеш-таблицы мы хотим использовать.