<   2011年 11月 ( 46 )   > この月の画像一覧

みうめ

ソロ

メルト 踊ってみた【みうめ】
【NG採用】少女時代Genieを踊ってみた【みうめ】

コラボ

【K'suke】ローリンガール 踊ってみた【みうめ】
【みうめろちん】PONPONPON踊ってみた!
【みうめ&気まぐれプリンス】Romio & Cinderella 踊ってみた HD
【みうめ】kiss me 愛してるを踊ってみた【気まぐれプリンス】
【みうめ】magnet を踊ってみた【aira*】
【みうめろちん】Panda Hero パンダヒーロ踊ってみた!HD
【こずえ×のら×みうめ】みかん【踊ってみた】
【みうめ・217】KiLLER LADY 踊ってみた【東・加藤】
【みうめ】Sweet Magic スイートマジック踊ってみた【なつめ】HD

難しい振り付け

【みうめ】Nostalogic (single edit)を踊ってみたHD
[PR]
by tnomura9 | 2011-11-29 22:35 | ボーカロイド | Comments(0)

Haskell 記事リスト 応用編その2

フィルターを作ろう

コマンドライン引数を受け取る
Haskell 版 cat
Haskell 版 reverse
メモ帳内のタグをリストアップする
メモ帳を語句検索する
メモ帳を検索式で検索する
Parsec と PEG (解析表現文法)
メモ帳を検索式で検索する 構文解析
メモ帳を検索式で検索する 状態機械
メモ帳を検索式で検索する find_word2

Parsec を使おう

Parsec を使おう
Parsec の戻り値をパターンマッチに利用する Match.hs
Parsec parseTest, 1文字のパーサ
Parsec パーサコンビネータ many, many1
Parsec 並びと選択
Parsec いろいろなパターン
Parsec search : 文字列中のパターンとマッチ
Parsec replaceMatch マッチの置き換え
Parsec マッチした全ての文字列を取得 getMatchAll
Parsec を正規表現がわりに使う
PEG のパーサ
Parsec パターンをプログラムする
Parsec fmap
Parsec notFollowedBy
Parsec newline と eof
Parsec リストのフィルター
Parsec literate programming
Parsec Bird-syle からコードを抜き出す
Parsec の実例: HTMangl

48時間でSchemeを書こう

48時間でSchemeを書こう 最初の一歩
48時間でSchemeを書こう/構文解析
48時間でSchemeを書こう/構文解析 (2)
48時間でSchemeを書こう/評価: 第一部
『48時間でSchemeを書こう』のこれまでのまとめ
Haskell の例外処理
自前のエラーモナドの作り方
Either モナド?
48時間でSchemeを書こう/エラー処理と例外
48時間でSchemeを書こう/評価: 第二部
条件分岐: パターンマッチ2
リストのプリミティブ: car、cdrとcons
ダック・タイピング
存在型 (Existentially quantified data constructors)
48時間でSchemeを書こう/評価: 第二部 (2)
48時間でSchemeを書こう/REPLの作成
Data.IORef モジュール
48時間でSchemeを書こう/変数と代入
48時間でSchemeを書こう/変数と代入 (2)
48時間でSchemeを書こう/変数と代入 (3)
48時間でSchemeを書こう/変数と代入 (4)
48時間でSchemeを書こう/Scheme関数の定義

圏論でもやってみよう

圏論は面白い(1) メタグラフ
圏論は面白い(2) メタグラフ(2)
圏論は面白い(3) メタ圏
圏論は面白い(4) メタ圏(2) モノイド
圏論は面白い(5)  関手
圏論は面白い(6)  自然変換
圏論は面白い(7)  随伴
圏論は面白い(8)  モナド
圏論は面白い(9)  Kleisli 圏
[PR]
by tnomura9 | 2011-11-29 22:13 | Haskell 記事リスト | Comments(0)

Parsec replaceMatch マッチの置き換え

Parsec でマッチした部分を置き換える関数を作成した。基本的なアイディアは次のようになる。

ghci> parse (do {m <- manyTill anyChar (string "world"); n <- many anyChar; return (m ++ "there" ++ n)}) "" "hello, world"
Right "hello, there"

プログラムにすると次のようになるがやや物々しくなる。

replaceMatch expr str line =
  case parse replaceParser "" line of
    Left _ -> line
    Right x -> x
  where
    replaceParser = do
      m <- manyTill anyChar (try expr)
      n <- many anyChar
      return (m ++ str ++ n)

実行例:
*Match> replaceMatch (string "world") "there" "hello, world"
"hello, there"
*Match> replaceMatch (string "nothing") "there" "hello, world"
"hello, world"

