人気ブログランキング |

魔法陣

Haskell をつかって3×3の魔法陣を作ってみた。全自動ではなく、候補を絞っただけで結局手作業になった。

最初にマス目の合計の数を求めた。これは 1 .. 9 の総和の3分の1になる。

Prelude> sum [1..9] `div` 3
15

次に組み合わせを計算するプログラムを作成して、1 .. 9 から3個を取る組み合わせを作った。

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]]

このうち合計が15になるものを選別した。

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]]

意外と少ない。しかし、この中から3つを選び出さなければならない。これらを含まれる数字ごとにグループ分けした。

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]]

含まれる数字が同じものが4組あるのは5だけだ。魔法陣の中心にあるのは4つの和を計算しなければならないので、5がマスの中心でなければならないことが分かる。

そこで、最初の [1,5,9] を真ん中の行にすると仮定してみた。このうち 1 について見ると [1,5,9] と [1,6,8] の組み合わせしかない。1の縦方向の数字を6と8であると仮定したすると、魔法陣を次のように部分的に決定する。

6 * *
1 5 9
8 * *

6 と 5 が含まれる組み合わせは [4,5,6] だから6の対角線上の値は 4 だ。同様に 8 の対角線上の値は 2 だ。

6 * 2
1 5 9
8 * 4

6 が含まれる組み合わせをみると 2 が含まれるのは 7 だから魔法陣の1行目は 6 7 2 になる。同様に3行目は、8 3 4 だ。念の為第2列の和を取ると 7 + 5 + 3 = 15 で大丈夫だということが分かる。したがって、求める魔法陣は次のようになる。

6 7 2
1 5 9
8 3 4

ここで改めて組み合わせのヒストグラムを眺めてみると、組み合わせの数が3つなのは 2, 4, 6, 8 でこれらは正方形の頂点に来なくてはならない。また、組み合わせの数が2つなのは 1, 3, 7, 9 で、これらは正方形の辺の中央にしか置けない。

中央の数が5であるのは必然だが、その5に対して辺の数は (1, 9) と (3, 7) の組み合わせしかない。すると、魔法陣の十字の部分は必然的に決定してしまう。これは、5を中心に点対称や、線対称を作って重なる場合を考えそれらを同じものと考えると、可能性は一つしかない。そうして、真ん中の十字の部分が決定してしまうと必然的に頂点の部分も決定してしまう。したがって、3×3の魔法陣はこれ一つしかないことになる。

3×3の魔法陣はそれぞれの数字が緊密な関係を保っていて、まさに魔法陣なのだ。

# by tnomura9 | 2019-06-25 19:30 | Haskell | Comments(0)

ハノイの塔

ハノイの塔のパズルは、土台に横一列に3本の柱が並んで立っており、その柱には中心に穴の空いた円盤がさしてある。円盤は最初は左端の柱に大きい方から下から順番に棒に通して重ねてある。

パズルの目的はこの円盤を右端の柱に全て移してしまうことだ。柱の数は3本あるのでそのうちの1本は作業用として使うことができる。ただし、円盤は1回に1枚しか動かせない。また、小さい円盤の上に大きい円盤を重ねることはできない。このパズルはしかし、コンピュータのプログラムで解法を見つけることができる。

お手本のプログラムを写経して動くのを確認して見たことはあるのだが、そのアルゴリズムがもう一つよくわからなかったので Haskell で実験することにした。プログラムは何回も手直しが必要だと思われたので、ファイルに作成した。ファイル名は hanoi.hs にした。

先ず3本の棒の場所を表すデータ型 Place を作った。

module Hanoi where

data Place = A | B | C deriving Show

次に、円盤が1枚だけのパズルの解答を考えてみた。hanoi 関数は円盤の枚数と、円盤の置かれている場所 from とそれを移動する先の to と円盤を一時置いておくための場所の work を引数として、移動を表すペア、たとえば A -> C なら (A,C) のリストを戻り値とした。

円盤の移動の一番単純な形は、円盤が1枚だけのときだ。このときは、円盤は 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 の場所には何も置かれていないので使われていない。

次に円盤が2枚の場合を考えてみた。2枚めの円盤を A から C に移し、B に置いてあった1枚目の円盤を B から C に移す。この動作を hanoi 2 from to work を利用して定義すると、1枚目の板は 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) は2枚めの板を A -> C に移動させることを示しており、(B -> C) は1枚目の板を B -> C に移動させることを意味しているが、1枚目の板は最初は A にあったはずなのにいきなり B のところにあることになっている。これは実際のパズルとは違う。

