Parsecで数式のパーサを書いてみた(Applicative Functor版あり)
wvogel00のために、昔書いたParsecを使ったコードを載せてみます。コメントに書いてあるのはコードに直す前のEBNFです。
import Text.ParserCombinators.Parsec run :: Show a => Parser a -> String -> IO () run p input = case (parse p "" input) of Left err -> do putStr "parse error at " print err Right x -> print x --expr = factor ('+' factor | '-' factor)* expr :: Parser Float expr = do l <- factor rs <- many ((do char '+' n <- factor return $ (+) n ) <|> (do char '-' n <- factor return $ flip (-) n )) return $ foldr ($) l rs --factor = term ('*' term | '/' term)* factor :: Parser Float factor = do l <- term rs <- many ((do char '*' n <- term return $ (*) n ) <|> (do char '/' n <- term return $ flip (/) n )) return $ foldr ($) l rs --term = number | '(' expr ')' term :: Parser Float term = do (do n <- many1 digit return $ read n ) <|> (do char '(' n <- expr char ')' return n ) main = do run expr "1+2*3/6-(12*12-8/4)"
これをApplicative Functorを使って書き直したのが以下ののものです。
kazu-yamamotoさんのエントリーを参考にして書きました。ちなみにParserがApplicativeのインスタンスになったのはParsec3以降なので、インポートしているモジュールが上とは違います。(Text.ParserCombinators.Parsec.*がParsec2、Text.Parsec.*がParsec3)
import Control.Applicative hiding ((<|>), many) import Text.Parsec import Text.Parsec.String run :: Show a => Parser a -> String -> IO () run p input = case (parse p "" input) of Left err -> do putStr "parse error at " print err Right x -> print x expr :: Parser Float expr = foldr ($) <$> factor <*> many (add <|> sub) where add = ((+) <$> (char '+' *> factor)) sub = (flip (-) <$> (char '-' *> factor)) factor :: Parser Float factor = foldr ($) <$> term <*> many (mul <|> div) where mul = ((*) <$> (char '*' *> factor)) div = (flip (/) <$> (char '/' *> factor)) term :: Parser Float term = number <|> paren where number = (read <$> many1 digit ) paren = (char '(' *> expr <* char ')') main = do run expr "1+2*3/6-(12*12-8/4)"
たしかにコンパクトで可読性が上がってますね。このコードはテスト用に適当に書いたコードなのでパースしながら評価もしていて、けっこう汚いですが、ちゃんとしたパーサをつくるならASTを構築して返し、評価は別に行うのが良いと思います。
HaskellでBMPファイルを読み込む
Haskellでバイナリファイルを扱うときは、Data.Binaryモジュールを用いるのが定石みたいです。この前pingをHaskellで書いたときはそれを知らず、ICMPヘッダをpeekとかpokeでガリガリ読み書きしてました…
というわけで友達が書こうとしているBMPファイルローダを、ヘッダ部分の読み出しだけ書いてみました。バイナリファイルの読み出しには、Data.Binary.GetにあるGetモナドを使用します。Getモナドは内部で入力のByteStringを持ち回してくれて、使用する側が明示的にByteStringに触らなくても良いようになっているみたいです。
Getモナドを構築したら、後はrunGetでByteStringを読み込ませ、パーサを走らせます。直感的で使いやすくて良いですね!書いててなんとなくParsecを思い出しました。まあData.Binary.Getもある意味パーサなわけですからね。
import qualified Data.ByteString.Lazy as L import Data.Binary import Data.Binary.Get import Data.Word data BitmapFileHeader = BitmapFileHeader { bfType :: Word16, bfSize :: Word32, bfOffBits :: Word32 } deriving (Show, Eq) data BitmapInfoHeader = BitmapInfoHeader { biSize :: Word32, biWidth :: Word32, biHeight :: Word32, biBitCount :: Word16 } deriving (Show, Eq) readBmpFileHeader :: Get BitmapFileHeader readBmpFileHeader = do t <- getWord16le s <- getWord32le getWord32le ob <- getWord32le return BitmapFileHeader {bfType = t, bfSize = s, bfOffBits = ob} readBmpInfoHeader :: Get BitmapInfoHeader readBmpInfoHeader = do s <- getWord32le w <- getWord32le h <- getWord32le getWord16le bc <- getWord16le getBytes 24 return BitmapInfoHeader {biSize = s, biWidth = w, biHeight = h, biBitCount = bc} readBmpHeader :: Get (BitmapFileHeader, BitmapInfoHeader) readBmpHeader = do f <- readBmpFileHeader i <- readBmpInfoHeader return (f, i) main = do contents <- L.readFile "test.bmp" print $ runGet readBmpHeader contents
追記@2011.07.15
このソースコードでは不要な値を読み飛ばすのにgetWord16leなどを使ってますが、skipの方が良いのでは、という意見をもらいました。たしかにそっちの方がわかりやすい…っていうかskipを知らなかった。
LaTeXの相互参照がおかしくなるとき
最近LaTeXで文章を書いていてはまったのでメモ。
LaTeXで次のように図を貼り、
\begin{figure}[htbp] \centering \includegraphics{some_figure.pdf} \caption{図のタイトル} \label{labelOfFigure} \end{figure}
文章中で次のように参照を設定すると、その位置に図表番号が挿入されるはずです。
\ref{labelOfFigure}
ただしなぜか図表番号が章・節の番号となることがあります。その場合は、
\begin{figure}[htbp] \centering \includegraphics{some_figure.pdf} \label{labelOfFigure} \caption{図のタイトル} \end{figure}
というように、labelがcaptionの書かれているからかもしれません。labelはcaptionの直後でないといけないみたいです。
HaskellでSQLiteを使う
HaskellでDBを操作するならHDBCを使うのが定石だとは思うんですが、やりたいことが簡単でかつSQLiteで十分だったので、Database.SQLiteを使ってみました。
使い方
SQL文を発行する
最初にsqlite3本体と、cabalでsqliteパッケージをインストールする必要があります。
使い方は簡単で、openConnectionで接続で開き、execStatementでSQL文を発行して、結果を取得します。execStatementの返値は多相で、Either String [[Row String]] 、Either String [[Row Value]]、Either String [[Row Value]]のいずれかを選べます。
Either String [[Row String]] ならLeftがエラーで、Rightなら列名と値のタプルのリストのリストのリストが返ってきます。詳しく書くと、Row Stringは[(String, String)]と同値で、列名と値のタプルのリストで、1行を表します。そして[Row String]は複数行をあらわします。そして[[Row String]]なんですが、これは"select * from urls;select * from profiles;"みたいな感じで複数のSQL文をまとめて実行したときに、各SQLの結果がリストにまとめられるみたいです。
module Main where import Database.SQLite printResult :: Either String [[Row String]] -> IO () printResult result = case result of Left error -> putStrLn error Right result -> print result main = do h <- openConnection "test.db" result <- execStatement h "select * from urls;" printResult result closeConnection h
また、返値をEither String [[Row Value]]という型にすると、以下のようにValueという代数的データ型が定義されていて、元々のテーブルの各列の型のまま結果を受け取れます。
data Value = Double Double | Int Int64 | Text String | Blob ByteString | Null
パラメータ付きのSQL文を発行する
次にパラメータ付きのSQL文を実行する場合ですが、execParamStatement関数を使います。SQL文中でプレースホルダを:placeholderのように書き、execParamStatementの引数でプレースホルダと値のタプルのリストを与えます。
result <- execParamStatement h "select * from urls where id = :col_id;" [(":col_id", Int 1)]
返値はexecStatementと同様です。また、これらの関数の返値を捨てるバージョンexecStatement_やexecParamStatement_も存在します。他にも行を挿入するにはinsertRowや、テーブルを作成するならdefineTableという関数を使えばよいみたいです。また、コールバック関数を自分で定義することもできます。
参考
LuaBindで静的メソッドをバインドする
LuaBindのドキュメンテーションには、
class_<foo>("foo") .def(constructor<>()) .scope [ class_<inner>("nested"), def("f", &f) ];
のようにバインドすると、fをfooの静的メソッドとしてバインドできるよ、と書いてありますが、実際にLua側からどのように使うのか明記されていません。まず、内部クラスが必要なければ、以下のようにscope定義がけ書けば良いようです。
class_<foo>("foo") .def(constructor<>()) .scope [ def("f", &f) ];
そしてLua側からこの静的メソッドを呼ぶときですが、
foo.f()
とすれば良いようです。普通のインスタンスメソッドの呼び出しは
hoge = foo() hoge:g()
のようにコロンなので、C++が頭にあると、ちょっと混同しますね。
参考
LuaBindをMinGW上でbjamを使わずにビルドする
Windows 7 + MinGW + MSYSという環境で、どうしてもマニュアルに書いてあるbjamを使うデフォルトの方法でuaBindがビルドできなかったので(っていうかbjam自体何かおかしい)、Eclipseでライブラリをビルドしてみました。
スタティックライブラリとして作りましたが、シェアードの場合も(たぶん)同様にできるはず。
- MinGW+MSYS+Eclipse CDT+Luaインストール済みの環境が前提です
- LuaBindの公式サイトからソースコードのアーカイブを落とし、解凍するとINSTALL 、Jamroot 、LICENSE、doc、examples 、luabind 、src、 testというファイルとディレクトリが生成されるはずです。
- luabindの中にはヘッダファイルが入っているので、ディレクトリごと/mingw/includeにコピーします。
- srcの中にライブラリのソースが入っているので、これをEclipseでビルドします。
- EclipseでC++ Project > Static Library > Empty Projectを、luabindという名前で作成します。Debugビルドのチェックは外しておきます。
- このプロジェクトに、D&Dでsrc以下の全てのcppファイルを追加してから、プロジェクトをビルドします。
- ビルドが成功すれば、プロジェクトのディレクトリ/Releaseにlibluablind.aというライブラリファイルが生成されるので、これを/mingw/libにコピーします。
- 完成!
MinGW+MSYSの環境でLuaをビルド
最近MinGWで開発環境を構築しているので、自分用のメモとして書いておきます。まずはLuaのビルドについて。
公式サイトのダウンロードページか(http://www.lua.org/download.html)からソースコードのアーカイブを落として、解凍します。
Makefileの
# Where to install. The installation starts in the src and doc directories, # so take care if INSTALL_TOP is not an absolute path. INSTALL_TOP= /usr/local
を
# Where to install. The installation starts in the src and doc directories, # so take care if INSTALL_TOP is not an absolute path. INSTALL_TOP= /mingw
に書き換え、シェルで
make mingw make install
と実行します。以上で/mingw/includeと/mingw/libにヘッダファイルとライブラリがインストールされます。
SVNリポジトリが停止中
サーバメンテにより、2chViewerやNicovideoUtilなどを公開していたSVNリポジトリが現在停止しています。
近日中に復旧する予定ではありますが、ご迷惑をおかけします。
F#でMaybeモナド
最近F#を使っていなかったのでちょっと書いてみました。Computation Expression使ってます。
open System type 'A Maybe = | Just of 'A | Nothing type MaybeBuilder() = class member self.Bind(ex, f) = match ex with | Just x -> f x | Nothing -> Nothing member self.Return(x) = Just x member self.Delay(f) = f () end let maybe = new MaybeBuilder ();; let alist = [ ("A","B"); ("B","C"); ("C","D")] let rec lookup list key = match list with | [] -> Nothing | (k, v) :: xs -> if k = key then Just v else lookup xs key let search = maybe { let! x = lookup alist "Bob" let! y = lookup alist x let! z = lookup alist y return z } search |> printfn "%A" Console.ReadLine () |> ignore
Mac OSXでGtk2hsを使う
Mac OS 10.6でGtk2Hsを使ったときのメモ。HaskellWikiに書いてある方法だとgtk2hsをmakeするときに失敗したので、代替案を考えました。
- まずはsudo port install gtk +universalでgtkをインストールします。universalを指定せずにインストールした場合は、uninstallしてから+universalしてインストールし直す必要があります。
- 次に
cabal update cabal install gtk2hs-buildtools cabal install gtk
でgtk2hsをインストールします。ここでgtk2hsC2hsが見つからない、みたいなエラーが出る場合は、~/.cabal/binにパスが通っていない可能性が高いです。~/.bash_profileに
export PATH=~/.cabal/bin:$PATH
と追記しましょう
- そしてテスト用に
import Graphics.UI.Gtk main :: IO () main = do initGUI window <- windowNew widgetShowAll window mainGUI
と書いたファイルをmain.hsとして保存します。
-
これを
ghc --make main.hs
でコンパイルしますが、私の環境では
Linking main ... Undefined symbols: "_iconv_open", referenced from: _hs_iconv_open in libHSbase-4.2.0.2.a(iconv.o) (maybe you meant: _hs_iconv_open) "_iconv", referenced from: _hs_iconv in libHSbase-4.2.0.2.a(iconv.o) (maybe you meant: _hs_iconv_open, _hs_iconv , _hs_iconv_close ) "_iconv_close", referenced from: _hs_iconv_close in libHSbase-4.2.0.2.a(iconv.o) (maybe you meant: _hs_iconv_close) ld: symbol(s) not found collect2: ld returned 1 exit statusのようなリンクエラーを吐きました。このようなときは、
ghc --make main.hs -L/usr/lib
とすると上手くいきました。もちろんlibiconvを+universalでインストールしていないといけません。
- これでmainを起動するとウィンドウが開くはずです。X11なので、ちょっとデザインがださいです…OSXネイティブのAquaなUIにするためには、GTK-OSXをインストールしてGtk2Hsをビルドし直す必要がありそうです。これの詳しい方法はHaskellWikiに書いてあります。