ついでに一行に現れるマッチ全てを置き換える関数 replaceMatchAll も作ってみた。

replaceMatchAll expr str line =
  case parse replaceAllParser "" line of
    Left _ -> line
    Right x -> x
  where
    replace1Parser =
      do
        m <- manyTill anyChar (try expr)
        return (m ++ str)
    replaceAllParser =
      do
        n <- replace1Parser
        m <- try replaceAllParser <|> many anyChar
        return (n ++ m)

実行例:

ghci> replaceMatchAll (string "world") "there" "hello world hello world hello"
"hello there hello there hello"
ghci> replaceMatchAll (string "l") "L" "hello world hello world hello"
"heLLo worLd heLLo worLd heLLo"
ghci> replaceMatchAll (string "nothing") "there" "hello world hello world hello"
"hello world hello world hello"
[PR]
by tnomura9 | 2011-11-29 13:13 | Haskell | Comments(0)

Parsec search : 文字列中のパターンとマッチ

Parsec のパーサは、プログラム言語の構文解析が目的なので、パーサは文字列の先頭から始まるパターンにしかマッチしない。しかし、正規表現のように文字列の中ほどのパターンにマッチしてくれるパーサがないと不便だ。そこで、パーサ expr が文字列の中ほどにあってもマッチするようなパターンをつくるパーサ・コンビネータ search を作ってみた。定義は次のようになる。

ghci> let search expr = try (expr) <|> do {anyChar; search expr}

実行例:
Prelude> :m Text.ParserCombinators.Parsec
Prelude Text.ParserCombinators.Parsec> :set prompt "ghci> "
ghci> let search expr = expr <|> do {anyChar; search expr}
ghci> parseTest (search (string "world")) "hello, world"
"world"
ghci> parseTest (search (char 'w')) "hello, world"
'w'
ghci> parseTest (search (string "nothing")) "hello, world"
parse error at (line 1, column 13):
unexpected end of input

これで、安心して正規表現から Parsec へ移行できる。
[PR]
by tnomura9 | 2011-11-29 04:43 | Haskell | Comments(0)

Parsec いろいろなパターン

このページでは、Parsec で記述できる色々なパターンを集めるつもり。Parsec のパワーを感じさせる例を集めていければいいと思う。

ghci のセッティング

Prelude> :m Text.ParserCombinators.Parsec
Prelude Text.ParserCombinators.Parsec> :set prompt "ghci> "

入れ子になった括弧

ghci> let parens = do { char '('; parens; char ')'; parens } <|> return ()
ghci> parseTest parens "(())"
()
ghci> parseTest parens "(()"
parse error at (line 1, column 4):
unexpected end of input
expecting "(" or ")"

HTMLのコメント

ghci> let simpleComment = do string "<!-"; manyTill anyChar (try (string "-->"))
ghci> parseTest simpleComment "<!- this is a comment -->"
" this is a comment "

トークンを切り出す

ghci> let getToken = do {tk <- (many1 letter <|> many1 digit <|> count 1 (oneOf "+-*/=")); spaces; return tk}
ghci> parseTest (many getToken) "let a = 12 + 34"
["let","a","=","12","+","34"]

複数の空白文字で区切られた単語を抜き出す定石

ghci> parseTest (many (do m <- many1 letter; spaces; return m)) "apple orenge lemon"
["apple","orenge","lemon"]
[PR]
by tnomura9 | 2011-11-28 01:04 | Haskell | Comments(0)

Parsec 連接と選択

個々のパーサは単独では余り利用価値がない。パーサを組み合わせることで多様なパターンに対応できる。組み合わせかたの「くりかえし」については前回に述べた。この記事では、パターンの連接と選択について調べてみる。

Parsec で使われる要素的なパーサは Parsec モナドの関数だ。IOモナドの時と同じように、モナドの関数を合成してもそれはやはりそのモナドの関数になる。つまり、Parsec モナドの関数であるパーサを合成してもやはり、Parsec モナドの関数つまりパーサになるということだ。

たとえば、(many letter) という関数はアルファベットの文字列のパーサだ。また、(many digit) というのは、数字の列のパーサだ。この2つを使って、文字列の次に数字の列が来るようなパターンにマッチするパーサを組み立てたいときはどうすればいいだろうか。このようなパターンの連接(並び)を作るには、モナドの do 記法を使う。そこで、次のような alnum という新しいパーサを定義してみる。

Prelude> :m Text.ParserCombinators.Parsec
Prelude Text.ParserCombinators.Parsec> let alnum = do many letter; many digit
Prelude Text.ParserCombinators.Parsec> parseTest alnum "hello123 world"
"123"

