わどぅー

記事については、中間出力の場合も多いので間違ってたらごめんなさい。twitter は waddlaw です。どうぞよろしく。

プログラム工学 VI 講義資料 第一回 演習課題

Haskell の講義らしい。復習を兼ねて問題解いてみようかな。
http://web.archive.org/web/20041231040553/http://www.teu.ac.jp/kougi/koshida/Prog6/text01.html
アーカイブから取ってるみたいなのでページ転送まで時間かかります。

2004年のやつなのでHgus使ってるみたい。だけど、もう時代はGHCなのでghci使って解いていきます。英語苦手だから、できるだけ英語表記入れてみよ
課題1に「(Haskellでは,プログラムのことをスクリプトと呼ぶ)」ってそうなんだ!?

                                                                        • -

課題1
問1 dbl (sqr 2) と sqr (dbl 2) の結果が異なる理由を説明せよ.

一応、実行結果は

*Main dbl (sqr 2)
8
*Main sqr (dbl 2)
16

遅延評価 (lazy evaluation) だと評価順序が次のようになるから。ちなみに、遅延評価は最外間約 (outer most reduction) と式グラフの共有を組み合わせた評価方法。こういう間約の方法をグラフ間約 (graph reduction) って言うんだっけ。
詳しくはこの辺http://en.wikibooks.org/wiki/Haskell/Graph_reductionを参照すると良いのかな。

dbl (sqr 2)
= (sqr 2) * 2
= (2 * 2) * 2
= 4 * 2
= 8

sqr (dbl 2)
= (dbl 2) * (dbl 2) -- 式グラフをポインタで共有するので、* の左の (dbl 2) と
-- 右の (dbl 2) は内部的に同一の式
= (2 * 2) * (2 * 2) 
= 4 * 4
= 16

型についても整理しておこう

sqr :: Int -> Int
sqr 2 :: Int
dbl :: Int -> Int
dbl (sqr 2) :: Int
sqr (dbl 2) :: Int

ちゃんと型が合ってるから大丈夫だ!

                                                                        • -
                                                                        • -

問2 23 - dbl (3+1) と 23 - dbl 3+1 の結果が異なる理由を説明せよ.
同じ要領でやってみるうう

23 - dbl (3+1)
23 - ((3+1) * 2) -- 関数適用 (function application) の優先順位は10で、どの演算子 (operator) よりも強い
23 - (4 * 2)
23 - 8
15

23 - dbl 3+1
23 - (3 * 2) + 1 -- さっきは(3+1)がdblの引数だったけど、今回はカッコがないので引数は3になる
23 - 6 + 1 -- (-),(+)どちらも infixl 6 なので、カッコは次のようになるでしょう
(23 - 6) + 1
17 + 1
18

