Haskell изменяемая карта/дерево
Я ищу изменяемое (сбалансированное) дерево/карту/хеш-таблицу в Haskell или пути, как моделировать его в функции. Т.е. когда я несколько раз вызываю ту же функцию, структура сохраняется. До сих пор я попробовал Данные. HashTable (который в порядке, но несколько медленный), и попробованные Данные. Массив. Judy, но я не мог заставить его работать с GHC 6.10.4. Есть ли какие-либо другие опции?
4 ответа
Если вам нужно изменяемое состояние, вы можете его получить. Просто передавайте обновленную карту по кругу или храните ее в монаде состояний (что, как оказалось, одно и то же).
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]
Опираясь на ответ @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 универсальной для функций, использующих карты таким образом.
Хотя вы запрашиваете изменяемый тип, позвольте мне предложить вам использовать неизменяемые данные структура и что вы передаете последовательные версии своим функциям в качестве аргумента.
Относительно того, какую структуру данных использовать,
Существует реализация красно-черных деревьев в Кенте
. Если у вас есть целочисленные ключи,
Data.IntMapчрезвычайно эффективный.Если у вас есть строковые ключи, пакет
bytestring-trieот Hackage выглядит очень хорошо.
Проблема в том, что я не могу (или не знаю, как) использовать неизменяемый тип.
Если вам повезет, вы можете передать структуру данных таблицы в качестве дополнительного параметра каждой функции, которая в ней нуждается. Если, однако, ваша таблица должна быть широко распространена, вы можете использовать монаду состояния , где состояние - это содержимое вашей таблицы.
Если вы пытаетесь запоминать, вы можете попробовать некоторые из уловок ленивого запоминания из блога Конала Эллиотта, но как только вы выйдете за рамки целочисленных аргументов, ленивое запоминание станет очень непонятным - не то, что я бы рекомендовал вам попробовать как новичок . Может быть, вы можете задать вопрос о более широкой проблеме, которую вы пытаетесь решить? Часто с Haskell и изменчивостью проблема заключается в том, как удержать мутацию или обновления в какой-то области.
Не так-то просто научиться программировать без каких-либо глобальных изменяемых переменных.
Если я правильно прочитал ваши комментарии, то у вас есть структура с возможно ~ 500k общими значениями для вычислить. Вычисления дороги, поэтому вы хотите, чтобы они выполнялись только один раз, а при последующих доступах вам просто нужно значение без пересчета.
В этом случае используйте лень 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