上の例では確かにマッチしているが、戻値は後半のマッチだけだ。マッチの全体を戻値として得るためには、alnum を次のように定義すればいい。

Prelude Text.ParserCombinators.Parsec> let alnum = do a <- many letter; b <- many digit; return (a ++ b)
Prelude Text.ParserCombinators.Parsec> parseTest alnum "hello123 world"
"hello123"

Parsec のパターンマッチのうれしいところは、Perl では正規表現が言語内言語として使用されているのに対し、あくまでも Haskell で記述できるということだ。上のような細かい調整が、Haskell で記述できるので新しい言語を覚える必要がない。

それでは、(many letter) または (many digit) にマッチするパーサを作ってみよう。

Prelude Text.ParserCombinators.Parsec> let alOrNum = many1 letter <|> many1 digit
Prelude Text.ParserCombinators.Parsec> parseTest alOrNum "123hello"
"123"

パターンの選択の場合はパーサを <|> 演算子で結合するとよいことが分かる。

これで、Parsec を使ってパターンマッチを使うプログラムの作り方に関する記事は終わりだ。

最後に、Parsec によるパターンマッチを使ったサンプルプログラム match_test を紹介する。*.hs ファイルの中から = 記号を見つけて関数の名前をリストアップするプログラムだ。以前に紹介した Match.hs を利用する。コンパイルは ghc --make mathc_test.hs -o match_test で行う。

実行例:
>match_test Match.hs
match expr line =
getMatch expr line =

ソースファイルは次のようになる。

ファイル名: match_test.hs

module Main where

import Text.ParserCombinators.Parsec
import Match
import System.Environment (getArgs)

concatFile :: [FilePath] -> IO [Char]
concatFile [] = return []
concatFile (f:fs) = do
  xs <- readFile f
  rest <- concatFile fs
  return $ xs ++ rest

func_def = manyTill anyChar (char '=')

main = do
  args <- getArgs
  cs <- if null args
    then getContents
    else concatFile args
  putStrLn $ unlines $ filter (match func_def) $ lines cs
[PR]
by tnomura9 | 2011-11-27 19:27 | Haskell | Comments(0)

Parsec パーサコンビネータ many, many1

パーサコンビネータとは、パーサ(関数)を引数に取る高階関数のことで、パーサを組み合わせて新しいパーサを組み立てることができる。正規表現の * や + と同じ作用をするのが、many と many1 というパーサコンビネータだ。

many は引き数のパーサを0回以上くりかえすパターンにマッチする。例えば letter は英文字1字にマッチするので、many letter は "hello world" のスペースが出現するまでの部分にマッチする。

Prelude> parseTest (many letter) "hello world"
"hello"

このような使い方の時は many1 でも動作は同じだ。

Prelude> parseTest (many1 letter) "hello world"
"hello"

しかし、最初からひとつも英文字がない次のような場合は、many はマッチするが、many1 まマッチ・エラーになる。

Prelude Text.ParserCombinators.Parsec> parseTest (many1 letter) "123"
parse error at (line 1, column 1):
unexpected "1"
expecting letter

skipMany, skipMany1 は many, many1 と同じマッチをするが、結果は捨てさってしまう。

Prelude> parseTest (skipMany letter) "hello world"
()

sepBy, sepBy1 は、引き数に取り出したいデータのパーサとセパレターにマッチするパーサをとり、セパレータでデータを分割してリストにして戻す。ややこしいが、トライアンドエラーで何回か使ってみると、そのありがたさが分かる。

Prelude> parseTest (sepBy (many letter) (char ',')) "apple,banana,orange"
["apple","banana","orange"]

endBy, endBy1 は sepBy と同じやり方で終端記号で行を分割する。

Prelude> parseTest (endBy (many letter) (char ';')) "hello;world;"
["hello","world"]

sepEndBy, sepEndBy1 は sepBy と sepEnd を組み合わせたような動作をする。

Prelude> parseTest (sepEndBy (many letter) (oneOf ",;")) "hello,world;how,are,you"
["hello","world","how","are","you"]

count は引き数に個数とパーサをとり、そのパーサにマッチを回数指定でマッチする。

Prelude> parseTest (count 3 (string "hello")) "hellohellohellohellohello"
["hello","hello","hello"]

between は記号や文字列で挟まれた部分とマッチする。

Prelude> parseTest (between (char '{') (char '}') (many letter)) "{hello} world"
"hello"

option は第2引数のパターンマッチが失敗した時、第1引き数の値を返す。パターンマッチが成功すればその値が戻される。

