f#入門の方向性
F#入門のサイトについて、そこそこ人が見に来てくれているのに
古い情報を放置してるのは良くないかもしれないと思い
わりと最近更新は再開したわけですが
今となっては日本語で読めるMSDNのリファレンスもあるし
これは推測だけれども
F#に興味を持つ人は、プログラミング経験者が多い気がするので
若干、サイトの存在意義的なものを見失い気味です。
ユーザ視点では、.netライブラリの使い方を充実させるとかのほうが
良いのかもしれないなとか思ったり。
内容についても、改めて見直すと変な所は多いし
間違ったところや知識が曖昧なことを結構言い切ってしまってて
結構凹んでいます。
更新では出来るだけ情報元を出すように気をつけてますが
一方で冗長になりすぎやしないかとも。
それから、文章を書く心構え的なものとして
数学ガールなどはじめ、色々な書籍を書かれてる
結城浩さんのtweetで
「陥りがちな誤りは、「自分が知っていることを全部書こうとする」という誤り」
Twitterでたくさんふぁぼられた結城のツイート
っていう言葉を最近知り、
これは、もっと気をつけたいと思いました。
入門サイト的な意味では
本を全て公開し、さらに内容全てに対して
ユーザからのコメントが付けられるようになっている
Real World Haskellは素晴らしいなって思います。
こういうのはWeb2.0って言うんでしょうか(Web2.0がどういう意味かは知らないわけですが)
その他最近気になったもの
・日銀砲
・最近のJavaScriptはすごい→(JavaScriptで比較的本気でお絵描きアプリを作ってみた)
・ハイボールラーメン
復帰
久しぶりの更新、
未熟でずぼらでマイペースな人間ですが、
そこそこ元気にはしてます。
気づいたらF#は2.0が出ていて
しかもすでに半年は経過していた！状態です。
今は、F#入門のサイトメンテのために
仕様書をちょこちょこと読んでいます。
どうやら、過去の版の仕様書はレアアイテムになってしまってるみたい。それはちょっと困る・・
F#入門は先日リニューアルしたのですが
旧サイトから新サイトへのリンクが一つもないという
アホなことをやらかしてたので、旧サイトも更新しました。
新サイトでは、BBSとブログと2個あるよりも
1個にしてしまおうかなとか思ってますがまだ決めてません。
それと、F#のUser Groupが出来てたので
こっそり参加してきました。(プロい人が一杯いるに違いない！)
内向的な人間なのでおろおろしていますが
とりあえず、翻訳向上委員会で提案されている訳語は
サイトのほうで反映していこうと思ってます。
パターンマッチング→パターンマッチは既に反映しました。
こんな感じで、自分に出来る範囲で協力していこうと思います。
最後にネタ。MSDNをうろうろしてたら、こんな記事がありました。
タイトルからして素晴らしく、マイクロソフトの層の厚さを感じますね。
誰が書いたんだろう、こんなの？
MSDN:デバッギングはゲシュタルト
「バグは最高です」から始まるMSDNの記事。
「無口で内向的な人ほど、デバッグ中に、異様と思えるほどの感情的な行動に出ます」
とか、節々にすごい言い回しが出てきます。
休息
体調不良にて、静養することになりました。
そのため、しばらくの間、更新はお休みします。
F# 50行で書くパーサコンビネータ
グラフ理論は速攻で三日坊主になってしまったけれども、
ネタができたのでかなり久しぶりに更新してみる。
まず最初に、今回作成したプログラムはあくまで勉強用のものなので
真面目にパーサを書きたい人はFParsec
を使うほうが100万倍良いとおもいます。
というわけで、タイトルにもあるとおり、
最小限の機能だけを詰め込んだパーサコンビネータをF#で書いてみた。理論の知識は適当なので、用語とか変なところがあったら聞き流してください(それでいいのか
なお、以下のプログラムは、変数名に日本語の文字列を使っているので
試す場合はUTF-8で保存が必要です(あるいはパーサ名だけアルファベットに変えてください)
→設定法
#light "off" //文字列の範囲チェック let check1 (str:string) p = if p < str.Length then true else false;; let check2 (str:string) p = if p <= str.Length then true else false;; //1文字を認識するパーサ。predが真となるときマッチなのでnot述語もこれで記述 //基本的なパーサの作成はこの関数でしか行わない let genp pred (str:string) (p:int) = if check1 str p then if pred str.[p] then (true,p,p+1) else (false,p,p) else (false,p,-1);; //選択e1/e2に相当するパーサコンビネータ。F#には|,||, ||| まで定義されてるのでこんな名前に・・ let (||||) pa pb (str:string) (p:int) = let (result,ps,pe) = pa str p in if result then (true,p,pe) else let (resultb,psb,peb) = pb str p in if resultb then (true,p,peb) else (false,p,p);; //並びe1 e2に相当するパーサコンビネータ。選択にあわせてこんな名前に・・ let (>>>>) pa pb (str:string) p = let (result,ps,pe) = pa str p in if result then let (resultb,psb,peb) = pb str pe in if resultb then (true,p,peb) else (false,p,p) else (false,p,p);; //ゼロ個以上の繰り返しに相当するパーサコンビネータ。もっとすっきり書けないかな let many pa (str:string) p = let rec aux pa str (lastresult,rs,re) = let (result,ps,pe) = pa str re in if result then aux pa str (result,ps,pe) else (lastresult,rs,re) in let (result,ps,pe) as r = pa str p in if result then let (_,_,re) = aux pa str r in (true,p,re) else if check2 str p then (true,p,p) else (false,p,-1);; //1個以上の繰り返しに相当するパーサコンビネータ let many1 pa (str:string) p= pa >>>> (many pa);; //省略可能に相当するパーサコンビネータ let option pa (str:string) p = let (result,ps,pe) as r = pa str p in if result then r else if check2 str p then (true,p,p)else (false,p,-1);; //↑パーサはここまで //実際にパースしてみる //パース対象文字列とパーサの結果を取り、表示する関数 let print_match (str:string) (_,s,e) = str.Substring(s,e-s) |> print_any;; let csv_parser = let 改行 = genp ((=)'\n') in let カンマ = genp ((=)',') in let スペース = genp ((=) ' ') in let タブ = genp ((=) '\t') in let ダブルクォート = genp ((=)'"') in let ダブルクォート以外の文字 = genp ((<>)'"') in let 空白文字 = many (スペース |||| タブ) in let カンマダブルクォート改行以外の文字 = genp (fun x -> (x<>'\n')&&(x<>',')&&(x<>'"')) in let ダブルクォート2個 = ダブルクォート >>>> ダブルクォート in let クォート文字列 = many (ダブルクォート以外の文字 |||| ダブルクォート2個) in let ただの文字列 = many カンマダブルクォート改行以外の文字 in let CSVの値 = (空白文字 >>>> ダブルクォート >>>> クォート文字列 >>>> ダブルクォート >>>> 空白文字) |||| ただの文字列 in let CSVの行 = CSVの値 >>>> (many (カンマ >>>> CSVの値)) >>>> 改行 in many CSVの行;; let str = "comma,separated,value\nlotsofcomma,,,,,,,,,newlines\n\n\nthis line don't have eol" in printfn "#####input#####"; print_any str;printfn ""; printfn "#####output##########"; let matched = csv_parser str 0 in matched |> print_match str;printfn ""; printf "matched " |> ignore;print_any matched|>ignore; printfn "";;
このパーサは出来るだけ長くマッチした部分が返ってくる。
最後に改行がない場合はCSVとは見なされない定義になってるので
マッチ結果は途中までとなっている。
なお、CSVの定義については
このサイトを参考にさせて頂きました。
以下、超かいつまんだプログラムの説明
パーサの型(string -> int -> bool * int * int)
パーサ対象は文字列限定
入力：パース対象文字列->対象文字列のパース開始位置
出力：(パースが成功したか、パースを始めた位置、パースを終えた位置)
パーサ
条件が真となるときに1文字読み込むパーサだけ定義。
後は全てパーサを合成して使用する
パーサコンビネータ
選択：2つのパーサが両方真なら真。さもなくば偽
並び：2つのパーサのどちらかが真なら真。さもなくば偽。
繰り返し：与えられたパーサが真の間いけるところまでいって真を返す。
Greedyに動作するので、動作途中の位置からのバックトラックはない、はず。
おそらく、PEGと同じ動作だと思う
さらなる拡張に向けて
比較的簡単な拡張
1．文字を消費せず先読みするパーサの追加
2．文字列リテラルを直接与えられるパーサの追加(合成するだけ)
3．与えられた文字列全体がマッチしたかどうかの判定
パース成功=「入力文字の長さとマッチ結果のパースを終えた位置が等しいか」で判定する
4．パーサに引数を追加し、一つ前にマッチしたパース結果を持たせる
→これで構文木みたいなのが作れるので、
後は構文木を処理するプログラムを書けばマイプログラミング言語が完成？
5．パースに対応するアクションを実行出来るようにする(パーサの引数を増やす)
ただ、バックトラック対応を考えると
構文木を作ってからそれに対してアクションを設定するほうが楽かも
頑張る拡張
1.スキップパーサの作成と、一時的にスキップパーサをOFFにする構文の追加(Boost.spiritにあるやつ)
2.左再帰への対応(HaskellのParsecにはchainlというのがあるらしい。どうやるんだろう？)
3.動的計画法を使ってPackrat Parser？に変える(同じ位置に対するあるパーサの読み込みは1回だけにする)
4.Monadic Parserにする(Computation Expressionの利用)
以上、CSVパーサも入っているのでソース全体は80行弱だけど
パーサ部分は50行に収まりました。
Kruskal法
今回はクラスカル法(Kruskal法)のプログラムに挑戦したのだが、Prim法に比べてプログラム作成には苦戦した。Kruskal法はPrim法と同じく最小全域木(MST)を求めるためのアルゴリズムで、Prim法と異なり、グラフが連結でない場合にも利用出来る。しかし、今回のプログラムでは連結でないグラフは考慮していない。
最初、wikiの例を見てアルゴリズムの動作を確認していたのだが、新しく辺を追加して、頂点が同じ木に所属するとなった際の動作が自分にはどうもわからない。(疑似コードとかついてるけど読む気になれない)
そこで、Google頼りにさらに調査を続けた結果、どうやらUnion-Findなるデータ構造を使えば木と辺の統合を効率的に記述出来るらしいことが判明。Union-Findの実装にはこのページを参考にさせてもらった。Union-Findの実装が済むとKruscal法の実装はすぐ出来た。
胆になる部分は、「コストが小さい辺から順に、木に統合出来る場合は結果の辺リストに加える」という操作で、プログラムでは以下の部分に相当。木に統合できるかどうか、という部分でUnion-Findを使っている。
for i in adj do let (f,t,c) = i in if uf.union f t then edges.Add(i) done;;
以下、今回作成したコード
#light "off" open Microsoft.FSharp.Collections;; let pe x = print_any x;print_endline "";; //Kruskal法(Union-Findを利用) //Union-Findクラス type UnionFind = class val data : ResizeArray<int> new (size:int) as x = {data = new ResizeArray<int>(size)} then //-1で初期化 for i=1 to size do x.data.Add(-1) done member private x.root n = let rec aux n = //経路圧縮なし //if x.data.[n] < 0 then n else aux (x.data.[n]) //経路圧縮あり if x.data.[n] < 0 then n else begin x.data.[n] <- aux (x.data.[n]);x.data.[n] end in aux n member x.find a b = x.root(a) = x.root(b) member x.union a b = let src = x.root(a) in let dst = x.root(b) in if src < dst then begin x.data.[src] <- x.data.[src] + x.data.[dst]; x.data.[dst] <- src; end else if src > dst then begin x.data.[dst] <- x.data.[src] + x.data.[dst]; x.data.[src] <- dst; end; src <> dst end;; //ノード数 let nodenum = 6;; //辺リスト let adj = [|(0,1,5);(0,2,4);(0,3,2);(1,2,2);(1,4,6);(2,3,3);(2,5,2);(3,5,6);(4,5,4)|];; //辺の重みの小さい順にソート let sorter a b = let ((_,_,l),(_,_,r))=(a,b) in if l>r then 1 else if l<r then -1 else 0 in Array.sort sorter adj;; let uf = new UnionFind(nodenum);; //結果を入れる辺リスト let edges = new ResizeArray<int*int*int>();; //辺の重みの小さい順に処理 for i in adj do let (f,t,c) = i in if uf.union f t then edges.Add(i) done;; for i in edges do pe i done; //↑ここまでのプログラムでも動作する //以下前回と同じ open Microsoft.FSharp.Core;; open System;; open System.Windows.Forms;; open System.Drawing;; //要素数と(始点、終点、コスト)の配列を受け取り、そのグラフを表示するクラス type Graph = class inherit Form val pbox : PictureBox val pos : (float32*float32) array //各ノードのx,y座標 val circle_width : float32 //1つのノードの幅 val circle_height : float32 //1つのノードの高さ new (pnum:int,adj) as this = {pbox = new PictureBox(); pos=Array.init pnum (fun x -> (0.f,0.f)); circle_width = 50.f; circle_height = 50.f;} then let (whole_width,whole_height)=(800,600) in this.Width <- whole_width; this.Height <- whole_height; let (screen_width,screen_height)=(this.ClientRectangle.Width,this.ClientRectangle.Height) in this.pbox.Dock <- DockStyle.Fill; this.Controls.Add(this.pbox); this.pbox.Image <- new Bitmap(screen_width,screen_height); //画面中央の計算 let (cx,cy)=((Float32.of_int screen_width)/2.f,(Float32.of_int screen_height)/2.f) in //各ノードの座標計算 for i=0 to pnum-1 do let dist = 200.f in let (dx,dy)= (cx+dist*Float32.of_float(Math.Cos(2.*Math.PI/(Float.of_int pnum)*(Float.of_int i))), cy+dist*Float32.of_float(Math.Sin(2.*Math.PI/(Float.of_int pnum)*(Float.of_int i)))) in this.pos.[i]<-(dx,dy); done; //ノードを描く Array.mapi (fun i x -> this.circle (fst x) (snd x) (i.ToString())) this.pos |> ignore; //ノード間の接続とコストを描く for i in adj do let (s,e,c) = i in this.line (fst this.pos.[s]) (snd this.pos.[s]) (fst this.pos.[e]) (snd this.pos.[e]) (Float32.of_int c) done //円とラベルを指定座標に描く member this.circle (x:float32) (y:float32) label = use g = System.Drawing.Graphics.FromImage(this.pbox.Image) in let w,h = (this.circle_width,this.circle_height) in g.DrawEllipse(Drawing.Pens.Black,x,y,w,h); let font = new Font("MS UI Gothic",18.f) in let size = g.MeasureString(label,font,768,new StringFormat()) in g.DrawString(label,font,Brushes.Black,x+w/2.f-size.Width/2.f,y+h/2.f-size.Height/2.f); //線を指定座標から指定座標へ描き、間にコストを描く member this.line (sx:float32) (sy:float32) (ex:float32) (ey:float32) c= use g = System.Drawing.Graphics.FromImage(this.pbox.Image) in let (dx,dy) = (this.circle_width/2.f,this.circle_height/2.f) in let font = new Font("MS UI Gothic",12.f) in let (nsx,nsy,nex,ney) = (sx+dx,sy+dy,ex+dx,ey+dy) in g.DrawLine(Pens.Black,nsx,nsy,nex,ney); //線を1:2に内分する点にコストを描く g.DrawString(c.ToString(),font,Brushes.Black,(nsx+2.f*nex)/3.f,(nsy+2.f*ney)/3.f); end;; [<STAThread>] do System.Windows.Forms.Application.Run(new Graph(6,edges));;
Prim法
特にテーマもなくBlogを初めたので、しばらくはグラフ理論のアルゴリズムに関するプログラムをF#を使って書いていくことにしてみようと思う。今回はPrim法で、入力データは前回と同じもの。グラフが与えられた時に、全ての点を通り、コストの総和が最小になるよう辺を選び取るアルゴリズムになります。
ところで、自分は、プログラムを作る際には、効率よりも「解けるプログラムを作ること」と、(自分にとって)理解しやすいこと、のほうを重視している。PerlやRubyなんかのLightweightな言語がはやってるように、とりあえず「出来る」だけで有用な場面のほうが多い気がするし、効率を気にして時間をかけてプログラムに四苦八苦するよりも、とりあえず出来たほうがなんか楽しい、というのが大きい。
という(いい)わけで、Prim法の実装にあたってResizeArray使った「手抜きPriority Queue」を実装してみた。本来ならヒープを使ってPriority Queueを実装するほうが効率もよいし本格的だが、そこは後で置き換えれば良いので、Prim法を解くことから入ってみる。
#light "off" open Microsoft.FSharp.Collections;; //プリム法 let pe x = print_any x;print_endline "";; let m = Int32.max_int;; let nodenum = 6;; //辺リスト let adj = [|(0,1,5);(0,2,4);(0,3,2);(1,2,2);(1,4,6);(2,3,3);(2,5,2);(3,5,6);(4,5,4)|];; //簡易プライオリティキュー type easy_pq<'T> = class val private array : ResizeArray<'T> val private sorter : 'T -> 'T -> int new (sortfunc,(ar : 'T array)) = {array = new ResizeArray<'T>(ar);sorter=sortfunc} new (sortfunc) = {array = new ResizeArray<'T>();sorter=sortfunc} member x.push v = x.array.Add(v);ResizeArray.sort x.sorter x.array member x.pop _ = let r = x.array.[0] in x.array.Remove(r)|>ignore;r member x.show f = Seq.iter f x.array end;; let mst = new ResizeArray<int>();; let edges = new ResizeArray<int*int*int>();; //MSTの初期値としてノード0を指定 mst.Add(0);; //MSTへ一つノードを追加し、edgesへ追加した辺を格納する let update mst edges adj= let sorter a b = let ((_,_,l),(_,_,r))=(a,b) in if l>r then 1 else if l<r then -1 else 0 in let pq = new easy_pq<int*int*int>(sorter) in //次の辺を見つけるためキューにデータを入れる for i in mst do Array.map (fun x -> let (f,t,c)=x in if f=i || t=i then pq.push x ) adj |> ignore done; //mstにないノードが見つかるまでキューからPOP let rec update_aux mst (edges:ResizeArray<int*int*int>) adj (pq:easy_pq<int*int*int>)= let nextedge = pq.pop() in let (f,t,c) = nextedge in if not (ResizeArray.exists ((=)t) mst) then begin mst.Add(t);edges.Add(nextedge) end else if not(ResizeArray.exists ((=)f) mst) then begin mst.Add(f);edges.Add(nextedge) end else update_aux mst edges adj pq in update_aux mst edges adj pq;; //最初に1個入れているのでノード数-1回MSTのアップデートを繰り返す for i=0 to nodenum-2 do update mst edges adj done;; ResizeArray.iter pe edges;;
出力結果は、辺のリスト。これは、前に作ったグラフを可視化するプログラムにそのまま入力出来るので、次のプログラムで最小全域木がどうなってるか確認出来る。なお、今回のupdate関数は副作用ありな関数になっている。
#light "off" open Microsoft.FSharp.Collections;; open Microsoft.FSharp.Core;; open System;; open System.Windows.Forms;; open System.Drawing;; //プリム法 let pe x = print_any x;print_endline "";; let m = Int32.max_int;; let nodenum = 6;; //辺リスト let adj = [|(0,1,5);(0,2,4);(0,3,2);(1,2,2);(1,4,6);(2,3,3);(2,5,2);(3,5,6);(4,5,4)|];; //簡易プライオリティキュー type easy_pq<'T> = class val private array : ResizeArray<'T> val private sorter : 'T -> 'T -> int new (sortfunc,(ar : 'T array)) = {array = new ResizeArray<'T>(ar);sorter=sortfunc} new (sortfunc) = {array = new ResizeArray<'T>();sorter=sortfunc} member x.push v = x.array.Add(v);ResizeArray.sort x.sorter x.array member x.pop _ = let r = x.array.[0] in x.array.Remove(r)|>ignore;r member x.show f = Seq.iter f x.array end;; let mst = new ResizeArray<int>();; let edges = new ResizeArray<int*int*int>();; //MSTの初期値としてノード0を指定 mst.Add(0);; //MSTへ一つノードを追加し、edgesへ追加した辺を格納する let update mst edges adj= let sorter a b = let ((_,_,l),(_,_,r))=(a,b) in if l>r then 1 else if l<r then -1 else 0 in let pq = new easy_pq<int*int*int>(sorter) in //次の辺を見つけるためキューにデータを入れる for i in mst do Array.map (fun x -> let (f,t,c)=x in if f=i || t=i then pq.push x ) adj |> ignore done; //mstにないノードが見つかるまでキューからPOP let rec update_aux mst (edges:ResizeArray<int*int*int>) adj (pq:easy_pq<int*int*int>)= let nextedge = pq.pop() in let (f,t,c) = nextedge in if not (ResizeArray.exists ((=)t) mst) then begin mst.Add(t);edges.Add(nextedge) end else if not(ResizeArray.exists ((=)f) mst) then begin mst.Add(f);edges.Add(nextedge) end else update_aux mst edges adj pq in update_aux mst edges adj pq;; //最初に1個入れているのでノード数-1回MSTのアップデートを繰り返す for i=0 to nodenum-2 do update mst edges adj done;; ResizeArray.iter pe edges;; //要素数と(始点、終点、コスト)の配列を受け取り、そのグラフを表示するクラス type Graph = class inherit Form val pbox : PictureBox val pos : (float32*float32) array //各ノードのx,y座標 val circle_width : float32 //1つのノードの幅 val circle_height : float32 //1つのノードの高さ new (pnum:int,adj) as this = {pbox = new PictureBox(); pos=Array.init pnum (fun x -> (0.f,0.f)); circle_width = 50.f; circle_height = 50.f;} then let (whole_width,whole_height)=(800,600) in this.Width <- whole_width; this.Height <- whole_height; let (screen_width,screen_height)=(this.ClientRectangle.Width,this.ClientRectangle.Height) in this.pbox.Dock <- DockStyle.Fill; this.Controls.Add(this.pbox); this.pbox.Image <- new Bitmap(screen_width,screen_height); //画面中央の計算 let (cx,cy)=((Float32.of_int screen_width)/2.f,(Float32.of_int screen_height)/2.f) in //各ノードの座標計算 for i=0 to pnum-1 do let dist = 200.f in let (dx,dy)= (cx+dist*Float32.of_float(Math.Cos(2.*Math.PI/(Float.of_int pnum)*(Float.of_int i))), cy+dist*Float32.of_float(Math.Sin(2.*Math.PI/(Float.of_int pnum)*(Float.of_int i)))) in this.pos.[i]<-(dx,dy); done; //ノードを描く Array.mapi (fun i x -> this.circle (fst x) (snd x) (i.ToString())) this.pos |> ignore; //ノード間の接続とコストを描く for i in adj do let (s,e,c) = i in this.line (fst this.pos.[s]) (snd this.pos.[s]) (fst this.pos.[e]) (snd this.pos.[e]) (Float32.of_int c) done //円とラベルを指定座標に描く member this.circle (x:float32) (y:float32) label = use g = System.Drawing.Graphics.FromImage(this.pbox.Image) in let w,h = (this.circle_width,this.circle_height) in g.DrawEllipse(Drawing.Pens.Black,x,y,w,h); let font = new Font("MS UI Gothic",18.f) in let size = g.MeasureString(label,font,768,new StringFormat()) in g.DrawString(label,font,Brushes.Black,x+w/2.f-size.Width/2.f,y+h/2.f-size.Height/2.f); //線を指定座標から指定座標へ描き、間にコストを描く member this.line (sx:float32) (sy:float32) (ex:float32) (ey:float32) c= use g = System.Drawing.Graphics.FromImage(this.pbox.Image) in let (dx,dy) = (this.circle_width/2.f,this.circle_height/2.f) in let font = new Font("MS UI Gothic",12.f) in let (nsx,nsy,nex,ney) = (sx+dx,sy+dy,ex+dx,ey+dy) in g.DrawLine(Pens.Black,nsx,nsy,nex,ney); //線を1:2に内分する点にコストを描く g.DrawString(c.ToString(),font,Brushes.Black,(nsx+2.f*nex)/3.f,(nsy+2.f*ney)/3.f); end;; [<STAThread>] do System.Windows.Forms.Application.Run(new Graph(6,edges));;
