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

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

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

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

Относительно того, какую структуру данных использовать,

• В Кенте есть реализация красно-черных деревьев

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

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

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

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

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

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

Answer 4

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

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

Answer 5

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

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

Вы можете найти небольшую реализацию этой идеи, используя 3D точечные расстояния в качестве вычисления в файле 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