Prelude> parseTest (option "universe" (string "world")) "hello world"
"universe"
Prelude> parseTest (option "universe" (string "hello")) "hello world"
"hello"

choice はリストにしたパターンのどれかにマッチすればその値を戻す。

Prelud> parseTest (choice [many1 letter, many1 digit]) "123 hello"
"123"

manyTill p end はend のパターンが現れるまでの部分を取り出す。

Prelude> parseTest (manyTill anyChar (char ';')) "hello world; nice to meet you"
"hello world"

chainl, chainl1 は、左結合の演算のパーサを作るときに便利な関数だが面倒なのでメモだけ。

chainr, chainr1 は、右結合の演算のパーサを作るときに使う。これもメモだけ

eof はファイルの終わりを判別する。

Prelude> parseTest eof ""
()
Prelude> parseTest eof "a"
parse error at (line 1, column 1):
unexpected "a"
expecting end of input

notFollowedBy は、最長マッチを実現するためにつかうパーサ。これもメモのみ

anyToken パースするトークンが残っているかどうかの検査。これもメモのみ。
[PR]
by tnomura9 | 2011-11-27 17:59 | Haskell | Comments(0)

Parsec parseTest, 1文字のパーサ

Parsec のパーサをテストするのには parseTest を使うのが便利だ。Parsec を使ってパーサを動かすときは、parse 関数を使うが、parseTest 関数は引数が2つ、すなわち、パーサ関数と文字列で、戻り値をprint で表示してくれるので、自作のパーサの動作を検証できる。

実行例:
Prelude> :m Text.ParserCombinators.Parsec
Prelude Text.ParserCombinators.Parsec> parseTest (many letter) "hello world"
"hello"

Parsec には、1文字を検出するパーサがたくさんそろっている。正規表現よりも種類が豊富だ。

oneOf は文字集合のどれかにマッチする。
Prelude> parseTest (oneOf "abc") "bird"
'b'

noneOf は文字集合のどれともマッチしないものにマッチする。
Prelude> parseTest (noneOf "abc") "def"
'd'

char は引数で指定した1文字にマッチする。
Prelude> parseTest (char 'a') "abc"
'a'

string は引数で指定した文字列にマッチする。
Prelude> parseTest (string "abc") "abcdef"
"abc"

anyChar は任意の1文字にマッチする。正規表現の . と同じ。
Prelude> parseTest anyChar "abc"
'a'

upper は英大文字にマッチする。
Prelude> parseTest upper "ABC"
'A'

lower は英小文字にマッチする。
Prelude> parseTest lower "abc"
'a'

letter はアルファベットにマッチする。
Prelude> parseTest letter "abc"
'a'

alphaNum はアルファベットと数字にマッチする。
Prelude> parseTest alphaNum "123"
'1'

digit は数字にマッチする。
Prelude> parseTest digit "123"
'1'

hexDigit は16進数に使う文字種にマッチする。
Prelude> parseTest hexDigit "AE"
'A'

octDigit は8進数に使う文字種にマッチする。
Prelude Text.ParserCombinators.Parsec> parseTest octDigit "777"
'7'

newline は改行記号 '\n' にマッチする。
Prelude> parseTest newline "\nabc"
'\n'

tab はタブ記号 '\t' にマッチする。
Prelude> parseTest tab "\tabc"
'\t'

space は空白記号 " \v\f\t\r\n" にマッチする。
Prelude> parseTest space " abc"
' '

spaces は複数の空白にマッチする。
Prelude> parseTest spaces " abc"
()

satisfiy は引数に条件式を取り、その条件にあった文字種にマッチする。
Prelude> parseTest (satisfy (\c -> c `elem` "abc")) "cde"
'c'
[PR]
by tnomura9 | 2011-11-27 16:27 | Haskell | Comments(0)

Parsec の戻り値をパターンマッチに利用する。

Parsec は本来パーサをプログラムするためのモナドとして設計されているので、これをパターンマッチに利用するためには少々工夫が必要だ。そこで、Parsec をパターンマッチに利用するための関数 match と getMatch を考えてみた。

ファイル名: Match.hs

module Match where

import Text.ParserCombinators.Parsec

match expr line =
  case parse expr "" line of
    Left _ -> False
    Right _ -> True

getMatch expr line =
  case parse expr "" line of
    Left _ -> Nothing
    Right x -> Just x

getMatchAll expr line =
  case parse getAllParser "" line of
    Left _ -> Nothing
    Right x -> Just x
  where
    get1Parser = try (expr) <|> do {anyChar; get1Parser}
    getAllParser = do
        n <- get1Parser
        m <- try (getAllParser) <|> do {many anyChar; return []}
        return ([n] ++ m)

