19

Haskell で変更可能な (バランスのとれた) ツリー/マップ/ハッシュ テーブル、または関数内でそれをシミュレートする方法を探しています。つまり、同じ関数を数回呼び出すと、構造が保持されます。これまでのところ、Data.HashTable (これは問題ありませんが、やや遅い) を試し、Data.Array.Judy を試しましたが、GHC 6.10.4 で動作させることができませんでした。他のオプションはありますか？

4

5 に答える 5

13

可変状態が必要な場合は、それを使用できます。更新されたマップを渡し続けるか、状態モナドに保持するだけです (結果的には同じことがわかります)。

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]
于 2010-02-10T17:00:02.017 に答える
8

@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をこのようにマップを使用する関数に対して汎用的にするのは簡単です。

于 2010-02-10T00:25:50.830 に答える
5

変更可能な型を求めていますが、不変のデータ構造を使用し、連続するバージョンを引数として関数に渡すことをお勧めします。

どのデータ構造を使用するかについては、

問題は、非可変型を使用できない (または使用方法がわからない) ことです。

運が良ければ、テーブルのデータ構造を必要なすべての関数に追加パラメーターとして渡すことができます。ただし、テーブルを広く分散させる必要がある場合は、状態がテーブルの内容である状態モナドを使用することをお勧めします。

メモ化しようとしている場合は、Conal Elliott のブログからいくつかの遅延メモ化のトリックを試すことができますが、整数引数を超えるとすぐに、遅延メモ化は非常に曖昧になります。解決しようとしているより広い問題について質問を投稿できますか? 多くの場合、Haskell と可変性の問題は、何らかの範囲内に変異または更新を含める方法です。

グローバルな可変変数なしでプログラミングを学ぶのはそれほど簡単ではありません。

于 2010-02-09T23:57:01.147 に答える
0

他のオプションはありますか？

のような純粋に機能的な辞書への変更可能な参照Data.Map。

于 2012-06-06T12:30:17.150 に答える
0

あなたのコメントを正しく読めば、計算する合計値が最大 500k の構造を持っていることになります。計算はコストがかかるため、1 回だけ実行し、その後のアクセスでは再計算せずに値だけを取得します。

この場合、Haskell の怠惰さを利用してください。~500k はそれほど大きくありません。すべての回答のマップを作成し、必要に応じてフェッチするだけです。最初のフェッチは計算を強制し、同じ答えの後続のフェッチは同じ結果を再利用します。特定の計算をフェッチしないと、決して起こりません!

ファイルPointCloud.hsの計算として 3D ポイント距離を使用して、このアイデアの小さな実装を見つけることができます。そのファイルは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
于 2010-02-10T05:54:14.187 に答える