3

それで、私は（速度上の理由から）変更可能なハッシュテーブルを探していました.Don Stewartからの更新された回答により、 hashtablesを試してみました.

STモナドに少し慣れていないので、与えられた例を次のように拡張することに成功しました:

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE FlexibleContexts #-}

import qualified Data.HashTable.ST.Cuckoo as C
import qualified Data.HashTable.Class as H
import Control.Monad.ST.Safe
import Data.Text

type HashTable s k v = C.HashTable s k v

foo :: ST s (HashTable s Text Int)
foo = do
  ht <- H.newSized 1
  H.insert ht "abc" 1
  H.insert ht "dea" 3
  return ht

add1 :: HashTable s Text Int -> ST s (HashTable s Text Int)
add1 ht = do
  H.insert ht "abc" 2
  H.insert ht "dea" 4
  return ht

main = do
  let x = runST $ H.toList =<< foo
  print x
  let y = runST $ H.toList =<< add1 =<< foo
  print y

私の（限られた）理解では、データ構造を変更可能な方法で操作できますが、「それらをフリーズ」して、エスケープできるように結果を提示します。runSTしたがって、letバインディングを使用できます。ありません<-。

しかし、リストとの間で常に変換せずにハッシュテーブルを操作する方法がわかりませんでした。次のコードはコンパイルさえしません。

   -- does not compile
   let z = runST foo
   let w = runST $ add1 z
   print w

次のエラーが発生します (特に): hashtable.hs:31:19:

Couldn't match type `a' with `C.HashTable s Text Int'
  `a' is a rigid type variable bound by
      the inferred type of z :: a at hashtable01.hs:31:7
Expected type: ST s a
  Actual type: ST s (HashTable s Text Int)
In the second argument of `($)', namely `foo'
In the expression: runST $ foo
In an equation for `z': z = runST $ foo

これはおそらくs型の制約によるものであり、おそらくまさにその理由でそこにあると思います。後で使用する場合、その場で操作されるzため、同じ値を持たadd1ないため、純粋ではありません。これは正しいです？

しかし、この特定の場合の ST モナドは、次のような状況でのみ役立ちます。

  • 固定入力を与える
  • 可変データ構造を使用して、それに基づいて新しい値を計算します
  • 結果を凍結して、再び不変にします。

それ以上の変更には、値を効果的にコピーし、元の不変を保持する toList/fromList が必要です。私がこれを書いているとき、私は考えています - 当然、これは純粋な関数の定義であり、haskell のあらゆる場所で使用されているため、ST モナドのユースケースです (私は ST 啓蒙に達しましたか?)

したがって、この場合の本当の問題は、この toList/fromList 操作は高価 (2xO(n)) ではないか、関数の toList/fromList ペアを使用せずにコピーを操作する別の方法がないかということです。 . それとも、複雑すぎて、Hashtables の IO バージョンを使用する必要がありますか?

4

1 に答える 1