search expr = try (expr) <|> do {anyChar; search expr}

replaceMatch expr str line =
  case parse replaceParser "" line of
    Left _ -> line
    Right x -> x
  where
    replaceParser = do
      m <- manyTill anyChar (try expr)
      n <- many anyChar
      return (m ++ str ++ n)

replaceMatchAll expr str line =
  case parse replaceAllParser "" line of
    Left _ -> line
    Right x -> x
  where
    replace1Parser =
      do
        m <- manyTill anyChar (try expr)
        return (m ++ str)
    replaceAllParser =
      do
        n <- replace1Parser
        m <- try replaceAllParser <|> many anyChar
        return (n ++ m)

実行例:
*Match> match (string "he") "hello"
True
*Match> getMatch (many letter) "hello123"
Just "hello"
*Match> getMatch (search (string "world")) "hello, world"
Just "world"
*Match> getMatchAll (do m <- string "a"; n <- count 1 anyChar; return (m++n)) "apple juice, bad apple"
Just ["ap","ad","ap"]
*Match> replaceMatch (string "world") "there" "hello world"
"hello there"
*Match> replaceMatchAll (string "world") "there" "hello world hello world hello"
"hello there hello there hello"

これがあれば、後は Parsec のパーサの作り方さえ習得すれば、正規表現でできるようなパターンマッチをすべて Parsec を使ってやることができる。
[PR]
by tnomura9 | 2011-11-27 11:19 | Haskell | Comments(0)

Parsec を使おう

Haskell の学習を始めて再帰的定義とIOモナドの壁を乗り越え、とりあえずHaskell のプログラムを作れるようになった新米 Haskeller が次に感じるのはどんなことだろうか。

それは、Haskell の標準環境である Prelude ではあまりにも文字列処理の機能が貧弱だということだ。

lines や unlines のような便利な関数はあるものの、文字列のパターンマッチの機能がほとんどない。Ruby や Perl から 正規表現の機能がなくなったらどうだろうか、これらの言語を使おうという意欲が半減するのは間違いない。Haskell にはその正規表現の関数がないのだ。

普通のプログラマにとって、素数やフィボナッチ数列がどんなに簡単に記述できても、あまりメリットは感じられない。普通のプログラマの抱えている問題は、ほとんどが文字列処理の問題だからだ。たとえば、書籍のリストから ISBN の番号を取り出すとか、HTML 文書からリンクの情報のみを抜き出すなどの処理は、ほとんどが文字列のバターン処理の機能を必要としている。文字列処理のできないプログラム言語は趣味にしか使えない。

しかし、実は Haskell platform をインストールしたときに文字列パターン処理の機能はちゃんと標準仕様でインストールされているのだ。それが、Parsec だ。

Parsec というと、インタプリターやコンパイラのパーサを作るための道具だとの印象がある。構文解析プログラムの理論を勉強するのはたいへんなので、自分には関係ないやと Parsec はすぐに頭の中のリストから削除してしまいがちだ。

しかし、Parsec を少しかじって分かった事だが、プログラム言語のパーサの記述は、Parsec の応用のひとつでしかないということだ。Parsec の本領は文字列のパターン処理なのだ。言語のパーサなど記述できなくても、Parsec のパーサやパーサコンビネータを使うことで、上で述べたような文字列処理が正規表現以上に簡単に実行することができる。

たとえば、Rubyで正規表現を使ったプログラムは次のようになる。

irb(main):007:0> def testreg (str)
irb(main):008:1> if /abc/ =~ str
irb(main):009:2> puts "match"
irb(main):010:2> end
irb(main):011:1> end
=> nil
irb(main):012:0> testreg ("abcde")
match
=> nil

同じ事を Parsec を使うと次のようにできる。

Prelude Text.ParserCombinators.Parsec> let testreg str = parseTest (string "abc") str
Prelude Text.ParserCombinators.Parsec> testreg "abcde"
"abc"

上の例はほんの一例だが、文字の繰り返しや、文字列のパターンなど、正規表現でできるものは、全く同じように Parsec で記述することができる。さらに、ネストした括弧の対応づけなど正規表現では表現できないパターン処理も Parsec なら楽々とやってのける。なにしろ、プログラム言語の構文解析も Parsec だけでやってのけることができるので当然だ。

プログラム言語のパーサを書く気がなくても、文字列処理を行いたい Haskeller にとって Parsec の使い方を覚えるのは必須の知識なのだ。Ruby や Perl に正規表現が必須であるのと同じくらい Haskell には Parsec が必要だ。
[PR]
by tnomura9 | 2011-11-26 05:45 | Haskell | Comments(0)