Chat (Lingr.com)
Informaiton
Daily
Column
- MySQL日本語の旅(5/1)
- アクセス向上秘伝(5/9)
- 一風変ったHaskellλ門(6/13)
- SICP Answer Book (5/31) 問題3.26追加
Zope Solution
Extra
アーカイブ
OSS案内所
Site Info
関連リンク
1.1. プログラミングの要素
SICPにはすべての強力なプログラミング言語にそなわっている3つの機構を挙 げています．もちろんHaskellにおいても当然この3つの機構がそなわっていま す．
- 基本式：その言語が扱う最も単純な実体を表現するもの
- 組合せ手段：単純なものを組合せて，複雑なものにする方法
- 抽象する手段：組合せに名前を付けて，ひとつのものとして扱う方法
1.1.1. 式
Glasgow Haskell Compiler には ghci という対話モードのインタープリタが 附属しています．ghci とすこし対話してみよう．コマンドラインから ghciとタイプしてみよう．
% ghci ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.4.1, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base-1.0 ... linking ... done. Prelude>
Prelude> というプロンプトが表示されれば OK．
そうそう，あれこれ試す前にインタープリタの終了方法をば．終了するには プロンプトが出ている状態で :quit を入力します．
Prelude> :quit Leaving GHCi. %
再度 ghci を起動して( -v0 オプションを付けると最初のバナーが出ずに すぐにプロンプトが出る)，
% ghci -v0 Prelude>
Haskell のインタープリタは式を与えられると，それを評価し， その結果を印字します．数字を与えてみましょう．
Prelude> 486 486
四則演算はどうでしょう．
Prelude> 137 + 349 486 Prelude> 1000 - 334 666 Prelude> 5 * 99 495 Prelude> 10 / 5 2.0 Prelude> 2.7 + 10 12.7
もちろん，演算子の優先順位もちゃんとあります．
Prelude> 3 + 2 * 5 - 4 9
括弧ももちろん使えます．
Prelude> (3 + 2) * (5 - 4) 5
1.1.2. 名前付けと環境
A critical aspect of a programming language is the means it provides for using names to refer to computational objects.
「計算対象に名前を付ける」という機能がプログラミング言語の重要なポイン トです．Haskellでは，一旦計算対象に名前を付けたら，その名前が指し示し ている計算対象が別の計算対象に変えることはできません．
さて，実際に名前をつけてみましょう．っとその前に， Haskell では Scheme の場合とちがい，インタープリタとの対話セッションで は名前付けはできません．Haskell では対話セッションと定義編集は別に行い ます．インタープリタのセッションを終了させてから Emacs を立ち上げます． 編集ファイル名は，とりあえず， sicp112.hs としてください．ファイル名に ついてい拡張子 .hs には意味がありますので，拡張子の.hsは必 ずつけてください．
Prelude> :quit % emacs sicp-1-1-2.hs
haskell-modeがインストールされて設定が適切になされ ていれば，Haskellモードで Emacs が起動するはずです．ステータスバーの mode 表示に Haskell の文字があれば OK です．
-E:--- sicp-1-1-2.hs (Haskell Ind Doc)--L1--C0--All---------------------
ステータスバーがこんな感じになっていればいいでしょう．
さて，実際に名前をつけてみましょう．Haskell では名前付けは，= を 使います．
size = 2
これを使うには，この名前付けをインタープリタにロードします． Emacs 上で C-cC-l (コントロールキーを押しながら c のキーを押す，それか らコントロールキーを押しながら l (エル))をやると，Emacs の画面が2つに 分割されて下半分の領域にghciの対話プロンプトが出ます．
___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.4.1, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base-1.0 ... linking ... done. Prelude> :load "/home/nobsun/haskell/sicp-1-1-2.hs" Compiling Main ( /home/nobsun/haskell/sicp-1-1-2.hs, interpreted ) Ok, modules loaded: Main. *Main>
などと出ていれば OK です．(Emacs の画面の大きさによってはスクロールし てしまって，プロンプトしか見えないかもしれません)
いま名前をつけたものを評価してみましょう．プロンプトの後ろに size とタイプしてリターンキーを押すと size が評価されます．
*Main> size 2
これを使って計算もできます．
*Main> 5 * size 10
編集のエリアにもどって(C-xo または編集エリアをクリック)，名前を付けく わえましょう．
size = 2 p = 3.14159 radius = 10.0
また，C-cC-l をやります.
*Main> :load "/home/nobsun/haskell/sicp/sicp-1-1-2.hs" Compiling Main ( /home/nobsun/haskell/sicp/sicp-1-1-2.hs, interpreted ) Ok, modules loaded: Main. *Main>
のようにまたプロンプト *Main> が ghci との対話エリアに表示され るとおもいます．式を入力してみましょう．
*Main> p * radius * radius 314.159
さらに名前を加えます．
size = 2 p = 3.14159 radius = 10.0 circumstance = 2 * p * radius
C-cC-l
*Main> circumstance 62.8318
こんな風に演算結果を指すにも名前を使うことができます．
名前と計算オブジェクトとの対応の集りのことを環境ということがあります． (Haskellでは環境は第一級の計算対象ではないので，プログラミングの際にこ の言葉がでてくることはあまりない．) Haskellでは大域環境(Global Environment)はプログラムをインタープリタに ロードしたときに作られます．式を評価することでは大域環境を変更すること はできません．インタープリタとの対話セッションからは名前を追加できない のはそのためです．
コメントをどうぞ！
There is no comment.
1.1.3. 合成式の評価
SICPでは合成式の評価手順を以下のように示している．
- To evaluate a combination, do the following:
- Evaluate the subexpressions of the combination.
- Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).
先に部分式すべてを評価してから，次に演算子の適用を行うということである． Haskellで評価方法は実は説明しにくい．後の節で関数の話がでてきたところ で説明する．ここではSICPの記述と同じに解釈してもよい．
Haskellでは四則演算は演算子中置記法で書きます．Scheme の
(* (+ 2 (* 4 6)) (+ 3 5 7))
という式は，Haskellでは
(2 + (4 * 6)) * ((3 + 5) + 7)
と書きます． 評価結果はおなじです．
% gosh
gosh> (* (+ 2 (* 4 6))
(+ 3 5 7))
390
gosh> (exit)
% ghci -v0
*Main> (2 + (4 * 6)) * ((3 + 5) + 7)
390
*Main> :quit
%
これをSICP同様に木にすると以下のようになります．
すこし木の形がSchemeとは違いますね．
コメントをどうぞ！
There is no comment.
1.1.4. 合成手続
SICP にあるように自乗する関数 square を定義してみましょう． 前にも言ったようにHaskellではインタープリタの対話セッションで 定義を追加できません．emacsを使いましょう．
% emacs sicp-1-1-2.hs
では square の定義です．
square x = x * x
square x = x * x ↑ ↑ ↑ ↑ ↑ ↑ 自乗 x すわち x かける x
と読めますね．Haskell では関数の定義は
<関数名> <仮引数1> ... <仮引数n> = <本体>
のような形式で書きます．
上の自乗squareの定義を使ってみましょう．すでに書いたように Emacs に Haskell モードが設定されていれば，C-cC-l とやると編集ウィンドウが2つに 割れて片方が編集領域，もう一方がインタープリタとの対話領域になります． 2 の自乗を計算するには，square 2 を評価します．すなわち，プロンプト (*Main> )の後に square 2 と入力してリターンキーを押します．
*Main> square 21 441 *Main> square (2 + 5) 49 *Main> square (square 3) 81
Haskellでは関数の呼出しは，
<関数> <実引数1> ... <実引数n>
のように書きます．Haskellでは「関数の呼出し」という表現はあまり使いま せん．「関数の適用」といいます．Haskellでは関数適用の結合力が四則演算 子よりも強いので，square 2 + 5 は (square 2) + 5 に解釈されます．
*Main> square 2 + 5 9
2つの数の自乗の和を計算する関数 sumOfSquares の定義を追加しましょう． sicp-1-1-4.hs の編集領域にもどって編集します． 名前が sum-of-squares ではないのは Haskellでは名前に'-'文字を使えない からです．
sumOfSquares x y = square x + square y
前述のように，関数適用の結合力は四則演算子よりも強いので， square x + square y は (square x) + (square y) と同じです．
C-cC-l とやって，sicp-1-1-4.hs をインタープリタにロードしなおします． sumOfSquares 3 4 を評価すると．．．
*Main> sumOfSquares 3 4 25
さらに
f a = sumOfSquares (a + 1) (a * 2)
の定義を追加して再ロードして， f 5 を評価すると
*Main> f 5 136
コメントをどうぞ！
sumOfSquare と sumOfSquares がまざってしまってます。。
ありがとうございます。修正しました。
一応、let 文で追加できるような気がします。
ghci では let を使うことで一段下？の環境を作れます。が、複数行にわたる定義を書けないなどの制約があり使い勝手はよくありません。また、REPLでの let 節と let式 のちがいなどの説明が面倒なので。。。^^;
1.1.5. 手続き適用の置換えモデル
置換えモデルの考え方は，Haskellプログラミングでは最も重要な概念です． Haskellでは関数作用の「意味」を定めているのはこの置換えモデルです． Schemeとちがい可変データを持つ関数は存在しないので，このモデルが破綻す ることはありません．
Haskell でも Scheme と同様，関数が引数に適用されるときのプロセスは，置 き換えモデルです．しかし，評価の方法は「完全に展開して，簡約する」とい う正規順序の評価(normal-order evaluation)を行います．
たとえば，
sumOfSquare (5 + 1) (5 * 2)
⇒ square (5 + 1) + square (5 * 2)
⇒ ● * ● + square (5 * 2) {● → (5 + 1)}
⇒ 6 * 6 + square (5 * 2)
⇒ 36 + square (5 * 2)
⇒ 36 + ▲ * ▲ {▲ → (5 * 2)}
⇒ 36 + 10 * 10
⇒ 36 + 100
⇒ 136
のように評価が進みます．
コメントをどうぞ！
どのように評価が進んで行くかを表示するコマンドとかは有るのでしょうか？
残念ながら全体の評価の動きを追いかけるツールはありません。 個別には Debug.Trace ライブラリの trace という仕組みを使うことは できますが、使い方をまちがうと、本来の評価順を変えてしまことがあります。 trace については近々、説明したいとおもいます。
1.1.6. 条件式と述語
Haskell では条件によって違う値を表すのにはいくつか方法があります． 数値の絶対値を求める関数 abs0 をガードを使う書き方では，
abs0 x | x > 0 = x
| x == 0 = 0
| x < 0 = -x
のようになります． ガードの部分には評価すると論理値になるような式を書 きます．ガードは上から順に評価され，真になったガードに対応する値が採用 されます．どのガードも真にならないような場合には「評価時エラー」になり ます．
abs1 x | x < 0 = -x
| othrewise = x
最後のガードに，otherwise を置くとこの評価時エラーは起きません． otherwise は Prelude (デフォルトで処理系が読み込むライブラリ)で真値と 定義されています．これは if式を使って書以下のようにも書けます．
abs2 x = if x < 0 then -x else x
if 式の構文は
if predicate then consequence else alternative
で，必ず then 節と else 節を持ちます．predicate は評価すると真理 値になる式で，これが真の時は consequence がこの if 式の値に，そう でないときは alternative がこの if 式の値になります．
論理値に対する基本演算子は論理積 && と論理和 || があります， 否定関数は，not です．
コメントをどうぞ！
othrewise は、エラーが出ます。 otherwise は、大丈夫です。
1.1.7. 例：ニュートン法による平方根
ここはほとんどSchemeと同じに書くことができる．
square x = x * x
sqrtIter guess x = if goodEnough guess x
then guess
else sqrtIter (improve guess x) x
improve guess x = average guess (x / guess)
average x y = (x + y) / 2
goodEnough guess x = abs (square guess - x) < 0.001
sqrt' x = sqrtIter 1 x
The sqrt program also illustrates that the simple procedural language we have introduced so far is sufficient for writing any purely numerical program that one could write in, say, C or Pascal. This might seem surprising, since we have not included in our language any iterative (looping) constructs that direct the computer to do something over and over again. Sqrt-iter, on the other hand, demonstrates how iteration can be accomplished using no special construct other than the ordinary ability to call a procedure.
ループのため構文は Haskell にはありません．でも，ちゃんと計算できます (^^)v.
sqrt は標準プレリュードで既に定義されているので，ここでは sqrt' としま す．SICPでは不正確数(inexact number)の計算をさせるために，最初の予想値 を1ではなく1.0としている．Haskellでは型推論によって，sqrt' の計算が倍 精度浮動小数でおこなわれます．上のコードを sicp-1-1-7.hs というファイ ルに保存し，ghci にロードしてから，:type コマンドを使って，sqrt' の型 を知ることができます．
*Main> :type sqrt' sqrt' :: (Fractional a, Ord a) => a -> a
これは sqrt' の引数の型と返り値の型は一致し，その型は Fractional クラスのインスタンスでありかつ Ord クラスのインスタンスであるというこ とがわかる．型クラスの詳細は別途説明する予定(は未定^^;)です．
上の条件を満す数値型はデフォルトでは Float型とDouble型の2つですが どちらか明示的に宣言されていなければ，Double型になります．
実行結果は，
*Main> sqrt' 9 3.00009155413138 *Main> sqrt' (100 + 37) 11.704699917758145 *Main> sqrt' (sqrt' 2 + sqrt' 3) 1.7739279023207892 *Main> square (sqrt' 1000) 1000.000369924366
ここで sqrt' の定義に明示的に単精度小数を使うように sicp-1-1-7.hs に 次の型宣言を加える．
sqrt' :: Float -> Float
再ロードして実行してみると
*Main> sqrt' 9 3.0000916 *Main> sqrt' (sqrt' 2 + sqrt' 3) 1.7739279 *Main> square (sqrt' 1000) 1000.0004
となる．
コメントをどうぞ！
There is no comment.
1.1.8. ブラックボックス抽象としての手続
The importance of this decomposition strategy is not simply that one is dividing the program into parts. After all, we could take any large program and divide it into parts -- the first ten lines, the next ten lines, the next ten lines, and so on. Rather, it is crucial that each procedure accomplishes an identifiable task that can be used as a module in defining other procedures.
SICPの 1章，2章では関数適用の置換えモデルで意味を与えられる範囲ですべ てのプログラミングを行っています．置換えモデルの計算では，原則としては 計算の結果は部分式の評価の順には依存しません．これは命令文を書かれた順 序にしたがって実行する「普通の」プログラミングとは違います．したがって， 行ごとに分けて「上から順に」見ることが重要なのではありません．
Haskellでも where 節を使って内部定義を書けます．たとえば，
sqrt :: Float -> Float
sqrt x = sqrtIter 1.0 x
sqrtIter :: Float -> Float -> Float
sqrtIter g x | goodEnough g x = g
| otherwise = sqrtIter (improve g x) x
goodEnough :: Float -> Bool
goodEnough g x = abs (square g - x) < 0.001
imporve :: Float -> Float -> Float
improve g x = average g (x / g)
square :: Float -> Float
square x = x * x
average :: Float -> Float -> Float
average x y = (x + y) / 2
という定義を
sqrt :: Float -> Float
sqrt x = sqrtIter 1.0 x
where
sqrtIter g x | goodEnough g x = g
| otherwise = sqrtIter (improve g x) x
goodEnough g x = abs (square g - x) < 0.001
improve g x = average g (x / g)
square x = x * x
average x y = (x + y) / 2
のように書くことができます．sqrtIter，goodEnough, improve の第二引数は 常に sqrt の第1引数になりますので，
sqrt :: Float -> Float
sqrt x = sqrtIter 1.0 x
where
sqrtIter g | goodEnough g = g
| otherwise = sqrtIter (improve g)
goodEnough g = abs (square g - x) < 0.001
improve g = average g (x / g)
square x = x * x
average x y = (x + y) / 2
(2006-03-02) 以下の部分は筆者の勘違いでした． 「where 節のネスト」を見てください．
ただし，Haskell の where 節はトップレベル でのみ使用でき，ネストさせることはできないことに注意してください． ネストさせたいような場合には，let 式を使います．
コメントをどうぞ！
ネストできないとは例えば
hoge x
= fuga x
where
fuga x
= damepo x
where
damepo x
= orz x
where
orz = id
が駄目ということでしょうか？
でも、このコードghcでもHugsでも動きますが。
hoge x | x > 0 = fuga
where
fuga = "plus"
| otherwise = ""
といった感じのは駄目みたいですね。
最後の行の|でパースエラーが起きます。
でも、下のはOKでした。
hoge x | x > 0 = fuga
| otherwise = ""
where
fuga = tmp
where
tmp = "plus"
where はトップレベルの定義にのみ作用します．
foo = bar
where
bar = baz+1
where
baz = 1
は
foo = bar
where
bar = baz+1
baz = 1
と同じです．
foo = let
bar = 1
baz = bar
in
let
bar = baz+1
in
bar
とは書けますが
foo = bar
where
bar = baz+1
where
bar = 1
baz = bar
はエラーになります．また，guard を使う定義ではすべてのガードが連続して
いなければなりませんので，guard の間に where 節を置くことはできません．
ただし，パターンを使った定義ではそれぞれが独立していますので，
foo 0 = x
where x = 2
foo 1 = x
where x = 0
foo _ = x
where x = 1
のように書けます．
1つめと2つめのfooが同じだとすると
foo = baz
where
bar = baz+1
where
baz = 1
がOKだということになりますが、実際はそうじゃありません。
4つめのfooはたしかにそのままではエラーが発生しますが、
2個目のwhereの位置を右にずらせばエラーは起きず、fooの値は2になりました。
私が完全に勘違いしていました。説明を訂正し、「where節のネスト」の節を追加しました。
補足：where節のネスト
2006-03-02 
where 節のネスト
where節のネストについて筆者は勘違いしており誤った説明をしてしまいました． あらためて説明しなおします．
where 節はネストできます．
- where 節は直前の束縛の右辺に対してのみ働く
- where 節は直前の束縛よりインデントは深くなければならない
いろいろな例を挙げてみましょう。
foo = bar + baz where bar = 1 baz = 2
↑は，2行目が 2. に違反しているのでシンタックスエラー．
foo = bar + baz where bar = 1 baz = 2
↑は foo を評価すると 3 になります．
foo = bar + baz
where
bar = 1
where
baz = 2
↑は4行目が 2. に違反しているのでシンタックスエラー．
foo = bar + baz
where
bar = 1
where
baz = 2
↑は 1. によりトップレベルからは5行目のbazの束縛が見えないので bazの定義が有効範囲にないというエラーになります．
foo = bar + baz
where
bar = 1
baz = baz + 1
where
baz = 1
↑のとき 4 行目の baz の束縛の右辺の baz の値は後の where 節の束縛 baz = 1 により定義された値となるので foo を評価すると 3 になります．
foo = bar + baz
where
bar = bar + 1
baz = 2
where
bar = 0
↑のとき 1. により3行目からは最後の行のbarの束縛は見えておらず， 3行目は自身を自身で定義する再帰的定義とみなされます．構文エラーは ないが，foo を評価には，bar の評価が必要である．ところが bar の評価は 停止しません．したがって，fooの評価も停止せず foo の値は表示されません． (評価はCtrl-Cなどを使って強制終了してください．)
foo = bar + baz
where
bar = bar + 1
where
bar = 0
baz = 2
↑の場合 foo を評価すると 3 になります．
コメントをどうぞ！
There is no comment.
