|
Haskell をつかって３×３の魔法陣を作ってみた。全自動ではなく、候補を絞っただけで結局手作業になった。 最初にマス目の合計の数を求めた。これは 1 .. 9 の総和の３分の１になる。 Prelude> sum [1..9] `div` 3 15 次に組み合わせを計算するプログラムを作成して、1 .. 9 から３個を取る組み合わせを作った。 Prelude> :{ Prelude| comb 0 _ = [[]] Prelude| comb _ [] = [] Prelude| comb n (x:xs) = map (x:) (comb (n-1) xs) ++ comb n xs Prelude| :} Prelude> a = comb 3 [1..9] Prelude> a [[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,2,7],[1,2,8],[1,2,9],[1,3,4],[1,3,5],[1,3,6],[1,3,7],[1,3,8],[1,3,9],[1,4,5],[1,4,6],[1,4,7],[1,4,8],[1,4,9],[1,5,6],[1,5,7],[1,5,8],[1,5,9],[1,6,7],[1,6,8],[1,6,9],[1,7,8],[1,7,9],[1,8,9],[2,3,4],[2,3,5],[2,3,6],[2,3,7],[2,3,8],[2,3,9],[2,4,5],[2,4,6],[2,4,7],[2,4,8],[2,4,9],[2,5,6],[2,5,7],[2,5,8],[2,5,9],[2,6,7],[2,6,8],[2,6,9],[2,7,8],[2,7,9],[2,8,9],[3,4,5],[3,4,6],[3,4,7],[3,4,8],[3,4,9],[3,5,6],[3,5,7],[3,5,8],[3,5,9],[3,6,7],[3,6,8],[3,6,9],[3,7,8],[3,7,9],[3,8,9],[4,5,6],[4,5,7],[4,5,8],[4,5,9],[4,6,7],[4,6,8],[4,6,9],[4,7,8],[4,7,9],[4,8,9],[5,6,7],[5,6,8],[5,6,9],[5,7,8],[5,7,9],[5,8,9],[6,7,8],[6,7,9],[6,8,9],[7,8,9]] このうち合計が１５になるものを選別した。 Prelude> b = filter (\x -> sum x == 15) a Prelude> b [[1,5,9],[1,6,8],[2,4,9],[2,5,8],[2,6,7],[3,4,8],[3,5,7],[4,5,6]] 意外と少ない。しかし、この中から３つを選び出さなければならない。これらを含まれる数字ごとにグループ分けした。 Prelude> c = map (\x -> filter (elem x) b) [1..9] Prelude> c [[[1,5,9],[1,6,8]],[[2,4,9],[2,5,8],[2,6,7]],[[3,4,8],[3,5,7]],[[2,4,9],[3,4,8],[4,5,6]],[[1,5,9],[2,5,8],[3,5,7],[4,5,6]],[[1,6,8],[2,6,7],[4,5,6]],[[2,6,7],[3,5,7]],[[1,6,8],[2,5,8],[3,4,8]],[[1,5,9],[2,4,9]]] 見づらいのでヒストグラムにしてみた。 Prelude> mapM_ print c [[1,5,9],[1,6,8]] [[2,4,9],[2,5,8],[2,6,7]] [[3,4,8],[3,5,7]] [[2,4,9],[3,4,8],[4,5,6]] [[1,5,9],[2,5,8],[3,5,7],[4,5,6]] [[1,6,8],[2,6,7],[4,5,6]] [[2,6,7],[3,5,7]] [[1,6,8],[2,5,8],[3,4,8]] [[1,5,9],[2,4,9]] 含まれる数字が同じものが４組あるのは５だけだ。魔法陣の中心にあるのは４つの和を計算しなければならないので、５がマスの中心でなければならないことが分かる。 そこで、最初の [1,5,9] を真ん中の行にすると仮定してみた。このうち 1 について見ると [1,5,9] と [1,6,8] の組み合わせしかない。１の縦方向の数字を６と８であると仮定したすると、魔法陣を次のように部分的に決定する。 6 * * 1 5 9 8 * * 6 と 5 が含まれる組み合わせは [4,5,6] だから６の対角線上の値は 4 だ。同様に 8 の対角線上の値は 2 だ。 6 * 2 1 5 9 8 * 4 6 が含まれる組み合わせをみると 2 が含まれるのは 7 だから魔法陣の１行目は 6 7 2 になる。同様に３行目は、8 3 4 だ。念の為第２列の和を取ると 7 + 5 + 3 = 15 で大丈夫だということが分かる。したがって、求める魔法陣は次のようになる。 6 7 2 1 5 9 8 3 4 ここで改めて組み合わせのヒストグラムを眺めてみると、組み合わせの数が３つなのは 2, 4, 6, 8 でこれらは正方形の頂点に来なくてはならない。また、組み合わせの数が２つなのは 1, 3, 7, 9 で、これらは正方形の辺の中央にしか置けない。 中央の数が５であるのは必然だが、その５に対して辺の数は (1, 9) と (3, 7) の組み合わせしかない。すると、魔法陣の十字の部分は必然的に決定してしまう。これは、５を中心に点対称や、線対称を作って重なる場合を考えそれらを同じものと考えると、可能性は一つしかない。そうして、真ん中の十字の部分が決定してしまうと必然的に頂点の部分も決定してしまう。したがって、３×３の魔法陣はこれ一つしかないことになる。 ３×３の魔法陣はそれぞれの数字が緊密な関係を保っていて、まさに魔法陣なのだ。
#
by tnomura9
| 2019-06-25 19:30
| Haskell
|
Comments(0)
ハノイの塔のパズルは、土台に横一列に３本の柱が並んで立っており、その柱には中心に穴の空いた円盤がさしてある。円盤は最初は左端の柱に大きい方から下から順番に棒に通して重ねてある。 パズルの目的はこの円盤を右端の柱に全て移してしまうことだ。柱の数は３本あるのでそのうちの１本は作業用として使うことができる。ただし、円盤は１回に１枚しか動かせない。また、小さい円盤の上に大きい円盤を重ねることはできない。このパズルはしかし、コンピュータのプログラムで解法を見つけることができる。 お手本のプログラムを写経して動くのを確認して見たことはあるのだが、そのアルゴリズムがもう一つよくわからなかったので Haskell で実験することにした。プログラムは何回も手直しが必要だと思われたので、ファイルに作成した。ファイル名は hanoi.hs にした。 先ず３本の棒の場所を表すデータ型 Place を作った。 module Hanoi where data Place = A | B | C deriving Show 次に、円盤が１枚だけのパズルの解答を考えてみた。hanoi 関数は円盤の枚数と、円盤の置かれている場所 from とそれを移動する先の to と円盤を一時置いておくための場所の work を引数として、移動を表すペア、たとえば A -> C なら (A,C) のリストを戻り値とした。 円盤の移動の一番単純な形は、円盤が１枚だけのときだ。このときは、円盤は from から to へ移動させることができる。つまり、次のようになる。 hanoi :: Int -> Place -> Place -> Place -> [(Place, Place)] hanoi 1 from to work = [(from, to)] 実行例は次のようになる。 *Hanoi> hanoi 1 A C B [(A,C)] これは A の場所から C の場所へ円盤を移したことを示している。作業用の B の場所には何も置かれていないので使われていない。 次に円盤が２枚の場合を考えてみた。２枚めの円盤を A から C に移し、B に置いてあった１枚目の円盤を B から C に移す。この動作を hanoi 2 from to work を利用して定義すると、１枚目の板は work 領域に置いてあるはずだから、hanoi 1 work to from になるはずだ。 hanoi :: Int -> Place -> Place -> Place -> [(Place, Place)] hanoi 1 from to work = [(from, to)] hanoi 2 from to work = [(from, to)] ++ hanoi 1 work to from 実行例は次のようになるがなにかおかしい。 *Hanoi> hanoi 2 A C B [(A,C),(B,C)] リストの最初の (A,C) は２枚めの板を A -> C に移動させることを示しており、(B -> C) は１枚目の板を B -> C に移動させることを意味しているが、１枚目の板は最初は A にあったはずなのにいきなり B のところにあることになっている。これは実際のパズルとは違う。 しばらく考えてもわからなかったのでカンニングしたら謎が解けた。上のプログラムでは、最初に１枚目の板を B へ移す動作が記述されていなかったのだ。そこで、それを加えてみた。 hanoi :: Int -> Place -> Place -> Place -> [(Place, Place)] hanoi 1 from to work = [(from, to)] hanoi 2 from to work = hanoi 1 from work to ++ [(from,to)] ++ hanoi 1 work to from 実行例は次のようになった。 *Hanoi> hanoi 2 A C B [(A,B),(A,C),(B,C)] この結果なら、１枚目の板を A -> B に移し、２枚めを A -> C へ、最後に１枚めを B -> C へ移すので実際のパズルとも合致している。 そこで板が３枚の場合も考えてみた。３枚の板を移動するときに２枚の板を移動させるプログラムを活用することにする。 hanoi :: Int -> Place -> Place -> Place -> [(Place, Place)] hanoi 1 from to work = [(from, to)] hanoi 2 from to work = hanoi 1 from work to ++ [(from, to)] ++ hanoi 1 work to from hanoi 3 from to work = hanoi 2 from work to ++ [(from, to)] ++ hanoi 2 work to from 結果は次の様になった。 *Hanoi> hanoi 3 A C B [(A,C),(A,B),(C,B),(A,C),(B,A),(B,C),(A,C)] hanoi 2 と hanoi 3 は同じ形をしているので、このようなものは再帰的定義の recursive case として定義することができる。 hanoi :: Int -> Place -> Place -> Place -> [(Place, Place)] hanoi 1 from to work = [(from, to)] hanoi 2 from to work = hanoi 1 from work to ++ [(from, to)] ++ hanoi 1 work to from hanoi 3 from to work = hanoi 2 from work to ++ [(from, to)] ++ hanoi 2 work to from hanoi n from to work = hanoi (n-1) from work to ++ [(from,to)] ++ hanoi (n-1) work to from 実行例は次の様になる。 *Hanoi> hanoi 4 A C B [(A,B),(A,C),(B,C),(A,B),(C,A),(C,B),(A,B),(A,C),(B,C),(B,A),(C,A),(B,C),(A,B),(A,C),(B,C)] これは１枚めをBに置き、２枚めをCに置き、Bの１枚めをCの２枚めの上に起き、空いたBのスベースに３枚めを置き、... と読めるから実際のパズルの動きをイメージでシミュレーションしてみると正しい答えのようだ。 hanoi n from to work 関数は hanoi 2 from to work と hanoi 3 from to work を含むのでプログラムを次のように整理した。 module Hanoi where data Place = A | B | C deriving Show hanoi :: Int -> Place -> Place -> Place -> [(Place, Place)] hanoi 1 from to work = [(from, to)] hanoi n from to work = hanoi (n-1) from work to ++ [(from,to)] ++ hanoi (n-1) work to from 最終的に出来上がったプログラムをみたら、なんのことはない、quick ソートと同じ両側への再帰だった。ｎ枚の板を動かすには先ず (n-1) 枚の板を work へ移動させ、次にｎ枚目の板を from から to へ移動させる。最後に (n-1) 枚の板を work から to へ移動させるという手順そのままのプログラムだ。 再帰的プログラムをいきなり作るのはハードルが高いが、Haskell ではパターンプログラミングができるので、実際の単純な例のプログラムを最初に作ってみて、最後に統一的な再帰的定義として完成させるというような芸当ができる。パターンプログラミングの威力を感じる例だ。
#
by tnomura9
| 2019-06-25 07:49
| Haskell
|
Comments(0)
Text.Printf モジュールと Data.List.Split モジュールを使って、リスト [1 .. 9] を３カラムの行列に分割し、桁幅５の整数フォーマットで表示してみた。 Prelude> import Data.List.Split Prelude Data.List.Split> import Text.Printf Prelude Data.List.Split Text.Printf> :set prompt "> " > mapM_ (\x -> mapM_ (printf "%5d") x >> putStrLn "") $ chunksOf 3 [1..9] 1 2 3 4 5 6 7 8 9 Text.Printf モジュールをインポートすると、C の printf のようなフォーマット付きの出力が使える。 > printf "%s, %d, %.4f" "hello" 123 pi >> putStrLn "" hello, 123, 3.1416 Data.List.Split モジュールには、様々なデリミタで文字列からデータのリストを作る関数が定義されている。 > splitOn "x" "axbxc" ["a","b","c"] > splitOn "x" "axbxcx" ["a","b","c",""] > endBy ";" "foo;bar;buz;" ["foo","bar","buz"] > splitWhen (<0) [1,3,-4,5,7,-9,0,2] [[1,3],[5,7],[0,2]] > splitOneOf ";.," "foo,bar,baz,glurk" ["foo","bar","baz","glurk"] > chunksOf 3 ['a'..'z'] ["abc","def","ghi","jkl","mno","pqr","stu","vwx","yz"] ちなみに chunks を自前で実装すると次のようになる。 > {chunks n [] = []; chunks n xs = take n xs : chunks n (drop n xs)}
> chunks 3 [1..9] [[1,2,3],[4,5,6],[7,8,9]] > chunks 3 ['a'..'z'] ["abc","def","ghi","jkl","mno","pqr","stu","vwx","yz"] #
by tnomura9
| 2019-06-23 07:42
| Haskell
|
Comments(0)
川渡りパズルの Haskell による解き方は、Haskell のパターンプログラミングのいい例ではないかと思う。 川渡りパズルというのは、川岸に農夫が狐と鵞鳥と豆袋を小舟を使って向こう岸に渡るにはどうすればいいかという問題だ。ただし、小舟には漁師以外にそれらのうちの一つしか乗せられない。また、狐と鵞鳥だけを残して農夫が向こう岸へ渡ってしまうと狐は鵞鳥を食べてしまう。また、鵞鳥と豆袋を残して農夫が向こう岸へ渡ってしまうと鵞鳥が豆を食べてしまう。 狐に鵞鳥を食べさせないように、また、鵞鳥に豆を食べさせないように狐と鵞鳥と豆袋を向こう岸へ渡らせるにはどうしたらよいだろうか。 このパズルは Haskell のプログラムで解くことができる。プログラムは farmer.hs というファイルに作成した。（文頭のアンダースコアはスペースに置き換える。） ファイル名：farmer.hs import Data.List data Member = Fox | Goose | Beans deriving (Show, Eq, Ord) data Farmer = LeftSide | RightSide deriving (Show, Eq) data State = State {left :: [Member], right :: [Member], farmer :: Farmer} deriving (Show, Eq) beginState :: State beginState = State [Fox, Goose, Beans] [] LeftSide goal :: State -> Bool goal s = left s == [] forbidden :: [Member] -> Bool forbidden xs = (elem Fox xs && elem Goose xs) || (elem Goose xs && elem Beans xs) available :: State -> Bool available s = (farmer s == LeftSide && (not $ forbidden $ right s)) || (farmer s == RightSide && (not $ forbidden $ left s)) updateLeft :: State -> [State] updateLeft s = filter available $ [State (delete x $ left s) (sort $ x:right s) RightSide | x <- left s] ++ [State (left s) (right s) RightSide] updateRight :: State -> [State] updateRight s = filter available $ [State (sort $ x:left s) (delete x $ right s) LeftSide | x <- right s] ++ [State (left s) (right s) LeftSide] findNext :: State -> [State] findNext s __ | farmer s == LeftSide = updateLeft s __ | otherwise = updateRight s search :: State -> [State] -> [[State]] search s path __ | goal s = [reverse (s:path)] __ | otherwise = concatMap (\x -> search x (s:path)) [x | x <- findNext s, (not $ elem x path)] main :: IO () main = mapM_ (\x -> (mapM_ print x >> putStr "\n")) $ search beginState [] 実行例は次のようになる。 Prelude> :l farmer.hs [1 of 1] Compiling Main ( farmer.hs, interpreted ) Ok, modules loaded: Main. *Main> main State {left = [Fox,Goose,Beans], right = [], farmer = LeftSide} State {left = [Fox,Beans], right = [Goose], farmer = RightSide} State {left = [Fox,Beans], right = [Goose], farmer = LeftSide} State {left = [Beans], right = [Fox,Goose], farmer = RightSide} State {left = [Goose,Beans], right = [Fox], farmer = LeftSide} State {left = [Goose], right = [Fox,Beans], farmer = RightSide} State {left = [Goose], right = [Fox,Beans], farmer = LeftSide} State {left = [], right = [Fox,Goose,Beans], farmer = RightSide} State {left = [Fox,Goose,Beans], right = [], farmer = LeftSide} State {left = [Fox,Beans], right = [Goose], farmer = RightSide} State {left = [Fox,Beans], right = [Goose], farmer = LeftSide} State {left = [Fox], right = [Goose,Beans], farmer = RightSide} State {left = [Fox,Goose], right = [Beans], farmer = LeftSide} State {left = [Goose], right = [Fox,Beans], farmer = RightSide} State {left = [Goose], right = [Fox,Beans], farmer = LeftSide} State {left = [], right = [Fox,Goose,Beans], farmer = RightSide} 面倒くさそうなプログラムの様に見えるがそうではない。ひとつづつ追いかけてみよう。対訳風にコメントをつけてみる。 data Member = Fox | Goose | Beans deriving (Show, Eq, Ord) 農夫以外のメンバーには Fox と Goose と Beans がいる。 data Farmer = LeftSide | RightSide deriving (Show, Eq) 農夫は川の左岸にいるか、右岸にいるかのどちらかである。 data State = State {left :: [Member], right :: [Member], farmer :: Farmer} deriving (Show, Eq) 農夫とメンバーとの位置関係を State (状態）で表す。状態のフィールドは、左岸にいるメンバーのリスト、右岸にいるメンバーのリスト、農夫が左岸にいるか右岸にいるかを表している。 beginState = State [Fox, Goose, Beans] [] LeftSide 最初の State （状態）はメンバーが３つとも左岸にいて、農夫も左岸にいる。右岸にはメンバーは誰もいない。 goal s = left s == [] State（状態の）ゴールは左岸に誰もいないことだ。 forbidden xs = (elem Fox xs && elem Goose xs) || (elem Goose xs && elem Beans xs) 禁止された状態とは、メンバーのリスト xs の中に Fox と Goose が同時に含まれるか、Goose と Beans が同時に含まれている場合だ。 available s = (farmer s == LeftSide && (not $ forbidden $ right s)) || (farmer s == RightSide && (not $ forbidden $ left s)) 利用可能な状態とは、農夫が左岸にいて右岸のメンバーが禁止された状態ではないか、または、農夫が右岸にいて左岸のメンバーが禁止された状態ではない場合である。 updateLeft s = filter available $ [State (delete x $ left s) (sort $ x:right s) RightSide | x <- left s] ++ [State (left s) (right s) RightSide] 左岸の状態を更新する。左岸のメンバーの一つを右岸に移し、農夫を右岸に移すか（複数の状態の可能性がある）または、メンバーの移動はせず農夫だけが右岸に移る。さらに、filter available 関数で禁止状態のない状態を選び出す。戻り値は可能な状態のリストだ。 updateRight s = filter available $ [State (sort $ x:left s) (delete x $ right s) LeftSide | x <- right s] ++ [State (left s) (right s) LeftSide] 右岸の状態を更新する。ということは、右岸のメンバーの一つを左岸に移し、農夫を左岸に移すか（複数の状態の可能性がある）または、メンバーの移動はせず農夫だけが左岸に移る。さらに、filter available 関数で禁止状態のない状態を選び出す。戻り値は可能な状態のリストだ。 | farmer s == LeftSide = updateLeft s | otherwise = updateRight s 次の一手をさがす。農夫が左岸にいれば、左岸を更新し、右岸にいれば右岸を更新する。 search s path | goal s = [reverse (s:path)] | otherwise = concatMap (\x -> search x (s:path)) [x | x <- findNext s, (not $ elem x path)] 移動の手順を探す。s には現在の状態が、path にはそれまでの状態のリストが束縛される。プログラムのなかで唯一技巧的なプログラム。seach s だけの再帰関数にしても良いのだが、search s path という末尾再帰関数にしてある。理由は not $ elem x path のように、選んだ状態が、過去の状態と重複しないようにするために、過去の状態のリストを参照するからだ。そうしないと、search s path 関数が巡回してプログラムが停止しなくなる。 goal s は search s path の base case で State の left == [] のときの base case だ。 [x | x <- findNext s, (not $ elem x path)] で次に来る状態のうち、過去の状態のリスト path に含まれていないものを選び出す。さらに、このリストに含まれる次の一手となる状態について再帰的に search s (s:path) を繰り返す。このとき path は s:path に更新されて新しい状態を含んだ path になっている。search s path :: State -> [State] -> [[State]] だから、map (\x -> search x (s:path) main = mapM_ (\x -> (mapM_ print x >> putStr "\n")) $ search beginState [] main 関数は beginState を出発点に search s path を適用してできた [[State]] 型の発見された状態のリストを端末に出力するだけ。 このプログラムには if ~ then ~ else ~ の制御構造は全く無い。現実の問題に対し、代数的データの定義から始めて自然にコード化しているうちに実行可能なプログラムになった。また、プログラムのパーツは、作るたびに動作確認ができるような仕組みになっている。Haskellの真骨頂は、このようなパターン処理によるプログラミングができることではないだろうか。
#
by tnomura9
| 2019-06-22 16:21
| Haskell
|
Comments(0)
Pasec 関連の記事が溜まったので『Parsec 入門』として記事リストを作ってみた。 最初の７つの記事はモナドを ghci のコマンドライン上で扱って実験するための予備知識だ。Parsec はパーサにモナドを使うので、モナドの扱い方を知っておく必要があるからだ。 Text.Parsec.Char 以下の記事は Hackage の parsec: Monadic parser combinators に記述されている parsec の機能を網羅する形で実験したものだ。最後の2つの記事は、他のサイトの記事を参考に、Parsec の最終の目的である、文のパースと構文木の作成について調査している。 もちろん、この記事リストだけでは不十分であるが、Parsec でやれることの概要はほぼ調べたつもりだ。 #
by tnomura9
| 2019-06-20 18:17
| Haskell 記事リスト
|
Comments(0)
Parsec で構文木を作るやり方について、次の記事が分かりやすかった。 Parsec を利用してプログラムをパースして構文木を作る手順については、次のようにまとめることができるだろう。 １．プログラム言語の文法（BNF記法など）を元に、構文木のノードとなる代数的データ型を定義する。 ＊ 定型的に Term, Expr, Stmt 型を考えるとよいようだ。 ２．字句解析パーサを作る。 ＊ makeTokenParser （Text.Parsec.Token モジュール）を使う。設定レコードは Text.Parsec.Lnguage モジュールのemptyDef などをカスタマイズして使う。 ３．字句解析パーサを元に項 term 解析パーサを作る。このときパーサの戻り値は対応する代数的データ型とする（Expr 型）。 ＊ buildExpressionParser （Text.Parsec.Expr モジュール）を使う。 ５．expression パーサを元に文 statement パーサを作る。パーサの戻り値は Stmt 型。 ＊ パーサの解析方法を再帰下降型にすることにより、特に構文木のマージなどを意識しなくても自然に構文木が形成される。 プログラムのソースから構文木を作成するまでの手順は、Parsec を使うと定型的にできるような気がする。あとは、どういう構文木を設計するかという問題だけが残る。 色々なデータの処理プログラムを作っても、実際にはそれらを組み合わせて使いたい場合が多い。自分用のプログラム言語とまではいかなくても、コンソールから処理の組み合わせを指示できたら便利だ。構文解析のプログラムを収集して習熟すれば、役立つ領域は広いだろう。構文解析のアルゴリズム自体は定型的なようで、後は、実験を繰り返して慣れることが必要だ。
#
by tnomura9
| 2019-06-20 07:32
| Haskell
|
Comments(0)
項 term のパーサ、式 expression のパーサが作れるようになったので、残りは文 statement のパーサだ。用例を探していたら、 という記事を見つけたので、そこのプログラム例を実行してみた。アイディアとしては、式の代数的データ型 Expr と単項演算の代数的データ型 Unop 、２項演算の代数的データ型 Duop 、文の代数的データ型 Stmt を作り、パーサによるパースの段階で、データをそれぞれの枠組みに割り当てていくという感じだった。 文のパーサを再帰下降型でプログラムすることで、その都度行われる処理が、自然に構文木を作るようになる。パターンマッチで自然に構文木が作られていくのが面白かった。 自分用のプログラム言語を作るための最後の関門である構文木の作成は、代数的データ型の利用で直感的に行うことができるようだ。 実行例 Prelude> :l stmt.hs [1 of 1] Compiling Statement ( stmt.hs, interpreted ) Ok, modules loaded: Statement. *Statement> play "a := true" Seq ["a" := Con True] *Statement> play "if a = b then c := true else c := false fi" Seq [If (Duo Iff (Var "a") (Var "b")) (Seq ["c" := Con True]) (Seq ["c" := Con False])] *Statement> play "a := true; b := a" Seq ["a" := Con True,"b" := Var "a"] ファイル名：stmt.hs （行頭のアンダースコアはスペースで置き換え） module Statement where import Text.Parsec import Text.Parsec.String import Text.Parsec.Expr import Text.Parsec.Token import Text.Parsec.Language (emptyDef) data Expr = Var String | Con Bool | Uno Unop Expr | Duo Duop Expr Expr __ deriving Show data Unop = Not deriving Show data Duop = And | Iff deriving Show data Stmt = Nop | String := Expr | If Expr Stmt Stmt | While Expr Stmt | Seq [Stmt] __ deriving Show def :: LanguageDef st def = emptyDef { __ commentStart = "{-" __ , commentEnd = "-}" __ , identStart = letter __ , identLetter = alphaNum __ , opStart = oneOf "~&=:" __ , opLetter = oneOf "~&=:" __ , reservedOpNames = ["~", "&", "=", ":="] __ , reservedNames = ["true", "false", "nop", "if", "then", "else", "fi", "while", "do", "od"] } lexer = makeTokenParser def m_parens = parens lexer m_identifier = identifier lexer m_reservedOp = reservedOp lexer m_reserved = reserved lexer m_semiSep1 = semiSep1 lexer
m_whiteSpace = whiteSpace lexer exprparser :: Parser Expr exprparser = buildExpressionParser table term <?> "expression" table = [ __ [ Prefix (m_reservedOp "-" >> return (Uno Not))] __ , [Infix (m_reservedOp "&" >> return (Duo And)) AssocLeft] __ , [Infix (m_reservedOp "=" >> return (Duo Iff)) AssocLeft] __ ] term = m_parens exprparser __ <|> fmap Var m_identifier __ <|> (m_reserved "true" >> return (Con True)) __ <|> (m_reserved "false" >> return (Con False)) mainparser :: Parser Stmt mainparser = m_whiteSpace >> stmtparser <* eof __ where ____ stmtparser :: Parser Stmt ____ stmtparser = fmap Seq (m_semiSep1 stmt1) ____ stmt1 = (m_reserved "nop" >> return Nop) ______ <|> do { v <- m_identifier; m_reservedOp ":="; e <- exprparser; return (v := e) } ______ <|> do { m_reserved "if" ; b <- exprparser ; m_reserved "then" ; p <- stmtparser ; m_reserved "else" ; q <- stmtparser ; m_reserved "fi" ; return (If b p q) } ______ <|> do { m_reserved "while" ; b <- exprparser ; m_reserved "do" ; p <- stmtparser ; m_reserved "od" ; return (While b p) } play :: String -> IO () play inp = case parse mainparser "" inp of __ Left err -> print err __ Right ans -> print ans #
by tnomura9
| 2019-06-20 00:15
| Haskell
|
Comments(0)
データコンストラクタに := という演算子風の書き方をするものがある。演算子ではなくあくまでもデータコンストラクタだ。使い方は次のようになる。 Prelude> data Example = String := Int deriving Show Prelude> "hello" := 7 "hello" := 7 := が中置演算子のように見えるが、これはデータコンストラクタだ。次のように前置型にすれば分かりやすいかもしれない。 Prelude> (:=) "world" 6 "world" := 6 := はあくまでもデータコンストラクタなので、"world" に 6 を束縛したりはできない。変数に束縛してもそれはフィールドに "world" と 6 を持つ Example 型のデータと言うことになる。 Prelude> a = "world" := 6 Prelude> a "world" := 6 Prelude> :t a a :: Example したがって、データ a から 6 を取り出すためには次のような value 関数を使ってパターン認識で取り出す必要がある。 Prelude> value (_ := x) = x Prelude> value a 6 ややこしい := データコンストラクタだが、次の記事のための伏線だ。 #
by tnomura9
| 2019-06-19 18:19
| Haskell
|
Comments(0)
Text.Parsec.Expr モジュールの buildEpressionParser を使うと、式 (expression) のパーサを自動的に作成できる。 手順としては、先ず makeTokenParser 関数で必要なトークンパーサを作する。次に項 (term) の定義を行う。そのあとで、演算を定義するテーブルを作成する。テーブルの prefix, postfix, bainary などはユーザが定義する関数だ。最後にそのテーブルと項を引数に式のパーサを作成することになる。 以下に実際に動作確認したプログラムを示す。このプログラムは色々な式のパーサの作成の雛形に利用できる。（アンダースコアは空白に置き換える） 実行例： Prelude> :l expr.hs [1 of 1] Compiling Expression ( expr.hs, interpreted ) *Expression> parseTest expr "2++" 3 *Expression> parseTest expr "-2 + 3" 1 *Expression> parseTest expr "(1 + 2) * (3 + 4)" 21 ファイル名：expr.hs module Expression where import Text.Parsec import qualified Text.Parsec.Token as P import Text.Parsec.Language (emptyDef) import Text.Parsec.Expr lexer = P.makeTokenParser emptyDef natural = P.natural lexer parens = P.parens lexer reservedOp = P.reservedOp lexer expr = buildExpressionParser table term <?> "expression" term = parens expr <|> natural <?> "simple expression" table = [ [prefix "-" negate, prefix "+" id] _____ , [postfix "++" (+1)] _____ , [binary "*" (*) AssocLeft, binary "/" (div) AssocLeft] _____ , [binary "+" (+) AssocLeft, binary "-" (-) AssocLeft] _____ ] binary name fun assoc = Infix (reservedOp name >> return fun) assoc prefix name fun = Prefix (reservedOp name >> return fun) postfix name fun = Postfix (reservedOp name >> return fun) パーサのプログラムは理解するのは難しいが、定型的になるので、参考になるプログラムがあれば、改造して利用することが可能だろう。問題はその参考プログラムをどこから探すかということだ。ちなみに、上のプログラムは Hackage の Text.Parsec.Expr に例示されていたものだ。
#
by tnomura9
| 2019-06-19 06:15
| Haskell
|
Comments(0)
makeTokenParser でトークンパーサを自動作成するときのユーザ設定は、GenLanguageDef を設定することでおこなう。それもスクラッチで作る必要はなく、myDef = emptyDef {commentStart = "/*", commentEnd = "*/" } のように、デフォールトのファイルを使って、フィールド名を指定して設定することができる。なぜこのようなことができるのだろうか。 デフォールトの設定レコードを再利用するテクニックは、代数的データ型のフィールドラベル付きフィールドを活用することで実行できる。 Haskell の フィールドラベルをもつ代数的データ型は、フィールドラベルを指定することでデータを取り出したり、変更したりすることができる。そこで、次のような簡単な代数的データ型を作って実験してみた。 Prelude> data Foo = Foo {foo :: String, bar :: String} deriving Show Foo 型のデータは次のようにフィールドラベルなしでも、フィールドラベルを使っても作ることができる。 Prelude> Foo "hello" "world" Foo {foo = "hello", bar = "world"} Prelude> Foo {bar = "world", foo = "hello"} Foo {foo = "hello", bar = "world"} また、元あるデータの一部分を変更した新しいデータを作ることもできる。 Prelude> hello = Foo "hello" "world" Prelude> hello Foo {foo = "hello", bar = "world"} Prelude> howdy = hello {foo = "howdy"} Prelude> howdy Foo {foo = "howdy", bar = "world"} このようなフィールドラベル付きの代数的データ型を利用して、ユーザ設定のカスタムレコードを次のように作ることができる。 Prelude> import Text.Parsec Prelude Text.Parsec> import Text.Parsec.Token Prelude Text.Parsec Text.Parsec.Token> import Text.Parsec.Language Prelude Text.Parsec Text.Parsec.Token Text.Parsec.Language> myDef = emptyDef {commentStart = "/*", commentEnd = "*/"} Prelude Text.Parsec Text.Parsec.Token Text.Parsec.Language> lexer = makeTokenParser myDef Prelude Text.Parsec Text.Parsec.Token Text.Parsec.Language> parseTest (whiteSpace lexer >> string "hello") "/* any comment */ hello" "hello" commentStart と commentEnd を設定するだけでコメント部分は whiteSpace として読み飛ばしてくれる。
#
by tnomura9
| 2019-06-18 08:13
| Haskell
|
Comments(0)
|
カテゴリ
主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude 圏論 ボーカロイド jQuery デモ Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
