Изменяемая карта / дерево 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

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

В этом случае используйте лень Хаскелла в ваших интересах! ~ 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