Haskell

STはState Transformerとは言うけれど

少し前に巷ではやったSTのことを勉強してみました。原典のLazy Functional State Threadsをかじってみました。僕はStateモナドはなんとなく自分でかけるくらいまで理解していたのですが、STは使ったこともないし、いったい何物なんだかぜんぜん知りませんで…

Data.Treeを初期化する方法を工夫してみた

詳しいことはそのうち書くとして、ReaderモナドとStateモナドの違いなんかを考えているうちにXMLやHTMLの記述を簡略化するDSLみたいなものがあったらいいなと思ったりしていたら、どちらのブログかは失念してしまったのですが、たしかmoeというライブラリが…

関数じゃなくてもモナドになれる

また、間が開いちゃったんですが、少し前にどんな関数でもモナドになれる件をかいたのですが、今回、さらに一歩進めて、ただの値でもモナドになることを書きたいと思います。ということでこちら: newtype V a = V {unv :: a} instance Monad (V) where retu…

モナドの分類

モナド型クラスに属する型はいろいろとあって、その中にはさらにMonadPlusをサポートするモナド型があったり、そうでないものがあったりするわけで、これはつまりいろいろなモナド型を2種類に分類しているわけですよね…IO (Maybe a)という型のモナドのコー…

実は関数もモナドとして捉えることができる

関数(a->b)はそのままArrowのインスタンスになっているわけなんですが、実はモナドのインスタンスとしても機能できることに気づきました…ステートモナドとかを見れば何の秘密にもなっていないことなんですが…「関数もモナドのインスタンスとして扱える」とい…

unwordsのコスト

Haskellで遊ぶよ さんのunwordsはO(n^2)?を読んで、unwordsのコスト、僕も考えてみました。コストはひょっとしたらO(n)なような気がしています。なぜかというと、unwordsがfoldrを使っているからかもと…間違ってるかもしれませんが…foldrはright associative…

ずらしてみよう

ずいぶんとご無沙汰様になってしまいましたが、まだまだ遊んでますよー。Haskellで… Haskellで遊ぶよさんの takeWhile2とdropWhile2 を読んでいてちょっと前にどこかのプレゼン資料で見たちょっと感心したテクニックを思い出しました…takeWhile のシグネチャ…

IArrayの怠け度合い

今日はちょっとしたメモ…リストのレイジーな振舞い方は割りとはっきりとイメージできるのですが、ちょっと遊びでIArrayを使っていて遅延評価がどういった形で動いているのかが気になったので、ちょっと実験してみました。IArray、つまりImmutableなArrayを作…

Programming Windows in Haskell、次の一歩。

もうかれこれ半年以上前のポストの続きになるんですが、なんというか、HaskellでWin32を直にたたくスタイルでGUIアプリを書いてみたわけなんですが、前回挫折したのは、ウィンドウごとのステートをどうやって保持するかというところだったわけです。IORefを…

PEGパーサーのバックトラッキング

前回、どちゃっと乗せたPEG電卓のコードなんですが、これはPappyやFrisbyのようにメモ化をまったくやっていないPEGパーサーです。ちょっと思いついて、いったいどれくらいの勢いでバックトラッキングが起きているのかを調べてみました。 バックトラッキング…

PEG電卓をやってみた

前回のポストから日数がたってしまいましたが、たまにはちゃんと最後まで書こうということで、出来上がったPEG電卓のコードを乗せておきます。パーサーの定義が前回までのポストとは微妙に変わっていますが、大筋は同じです。こっちのほうがコンパイルして動…

PEGパーサーを書いてみる:後半

前回、シグネチャだけで終わっていたパーサーを実装してみました。 seqP :: Parser i o -> Parser i o -> Parser i o seqP p q = do v ([o] -> Parser i o) -> Parser i o -> Parser i o ifP p ps pf = Parser $ \i -> case (runParser p i) of Nothing -> r…

PEGパーサーを書いてみる

PEGで文法を表現してみて、ルールのそれぞれの使い方動きにもなじみが出てきました。ここで、PEGパーサーをちょっと書いてみたいと思います。PappyやFrisbyのようにO(N)というわけに行くかどうかはわかりませんが…方針としては、Parsecのまねということで、…

スクラップ・ユア・ボイラープレート

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

遅延IOは可能か

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

fixと無限リストの相性

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

インチキデータ再帰と単位換算

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

fixを無限再帰させないもう一つの方法

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

fixを使うためのヒント

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

Data.List.unionは結構重そう

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

データ再帰という考えと双方向リスト

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

リスト操作のコスト

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

Haskellのプログラムをプロファイルしてみる。

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

バックトラックとリストモナド

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

メモ化とボックス型とグラフ簡約(Haskellとメモ化のこと その3)

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

Haskellのメモ化のこと:その2

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

Haskellのメモ化のこと

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

Haskellとglobal

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

Programming Windows in Haskell、次の一歩がなかなかでない。

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

ArrowLoopとCircularPrograming

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