Hatena::Grouphaskell

[ pred x | x <- "Ibtlfmm!ojllj" ] RSSフィード

2008-04-14

簡易ベンチマーク 00:26

> :m System.CPUTime
> let time m = do start <- getCPUTime; m; end <- getCPUTime; return $ end - start
> time $ do print 1
1
0
> :m +Control.Exception
> time $ evaluate $ show 100
0
> time $ evaluate $ length [1..1000000]
31250000000
> :m +Control.Monad
> time $ replicateM_ 100000 $ evaluate $ show 1000000000000
15625000000
> let timeSec = fmap (/ 10**12) . fmap fromIntegral . time
> time $ replicateM_ 100000 $ evaluate $ show 1000000000000
1.5625e-2

シンボルっぽいものを考える 00:56

Haskellはデータ構造が一通り豊富だが、不思議とシンボルがない。

自分のいうシンボルというのは、Schemeの'fooやRubyの:barのことで、以下のようなものだ。

  1. 比較が早い
  2. 手軽に生成できる
  3. 文字列から生成できる
  4. 文字列に変換できる
  5. 書き換えられない

このうち5はHaskellのデータ型ならほぼ大丈夫だ。

Data.Unique (1) (5)

Data.Uniqueに一見それらしい型があった。

data Unique
instance Eq Unique
instance Ord Unique
newUnique :: IO Unique
hashUnique :: Unique -> Int

問題は生成にIOがつくことと、文字列と相互変換ができないこと。

単純に文字列との組を作れば(4)を満たすが、IOのためにReadのインスタンスにもできない。

列挙型 (1?) (2) (3) (4) (5)

単純に考えるとこういう列挙子的なデータ型を作ればいい。

data Symbol = Foo | Bar | Baz deriving (Show, Read, Eq)

シンボルを受け取る関数は大体どんなシンボルを渡すべきか決まっているので、関数ごとにこういう型を作れば、型チェックがされてバグも少なくなる。

たいていはこの方法で用が済むのだが、異なる列挙子型どうしでは比較できない。(この方が便利な場合も多いが)

ハッシュ (1) (3) (5)

Data.HashTableにhashStringという関数がある。

hashString :: String -> Int32

もちろんハッシュテーブルに使うためなのだが、Int32をシンボルと見ると、これが文字列からシンボルを作る関数といえる。速度は計っていない。

(4)をするには辞書を自前で持つ必要がある。そのためShowのインスタンスにはできない。

辞書を作る場合、すぐそこにHashTableがあるが、操作にIOが付いているので元も子もない。Data.IntMapからIntMap Stringを作るのもいいかもしれない。

キャッシュすることを諦めれば、Uniqueと同様に文字列との組を作る選択肢がある。これが最もポータブルだろう。

また、IsStringクラスインスタンスにしておくと"hoge" :: Symbolのようなことができるので便利。

{-# OPTIONS -XOverloadedStrings #-}
module Symbol where

import Data.HashTable (hashString)
import Data.String
import Data.Int

data Symbol = Symbol { symbolName :: String, symbolID :: Int32 }

instance Eq Symbol where
  x == y = symbolID x == symbolID y

instance Show Symbol where
  show = symbolName

instance Read Symbol where
  readsPrec _ = map make . lex
    where
    make (word, rest) = (fromString word, rest)

instance IsString Symbol where
  fromString str = Symbol str (hashString str)

簡単なReadのインスタンス 01:42

忘れると思うので、上の記事から抜き出しておく。

Preludeのlexという関数はすごく便利。

instance Read Symbol where
  readsPrec _ = map make . lex
    where
    make (word, rest) = (fromString word, rest)

instance IsString Symbol where
  fromString str = Symbol str (hashString str)

ラップした。simply $ read "Foo" :: Fooのように使う。(Haskellに区切り方を任せているので、期待通りになるかはわからない)

module SimplyRead where

import Data.String

newtype R a = R { simply :: a }

instance (IsString a) => Read (R a) where
  readsPrec _ = map make . lex
    where
    make (word, rest) = (R $ fromString word, rest)

tt2008/04/22 10:50うちの環境だと :set +s で表示される時間と変わらないです > 簡易ベンチマーク

illillliillillli2009/05/14 20:50ほんとだ。GHCi本体についてるんですね。

トラックバック - http://haskell.g.hatena.ne.jp/illillli/20080414