他人のHaskell日記

■ HCFP-Chapter 11 プログラム開発

問題を理解する

最初にしなければならない事は、いまから解こうとしている問題を理解することだ

• 問題への入力と出力は何か？入力や出力に特別な条件はあるか？
• 問題を明白にするには例を見るのが役立つ
• 問題は解けるか？仕様は完全か？明らかにせねばならぬ側面があるか？
• 複数の理解の仕方があるならば、仕様者に、何を意図しているのか聞け
• 問題は構造を持っているか？問題は分割できるか？図が問題の著述に役立つか？

ソリューションを設計する

プログラムを書くまえに、どのようにやるのか計画する必要がある。

• 似たような問題を見たことがあるか？そうなら、それをガイドに使える
• より単純だが関連した問題を考えられるか？それを解けるなら、それを使うか、改造できる。
• 問題を一般化できるか？元の問題よりも簡潔になるかもしれない。
• 問題のアーキテクチャーは何か？(比較的)独立に解決できるような部分に分解できるか？部品それぞれについてと同様、部品を組み合わせる方法についても考えなければならない。
• ボトムアップアプローチ：入力から出力まで、どういけばいいか？中間のデータをガイドに使え。
• トップダウンアプローチ：どのようなリソースがあれば、問題が解決できるかを考えろ。
• 計画の時点ですら、使えるリソースが何かを知っておくことは重要だ。プログラミング言語やライブラリが何を提供しているのかをチェックしておけ。他の重要なリソースには、過去に書いたあなた自身のプログラムも含まれる。
• 変化を念頭に入れて設計せよ。プログラムが便利なら、そのライフタイムにおいて何度も変更されるだろう。

プログラムを書く

プログラムを書くには、言語が提供するリソースについて知っておく必要がある。非公式な設計や計画に従う必要もある。

• Haskellに存在する、リストに対する多くのライブラリ関数がプログラミングをサポートする。これらのいくつかは一般的な多相型の高階関数であり、いろいろな状況で使える。もし可能なら使ってみよう。
• 他のデータタイプに似たような一般的な関数が定義できることに気がつくだろう。これらの関数を使うのは、ソリューションをいちから書くより簡単だ。
• 特定の関数を抽象化することで、一般的な関数を定義することができる。特定の関数(例えば2倍するといった)は、mapのような一般的な関数のパラメータにすることができる。
• 多くの言語で、異なる場合への定義ができる。Haskellはパターンマッチングも提供しており、それは場合を区別するだけでなく、オブジェクトの一部を選択できる。
• 再帰はリストや数値のようなデータタイプに対してプログラムを設計する一般的な戦略である。再帰関数fを引数xについて定義するとき「f .. があればどう定義できるか」と考えてみよう。
• リスト内包表記はリストに対する表現力の高い記法を提供する。
• 関数を定義しようとすると、更に他の関数を定義する必要がでてくる。それはwhere節かtop-levelにおける。
• 必要な関数が定義できない場合、単純なものを定義してみよう。それは欲している関数のモデルになるかもしれないし、最終的な関数の定義で使えるかもしれない。

反省

やったことをふりかえることはプログラム、設計、そのプログラム自身の仕様に影響を与えるだろう

• ソリューションをテストできるか？特別な場合について熱心に見るだけでなく、似たような振舞いを見せるべきプログラムのテストグループを考える必要がある。
• テストがerrorやバグを暴いたら、その源を探そう。エラーは偶然の失敗のせいなのか、Haskell言語がどう動くのか理解してなかったせいなのか、問題を解決する手段を勘違いしていたからなのか？問題そのものを勘違いしていたのか？それとも他の理由なのか？
• 犯した誤ちから学ぶことができる。全ての誤ちを、理由とともに記録せよ。そうすれば、誤ちを繰り返さずに済む。
• プログラムが正しく振る舞うことを証明できるか？そうでなければ、なぜそうなのか？それは、プログラムや設計での誤ちに面しているのか？
• 同じプログラムを書けと言われたら、どのように違った書き方が出来るだろうか？
• プログラムを拡張や変更しろといわれたら、それは簡単だろうか？難しいとしたら、どのように設計し、ソリューションを書いていたなら、もっと簡単に変更できただろうか？
• プログラムは十分な速度で動くだろうか？そうでなければ、どこにボトルネックがあるかわかるだろうか？どのように変更をしてパフォーマンスを向上させることができるかわかるだろうか？

■ メモ：Haskellの再帰

Haskellは再帰をどうやってやっているのだろう

(中略)

一時はYコンビネータ使おうとまで思ったけど、Yコンビネータはハイブロウすぎる。そんな言語だれも使ってくれないだろう。巧妙に隠蔽する方法も無い訳では無いけど。

http://homepage3.nifty.com/mogami/diary/d0608.html#04t2

Haskell 98 レポートを見ると

変換:

(中略)

let p = e1 in e0 = let p = fix ( \ ~p -> e1) in e0

ここで fix は最小不動点演算子である。

http://www.sampou.org/haskell/report-revised-j/exps.html

と書いてあるので、まさに不動点演算子を使いながら、それを巧妙に隠蔽しているように思う。

ちなみにモナドの場合は、構文拡張オプションを指定しない限り、mfixという不動点演算子を使わなければならないようである。(理解していないが、haskell-jpのメーリングリストのログにそういう話題があった。)