トップ > Haskell > hashtables: Mutable hash tables in the ST monad　を使う。

hashtables: Mutable hash tables in the ST monad　を使う。

Haskell

Data.HashTableを使おうとすると hashtables パッケージを使えというメッセージがありましたのでインストールしてみました。

hashtables とhashableをインストール。

import Data.Hashable
import qualified Data.HashTable.IO as H

type HashTable k v = H.BasicHashTable k v

foo :: IO (HashTable Int Int)
foo = do
     ht <- H.new
     H.insert ht 1 1
     return ht

readfoo = foo >>= \f -> H.lookup f 1
-- => Just 1

mkHash :: IO (HashTable (Int,String) String)
mkHash = H.fromList [((1,"hello"),"Hello"),
                     ((1,"world"),"World"),
                     ((2,"hello"),"Hoge") ]

showH :: IO [Maybe String]
showH = do
  h  <- mkHash
  a1 <- H.lookup h (1, "hello")
  a2 <- H.lookup h (1, "world")
  a3 <- H.lookup h (2, "hello")
  a4 <- H.lookup h (2, "")
  return [a1,a2,a3,a4]

-- => [Just "Hello",Just "World",Just "Hoge",Nothing]

-- Keyの型を定義
-- 参考 http://hackage.haskell.org/package/hashable-1.2.0.3/docs/Data-Hashable.html
data Key a b = K a b deriving Eq
-- ハッシュ値を求めるためのインスタンスを定義
instance (Hashable a, Hashable b) => Hashable (Key a b) where
  hashWithSalt s (K a b) = s `hashWithSalt` a `hashWithSalt` b

data Dat = Dat Int String deriving Show

hashTable :: IO (HashTable (Key Int String) Dat)
hashTable = H.fromList [((K 1 "hello"),Dat 123 "Hello"),
                        ((K 1 "world"),Dat 456 "World"),
                        ((K 2 "hello"),Dat 789 "Hoge") ]

showHashTable :: IO [Maybe Dat]
showHashTable = do
  h  <- hashTable
  a1 <- H.lookup h (K 1 "hello")
  a2 <- H.lookup h (K 1 "world")
  a3 <- H.lookup h (K 2 "hello")
  a4 <- H.lookup h (K 2 "")
  return [a1,a2,a3,a4]
-- => [Just (Dat 123 "Hello"),Just (Dat 456 "World"),Just (Dat 789 "Hoge"),Nothing]

ハシュキーとなる型がData.Hashableにない場合はインスタンスを定義すればよい。

> :m Data.Hashable
>  data Date = Date Int Int Int
> instance Hashable Date where  hashWithSalt s (Date yr mo dy) =  s `hashWithSalt` yr `hashWithSalt` mo `hashWithSalt` dy
> hash $ Date 2013 11 14 -- > 2111158425

> data Color = Red | Green | Blue deriving Enum
> instance Hashable Color where  hashWithSalt = hashUsing fromEnum
> hash Red   -- > -1684209108
> hash Blue  -- > -1684209106
> hash Green -- > -1684209107