パーサーにかかわることについて勉強していて引っかかったのがPEG（解析表現文法）という文法です。CFG（文脈自由文法）やCSG(文脈依存文法）は生成文法、つまり文章を生成するときに使いやすい表記であるのに対し、PEGは解析、つまりパース時に使いやすい表…

id:kazu-yamamotoさんのとりとめのないパーサー談義に刺激されて パーサーのことを勉強しているところです。yamamotoさんは｢パーサーに詳しい人に答えていただけるととても嬉しい」といわれていますが、勉強がてら自分なりの答えを書いてみようと思います。 …

Scrap Your Boilerplate:A Practical Design Pattern for Generic Programmingという論文を勉強中です。以前リストの自由度で話した内容と関連しているのですが、Haskellのリストは長さは可変な代わりに要素の型が全て同一でなくてはいけなくて、タプルは要…

PyTestさんの記事を読んで考え込んでいました。取り上げられていた問題は、ディレクトリを深さ優先探索するコードなわけですが、これをpay as you goでやりたいときにはHaskellではどう書けばよいかというものです。 pay as you goで何がいいたいかというと…

昨日のポストは単なるいかさまだったわけですが、これに懲りずに、また何か展開があったら懲りずにデータ再帰についてポストしていきたいと思います。(泣)それとは別に、fixで無限リストを生成するコードが書けたのでそれについて簡単に書いておきたいと思い…

[追記：データ再帰を使ったコードを書こうと思っていたのですが、出来上がったものはデータ再帰に放っていませんでした…とほほ…/追記] また、データ再帰のことです… Recursive Monadic Bindingsの論文などを眺めていると、よく出てくるのが電子回路のサンプ…

引き続きfixのことです…昨日の文章を書いた後、しつこくRecursive Monadic Bindingsの論文を眺めていました…この論文は主にモナド関数を使ったfixの話なのですが、例のいくつかを眺めていてもfixの使い方が fix :: ((a -> a) -> a -> a) -> a -> a ではなく …

効率化の話はなんだか疲れるので、またデータ再帰の話へ脱線… id:dachs_hippoさんのfixに関する記事をボーっと読み返していてあることに気づきました…氏のサンプルのひとつは階乗の計算だったわけですが： import Data.Function g :: (Int -> Int) -> Int ->…

数独ソルバー効率化第2回です…今回も20％程度の効率化なのですが内容が面白みにかけるのでさらっと…数独では一つのマスの値が決定したときにそのマスと依存関係にあるマスの制約条件が厳しくなります。時にはそれだけで値が決定してしまうこともあるわけです…

今日はちょっとコードの効率化の話をいったんお休みして、別の話を書きたいと思います。以前に書いたControl.Arrow.loopでも実はさりげなく出ていたのですが、Haskellではletとwhere節の部分でちょっと変わったことができます。Control.Arrow.loopの定義を見…

さて、前回のプロファイルの結果で明らかになった数独ソルバーの最悪のホットスポットはexcludeという関数だったのですが、一体何をやっていたのでしょう…500万回呼び出されて250Mバイトものメモリーを消費していました…excludeは実は次のような関数でした… …

GHCではプログラムのプロファイルをとってくれる機能があります。 数独ソルバーのパ実行フォーマンスを見るのに使ってみました。GHCのマニュアルを見れば出ていることなのですが、GHCのプロファイラはいくつかモードがあって、ものによってはメモリの消費情…

ここ2-3週間、暇を見つけては数独ソルバーをHaskellで書いていました…動くもの自体ができるまではそんなにかからなかったのですが（と、一応言っておいて…）、プロファイルをとりながら高速化していくステップで色々と試行錯誤があって、自分的には「なるほ…

本業のほうが立て込んでしまって、ずいぶんと時間が空いてしまいました。えー、ここまでのHaskellの勉強の過程で、どうゆう理由でか、あるいはどこから仕入れたのかははっきりしないのですが、Haskellではメモ化が自動、兼タダで手に入ると僕は思い込んでい…

先日の記事をポストした後に思い出したようにやったことがメモ化についてネットで調べてみることでした…(はじめにやっとけば良いのに…)メモ化, Memoize, Memoizationで検索するとwww.sampou.orgとwww.haskell.org が引っかかります。こちらのほうではデータ…

僕の今までのメモ化の理解はこうです：Haskellでは値を必要となるときまで式は評価されない。(遅延評価）したがって値が必要にならない式は評価されない。そして、評価された式の値は記憶されるので式が再評価されることはない（メモ化）。さて、Debug.Trace…

こちらhttp://www.haskell.org/haskellwiki/Research_papers/Functional_pearls で"Global Variables in Haskell"という論文を発見…しかし、functional pearlsは色々とためになるものがあります…そういえば、大域変数はHaskellでは大変だったのか？まぁ、定…

以前に簡単な説明とともにWin32でウィンドウを表示するアプリのソースを載せたわけなんですが、実はそのソースのことで書きたいことがあったのです。ちゃんとウィンドウを表示してメッセージを描画するところまではちゃんとできて、さらに、細かいところを見…

こうゆう問題を考えて見ましょう。数字の入ったリストがある。そのリストの各要素をそのリストの最小値で引いた値を返す関数decWithMinを書け。つまり、decWithMin [5, 10, 20, 4, 3, 100] => [2, 7, 17, 1, 0, 97]そんなの簡単じゃんと： decWithMin ls = m…

前回までArrowの概要をザーッと流したわけなんですが、取りこぼしたことをいくつか…ArrowはWrappedArrow経由でApplicativeとFunctorのインスタンスになっているようです。まぁ、関数(->)自身がApplicativeやFunctorのインスタンスなので、関数をくるんだArro…

前回のポストに引き続き、Arrowを攻略していきたいと思います。もう一度、Arrowのクラス定義を引っ張ってきます。 class Arrow a where arr :: (b -> c) -> a b c pure :: (b -> c) -> a b c (>>>) :: a b c -> a c d -> a b d first :: a b c -> a (b, d) (…

Haskellを勉強し始めて、モナドのことを知ってちょっとしたころに名前だけ見かけて、実際どんなものなのかを知りたいと思っていたのがArrowです。こちらhttp://www.haskell.org/arrows/で見つけられるような説明を読んだりしたのですが、もう、半年ぐらいち…

先日はMonoidとFunctorのことで玉砕してしまいました。色々教えていただいたので、ここらが攻め時ということで、もう一押しです。Monad, Monoid, Functor, Applicativeなどを見ていていつもこんがらがっちゃうのが、それらが一体何のサブクラスなのかという…

[追記：おかしいところについて]用語の混乱があったり、勉強不足があったりで、間違ったことを書いてあります。まず、functorなんですが、これは圏論での関手が英語圏ではfunctorと呼ばれていたり、C++などで使われるファンクターというものがあったり、さら…

Haskellにもclassがあるのだから、C++とかで見るオブジェクト指向もできるでしょうということで、無理やりやってみました...笑って見過ごしてやってください。一応、クラスの継承関係もできるので、ここではObject -> Animal -> (Dog, Cat)という構図になっ…

えー、いまさら何をやってんだという声も聞こえてきそうですが、普段Win32を使うことがとても多いので、Haskellで簡単なWin32のアプリを書いてみました。ちょっと長めなサンプルなので、コードは最後につけときます。Win32でウィンドウを表示する基本的なプ…

C++にあってCにないものの一つ、クラスのコンストラクタとデストラクタがあります。これを使えば、スマートポインターなどといった、リソース管理を半自動化することができるような便利なクラスを定義できるようになるわけです。プログラムを書いていると、…

きっかけは、こんな雰囲気のコードでした： main = do args もうちょっとましな書き方はあるだろうという話はここでは触れないことにして、これは、コンパイルしないわけです。エラーは：do.hs:10:12: Not in scope: `args'つまり、最後の行(x:y:_)=argsで使…

重複、省略のない順列を返す関数を書いてみました。なんだか、もっと簡単にかけそうな気がするのですが、さっぱりといきません…Preludeとかにあっても驚かない気もするのですが、見つかりませんでした。順列生成の元となる要素集合をリスト[a]で与えて、そこ…

しばらく更新を怠っていました。今もまだ余り時間が取れないのですが、Doukaku.orgの問題を少し見る余裕が出てきました。平行して、いくつかHaskell関係の論文を読んでいたのですが、そのうちの一つ、Functional Programming with Overloading and Higher-Or…