Haskell mutable map/tree

Question

Я искал измененную (сбалансированную) таблицу деревьев/карт/хэшей в Haskell или способ имитировать ее внутри функции. То есть когда я вызываю одну и ту же функцию несколько раз, структура сохраняется. Пока я пробовал Data.HashTable (это нормально, но несколько медленнее) и попробовал Data.Array.Judy, но мне не удалось заставить его работать с GHC 6.10.4. Есть ли другие варианты?

Answer 1

Если вы хотите изменяемое состояние, вы можете иметь его. Просто продолжайте передавать обновленную карту или держите ее в государственной монаде (которая оказывается той же самой).

import qualified Data.Map as Map 
import Control.Monad.ST 
import Data.STRef 
memoize :: Ord k => (k -> ST s a) -> ST s (k -> ST s a) 
memoize f = do 
    mc <- newSTRef Map.empty 
    return $ \k -> do 
     c <- readSTRef mc 
     case Map.lookup k c of 
      Just a -> return a 
      Nothing -> do a <- f k 
          writeSTRef mc (Map.insert k a c) >> return a 

Вы можете использовать это так. (На практике, вы можете захотеть добавить способ очистить элементы из кэша тоже.)

import Control.Monad 
main :: IO() 
main = do 
    fib <- stToIO $ fixST $ \fib -> memoize $ \n -> 
     if n < 2 then return n else liftM2 (+) (fib (n-1)) (fib (n-2)) 
    mapM_ (print <=< stToIO . fib) [1..10000] 

На свой страх и риск, вы можете ненадежно побег из требования резьб состояния через все, что нуждается в этом.

import System.IO.Unsafe 
unsafeMemoize :: Ord k => (k -> a) -> k -> a 
unsafeMemoize f = unsafePerformIO $ do 
    f' <- stToIO $ memoize $ return . f 
    return $ unsafePerformIO . stToIO . f' 

fib :: Integer -> Integer 
fib = unsafeMemoize $ \n -> if n < 2 then n else fib (n-1) + fib (n-2) 

main :: IO() 
main = mapM_ (print . fib) [1..1000] 

Answer 2

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

, в отношении которых структура данных для использования,

• Существует implementation of red-black trees в Кенте

• Если у вас есть целые ключи, Data.IntMap является чрезвычайно эффективным.

• Если у вас есть строковые ключи, то bytestring-trie package from Hackage выглядит очень хорошо.

Проблема заключается в том, что я не могу использовать (или не знаю как) использовать не изменяемый тип.

Если вам повезет, вы можете передать структуру данных таблицы в качестве дополнительного параметра для каждой функции, которая в ней нуждается. Если, однако, ваша таблица должна быть широко распространена, вы можете использовать state monad, где состояние - это содержимое вашей таблицы.

Если вы пытаетесь memoize, вы можете попробовать некоторые ленивые трюки memoization из блога Conal Elliott, но как только вы выйдете за пределы целочисленных аргументов, ленивая memoization становится очень мутной — не то, что я бы рекомендовал вам попробовать как начинающий. Может быть, вы можете задать вопрос о более широкой проблеме, которую вы пытаетесь решить? Часто с Haskell и изменчивостью проблема заключается в том, как содержать мутацию или обновления в какой-то области.

Непросто научиться программировать без каких-либо глобальных изменяемых переменных.

Answer 3

Основываясь на ответе @ Ramsey, я также предлагаю вам восстановить свою функцию, чтобы взять карту и вернуть измененную. Затем код с использованием хорошего ol 'Data.Map, который довольно эффективен при модификациях. Вот картина:

import qualified Data.Map as Map 

-- | takes input and a map, and returns a result and a modified map 
myFunc :: a -> Map.Map k v -> (r, Map.Map k v) 
myFunc a m = … -- put your function here 

-- | run myFunc over a list of inputs, gathering the outputs 
mapFuncWithMap :: [a] -> Map.Map k v -> ([r], Map.Map k v) 
mapFuncWithMap as m0 = foldr step ([], m0) as 
    where step a (rs, m) = let (r, m') = myFunc a m in (r:rs, m') 
    -- this starts with an initial map, uses successive versions of the map 
    -- on each iteration, and returns a tuple of the results, and the final map 

-- | run myFunc over a list of inputs, gathering the outputs 
mapFunc :: [a] -> [r] 
mapFunc as = fst $ mapFuncWithMap as Map.empty 
    -- same as above, but starts with an empty map, and ignores the final map 

Легко абстрагировать этот шаблон и сделать mapFuncWithMap родовым над функциями, которые используют карты таким образом.

Answer 4

Если я правильно прочитал ваши комментарии, у вас есть структура с возможными значениями ~ 500 тыс. Для вычисления. Вычисления дорогостоящие, поэтому вы хотите, чтобы они выполнялись только один раз, а при последующем доступе вы просто хотите получить значение без пересчета.

В этом случае используйте ленту Haskell в ваших интересах! ~ 500k не так велик: просто создайте карту всех ответов, а затем при необходимости извлеките. Первая выборка заставит вычисление, последующие выборки одного и того же ответа будут повторно использовать один и тот же результат, и если вы никогда не получите конкретное вычисление - это никогда не произойдет!

Вы можете найти небольшую реализацию этой идеи с использованием трехмерных точечных расстояний в качестве вычисления в файле PointCloud.hs.Этот файл используется Debug.Trace для входа, когда вычисление фактически будет сделано:

> ghc --make PointCloud.hs 
[1 of 1] Compiling Main    (PointCloud.hs, PointCloud.o) 
Linking PointCloud ... 

> ./PointCloud 
(1,2) 
(<calc (1,2)>) 
Just 1.0 
(1,2) 
Just 1.0 
(1,5) 
(<calc (1,5)>) 
Just 1.0 
(1,2) 
Just 1.0 

Answer 5

Есть ли другие варианты?

Изменчивая ссылка на чисто функциональный словарь, такой как Data.Map.