エディターは何をおつかいですか？

プログラム書く人には、お気に入りのエディターがあると思うのですが、みなさん何をおつかいなのでしょうか？

自分の場合には、Debian上でscreenを使い、画面を分割し、vimを使いながら、別の画面でghciを使うという感じでやっております。

Haskellなら、入門Haskellでも簡単に書かれていましたが、Emacs　+　Haskell-modeを使われているかたがおおいのでしょうかね。

追記: Ajaxイン・アクション欲しい！
すいません。言いたかっただけです。

パスカルの三角形

SICPの問題1.12は、パスカルの三角形。
パスカルの三角形は、三角形の辺上の数は全て1。三角形の内部の数はその上の2つ上の数の和という三角形。
こんなかんじ

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
............

rubycoさんやtakatohさんがやられていたやつ。
SICPでは、三角形を描くのではなく、要素を求めるだけでいい。
というわけで、定義に忠実に実装。

pascal x y
        | x == y = 1
        | y == 1 = 1
        |otherwise = (pascal ( x - 1 ) (y-1)) + ( pascal ( x- 1) y)

*Main> pascal 4 3
3
*Main> pascal 5 3
6
*Main> pascal 1 1
1

簡単な定義のため、気づかないうちにid:takatohさんの実装とほぼいっしょになっちゃいました。

追記:id:takatohさんのコメントより。
こちらも、御参考に。http://hpcgi2.nifty.com/1to100pen/wiki/wiki.cgi?p=%CB%E8%C6%FCHaskell の 2006-05-12
http://d.hatena.ne.jp/takatoh/20060514

再帰的にプロセスと反復的プロセス

問題1.11は、次の定義を再帰的プロセスと反復的プロセスで書けというもの

n < 3 のとき　f(n) = n
n >= 3 のとき f(n) = f( n -1 ) + 2f(n -2) + 3f(n-3)

では、再帰的方法の実装から

saikiF n
        | n < 3 = n
        |otherwise = saikiF ( n-1 ) + 2 * (saikiF ( n -2 )) + 3 * ( saikiF ( n -3 ))

*Main> saikiF 2
2
*Main> saikiF 5
25
*Main> saikiF 10
1892

このやりかただと、saikiF(n-1),saikiF(n-2),saikiF(n-3)を実行していくときに、同じ計算を何度も行うことにより、効率がわるくなってしまいます。(ただ、Haskellは処理系がメモ化を行うから、そこまで遅く ないというのを読んだことがあります。あいまいなので、誰か情報お持ちでしたら教えてください)

というわけで、この関数を反復処理に直します。

hanpuku a b c d
        | d == 0 = c
        |otherwise = hanpuku  ( a + ( 2*b) + (3*c)) a b   (d -1)
hanpukuF n = hanpuku 2 1 0 n

*Main> hanpukuF 2
2
*Main> hanpukuF 5
25
*Main> hanpukuF 10
1892

ふつうのHaskellプログラミング

id:sshiさんのところで発見。日本語のHaskellの本。ふつうのHaskellプログラミングがAmazonに登録されたようです。

わたしも早速注文しました。

ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門

アッカーマン関数

問題1.10はアッカーマン関数。また、いつもどおり、schemeで書かれている関数をHaskellに

ackermann x y
        | y == 0 = 0
        | x == 0 = 2 * y
        | y == 1 = 2
        | otherwise = ackermann ( x -1 ) ( ackermann x ( y - 1))

で、問題は次の引数のときの値は何か？だから

*Main> ackermann  1 10
1024
*Main> ackermann  2 4
65536
*Main> ackermann  3 3
65536

このような結果になります。また、

f n = ackermann 0 n
g n = ackermann 1 n
h n = ackermann 2 n

の数学的定義を述べよという問題もある。
とりあえず、何パターンかやってみる。

*Main> ackermann  0 2
4
*Main> ackermann  0 3
6
*Main> ackermann  1 2
4
*Main> ackermann  1 3
8
*Main> ackermann  2 2
4
*Main> ackermann  2 3
16
*Main> ackermann  2 4
65536

これをみると、どうやら、fは2*n、gは2^nになるみたいだけど、hがよくわからない。
しょうがないので、こたえをみる。これは、わからなかったや。

haskellリングつくってみました

はてなリングを見ていて、schemeリングや、OCamlリングがあるのに、Haskellが無いのはと思い、haskellリングを作ってみました。
Haskellの勉強をしている人や、興味をもっている人の集まれる場にでもなれればと思いつくりましたので、よろしければ登録してみてください。

あと、当方まったく絵心がないもので、ロゴが作れていないのですが、誰か作ってやってもいいというような方がおれば、作っていただけると幸いです。

置き換えモデル

置き換えモデルとは、どうやら出てくる関数を置き換えていって、最後に計算をするモデル。遅延評価といっていいのかな。

問題1.9では、引数を1増やす手続きincと引数を1減らす手続きdecをつかって、2つの整数をたす方法を置き換えモデルを使い、4と5をたす過程を示すというもの。とりあえず、関数が2つ定義されているんだけど、まずはそれをHaskellで実装

mplus x y
        |x == 0 = y
        |otherwise = 1 + ( mplus ( x - 1 ) y)
mplus' x y
        |x == 0 = y
        |otherwise = mplus' ( x -1 ) ( y + 1)

incとdecは普通の足し算・引き算で実装。
では、mplusと定義したほうから。

mplus 4 5
1 + mplus 3 5
1 + 1 + mplus 2 5
1 + 1 + 1 +  mplus 1 5
1 + 1 + 1 + 1 + mplus 0  5
1 + 1 + 1 + 1 + 5
1 + 1 + 1 + 6
1 + 1 + 7
1 + 8
9

この方法だと、再起終了後にいっきに計算される。
本では、このように遅延演算の列の長さがスッテプ数のようにnに比例して増加するプロ セスを線形再起的プロセスとよんでいる。
では、mplus'だとどうなるだろう？

mplus' 4 5
mplus' 3 6
mplus' 2 7
mplus' 1 8
mplus' 0 9
9

この場合だと、再起呼び出しをするたびに足されていく。
このようにステップ数がnに比例して増加するプロセスを線形反復的プロセスというらし い。