Haskell演算子については「ふつうのHaskellプログラミング」や「The Haskell School of Expression (長いので SoE と略します)」を読むと書いてあったしたかなぁ。
演算子の結合性と優先順位を調べるために、ghciには :i コマンドが用意されてます。
自分で作った演算子に結合性と優先順位を与えるためにはソースコードで infixr, infixl, infix キーワードを使って定義できます。
(ネットで見やすい表はこれかなぁ。ふつけるのパクリblogっぽいから嫌いだけど・・・
http://haskell.g.hatena.ne.jp/muscovyduck/20060714/p1)

一応、型についてもみとこ

(+) :: Num a => a -> a -> a
(-) :: Num a => a -> a -> a

多相型 (polymorphic type) になってるけど、この段階だと理解してなくても問題とは関係ないかなぁ。具体的な型変数 (type variable) a はInt型やらDouble型などNumクラスのインスタンスになってる型。

                                                                        • -
                                                                        • -

問3 $$ という式は,何を表わしているのか? 実行結果から推測せよ.
なにこれ、ghciで実行すると

*Main> $$

<interactive>:1:1: parse error on input `$$'

って出るから、Hugsだけで使えるコマンドなのかな?

                                                                        • -
                                                                        • -

問4 dbl sqr という入力がエラーになる理由を説明せよ.また,これを入力した際にHugsが出力するエラーメッセージの意味を説明(推測)せよ.
Hugs のエラーメッセージは省略するとして、エラーになる理由は型推論を自分で行えばわかるかな。

dbl :: Int -> Int
sqr :: Int -> Int

つまり、dblもsqrもIntの入力を1つ受け取り、Intの出力を返す関数だとわかる。dblの第一引数はIntなので、sqrの型 Int -> Int と合わない。
よって、型エラーとなる。

これは簡単な例だけど、dblの第一引数が型変数になってくると楽しくなる。具体的には次のような関数

id :: a -> a
id n = n
sqr :: Int -> Int
sqr n = n * n

この場合の型を色々と考える

id :: a -> a
id 1 :: Num a => a
id sqr :: Int -> Int

idはPreldueで定義されている恒等関数。さっきは型エラーとなったけど、今回は型変数 a が (Int -> Int) という関数を引数に取る事ができるので次のような流れで Int -> Int の関数になる

id :: a -> a
id sqr :: (Int -> Int) -> a -- 型変数 a は sqr の型となる
=> id sqr :: (Int -> Int) -> (Int -> Int) -- 右の a は左と同じ a なので、同様に同じ型にならなければならない。もし、違う型であれば a -> b のように違う型変数となるはず。
=> id sqr :: (Int -> Int) -> Int -> Int -- 型の上で (->) は右結合となるので、カッコを外せる
=> id sqr :: Int -> Int -- id は引数を1つ適用したはずなので Int -> Int を返す関数 (id sqr) となった。(この例だと実用性のカケラも無いからあんまり面白くない・・・)

id というのは恒等関数なので、id sqr = sqr なのは明らかでしょう。実際に (id sqr) 2 と実行すると、4 が返ってくるはず。

もう少し面白い例だと、Prelude に const という関数があります。

const :: a -> b -> a
const a b = a -- const a _ = a と書く方が良いね。(b の値は使われないのに変数を束縛 (bind) するから)。_ はワイルドカードの意味で何でもマッチして、マッチした値を捨てる

この関数を実行してみる

*Main> const 1 2
1

このように、常に第一引数のみを返す関数です。なので第二引数は何を入れても大丈夫です。
const 1 ⊥ = 1 というように (⊥ は評価されたら止まらない計算を表す記号 bottom) 無限の計算を入力として与えても、値を返す関数を非正格関数 (non-strict function)と言います。
しかし、const は第一引数については const ⊥ 2 = ⊥ となるため、正格関数となります。
正格関数と、正格評価 (eager evaluation) は全然違うので注意。正格評価は遅延評価の逆ですね。(この辺の話は SoE で読んだ気がする)

かなり脱線しましたが、なにがしたいのかというと!このように常に第一引数を返す関数 (定数関数と呼ばれる) は Prelude に存在しますが、常に第二引数を返すような定数関数は存在していません。
なので、これを作ってみます。つまり、次のような実行結果が欲しいわけです。

*Main> const' 1 2
2

これを作るのは非常に簡単です。const と同様の定義をすれば良いのです。

const' :: a -> b -> b
const' _ b = b

これでも良いんですけど、部分適用 (partial apprication) を使えばもっと短くなります。
部分適用とは、簡単に言えばn個の引数を取る関数にn-1個までの引数を適用することです。n個適用しちゃうと値になってしまうので部分適用とは言わないです。

const' :: a -> b -> b
const' = const id

実行してみるとわかるんですが、両者の結果は同じです。何が起きたのかは、型を見ていくとわかりやすいです

id :: a -> a
const :: a -> b -> a
const id :: (a -> a) -> b -> a -- さっきと同じように型変数 a は (a -> a) の関数
const id :: (a -> a) -> b -> (a -> a)
const id :: (a -> a) -> b -> a -> a
const id :: b -> a -> a -- 実質ここで答えは出てるけど、わかりやすくするために b と a の変数名を入れ替えてみる
const id :: a -> b -> b -- 導出完了

型変数は1つの型だけでなく、関数も大丈夫なんだと理解しとくと Haskell が3倍ぐらい楽しくなる気がする!
プログラムの方で考えるとこんな感じかな。

(const id) 1 2
= (const id 1) 2 -- const は2引数の関数なので、こんな感じでカッコがつく
= id 2 -- const の定義
= 2 -- id の定義
                                                                        • -

課題2

 :typeコマンドは,与えられた式の型を判別するためのコマンドで「:type 式」の形式で使用する.例を下に示す.

*Main> :type sqr 2
sqr 2 :: Int

 課題1で入力した各式($$を含む式,13 `div` 5,13 `mod` 5 及び dbl sqr を除く)に対して,:typeコマンドを実行し,各式の型を確認せよ.なお,この課題には設問はないので,レポートには実行結果だけを示せば良い.もちろん,実行結果に対する考察(なぜ,そのような結果が得られるのか?)は,必要である.

型の考察については終わってるので答えだけ。

sqr a :: Int -- a って何かと思ったら、最初ら辺で定義してたんだね、忘れてた><
sqr :: Int -> Int
dbl (sqr 2) :: Int
sqr (dbl 2) :: Int
23 - dbl (3+1) :: Int
23 - dbl 3+1 :: Int
                                                                        • -

課題3

 課題1で作成したスクリプト(ex1.hs)に,次の機能を持つ関数を追加し,正しく動作することを確認せよ.もちろん,ex1.hsで定義された他の関数を利用してよい.

入力(整数値)を2倍した後に二乗する関数.
入力(整数値)を二乗した後に2倍する関数.

素朴な実装はこんな感じでしょうか (関数名ださい・・・)

ex3_1 :: Int -> Int
ex3_1 n = sqr (dbl n)

ex3_2 :: Int -> Int
ex3_2 n = dbl (sqr n)

カッコを使わない実装だとこんな感じかな

ex3_1 :: Int -> Int
ex3_1 n = sqr $ dbl n

ex3_2 :: Int -> Int
ex3_2 n = dbl $ sqr n

($) の型と実装はこうだっけ

($) :: (a -> b) -> a -> b
f $ x = f x

つまり、($) の第一引数は関数で第二引数の値を第一引数の関数に適用するような演算子ですね。
ついでにポイントフリーで書くとこんな感じ

ex3_1 :: Int -> Int
ex3_1 = sqr . dbl

ex3_2 :: Int -> Int
ex3_2 = dbl . sqr

(.) は関数合成 (function composition) で優先順位は最低の1です。型と実装はこうかな

(.) :: (b -> c) -> (a -> b) -> a -> c
(.) g f x = g (f x) -- 本当は g . f = λx -> g (f x) の方が良いね。(.) :: (b -> c) -> (a -> b) -> (a -> c) というように、合成した関数を返すことを強調できるから。

詳しくは、これ読んでるうちに出てくると思うからそのときかな。。。

                                                                        • -

やってみると、内容的にはプログラミングhaskellと同じような感じかな? 意外と楽しんでしまった・・・
間違ってたらコメントでお願いします。