しばらく考えてもわからなかったのでカンニングしたら謎が解けた。上のプログラムでは、最初に1枚目の板を 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)]

この結果なら、1枚目の板を A -> B に移し、2枚めを A -> C へ、最後に1枚めを B -> C へ移すので実際のパズルとも合致している。

そこで板が3枚の場合も考えてみた。3枚の板を移動するときに2枚の板を移動させるプログラムを活用することにする。

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)]

これは1枚めをBに置き、2枚めをCに置き、Bの1枚めをCの2枚めの上に起き、空いたBのスベースに3枚めを置き、... と読めるから実際のパズルの動きをイメージでシミュレーションしてみると正しい答えのようだ。

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枚の板を動かすには先ず (n-1) 枚の板を work へ移動させ、次にn枚目の板を from から to へ移動させる。最後に (n-1) 枚の板を work から to へ移動させるという手順そのままのプログラムだ。

再帰的プログラムをいきなり作るのはハードルが高いが、Haskell ではパターンプログラミングができるので、実際の単純な例のプログラムを最初に作ってみて、最後に統一的な再帰的定義として完成させるというような芸当ができる。パターンプログラミングの威力を感じる例だ。

# by tnomura9 | 2019-06-25 07:49 | Haskell | Comments(0)

Text.Prinf, Data.List.Split

Text.Printf モジュールと Data.List.Split モジュールを使って、リスト [1 .. 9] を3カラムの行列に分割し、桁幅5の整数フォーマットで表示してみた。

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

module Main where

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 (状態)はメンバーが3つとも左岸にいて、農夫も左岸にいる。右岸にはメンバーは誰もいない。

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 関数で禁止状態のない状態を選び出す。戻り値は可能な状態のリストだ。

findNext s
| 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)

Parsec 入門

Pasec 関連の記事が溜まったので『Parsec 入門』として記事リストを作ってみた。

最初の7つの記事はモナドを 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 で構文木を作るやり方について、次の記事が分かりやすかった。


Parsec を利用してプログラムをパースして構文木を作る手順については、次のようにまとめることができるだろう。

1.プログラム言語の文法(BNF記法など)を元に、構文木のノードとなる代数的データ型を定義する。

 * 定型的に Term, Expr, Stmt 型を考えるとよいようだ。

2.字句解析パーサを作る。
 
 * makeTokenParser (Text.Parsec.Token モジュール)を使う。設定レコードは Text.Parsec.Lnguage モジュールのemptyDef などをカスタマイズして使う。

3.字句解析パーサを元に項 term 解析パーサを作る。このときパーサの戻り値は対応する代数的データ型とする(Expr 型)。

4.項 term 解析パーサ以外に、演算定義のテーブル table を作る。さらに term パーサと演算テーブル table を元に式 expression パーサを作る。パーサの戻り値は Expr 型にする。

 * buildExpressionParser (Text.Parsec.Expr モジュール)を使う。

5.expression パーサを元に文 statement パーサを作る。パーサの戻り値は Stmt 型。

 * パーサの解析方法を再帰下降型にすることにより、特に構文木のマージなどを意識しなくても自然に構文木が形成される。

プログラムのソースから構文木を作成するまでの手順は、Parsec を使うと定型的にできるような気がする。あとは、どういう構文木を設計するかという問題だけが残る。

色々なデータの処理プログラムを作っても、実際にはそれらを組み合わせて使いたい場合が多い。自分用のプログラム言語とまではいかなくても、コンソールから処理の組み合わせを指示できたら便利だ。構文解析のプログラムを収集して習熟すれば、役立つ領域は広いだろう。構文解析のアルゴリズム自体は定型的なようで、後は、実験を繰り返して慣れることが必要だ。

# by tnomura9 | 2019-06-20 07:32 | Haskell | Comments(0)

Parsec 文のパーサ

項 term のパーサ、式 expression のパーサが作れるようになったので、残りは文 statement のパーサだ。用例を探していたら、


という記事を見つけたので、そこのプログラム例を実行してみた。アイディアとしては、式の代数的データ型 Expr と単項演算の代数的データ型 Unop 、2項演算の代数的データ型 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)

Parsec データコンストラクタ :=

データコンストラクタに := という演算子風の書き方をするものがある。演算子ではなくあくまでもデータコンストラクタだ。使い方は次のようになる。

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)

Parsec buildExpressionParser

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)

Parsec makeTokenParser ユーザ設定

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)