Haskell изменчивая карта/дерево

Ответ 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]

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

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]

Ответ 2

Основываясь на ответе @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 общим для функций, которые используют карты таким образом.

Ответ 3

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

Что касается используемой структуры данных,

• Существует реализация красно-черных деревьев в Kent

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

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

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

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

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

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

Ответ 4

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

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

Ответ 5

Если я правильно прочитал ваши комментарии, у вас будет структура с возможными значениями ~ 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