授業中に一度解いた問題も含まれているかもしれませんが、改めて紙にまとめてください。
プリントの以下の問題を解いて下さい。
問 2.5.4 (第 2 章 p.12)
2つの引数 x, xs を受け取り、リスト xs から
x と等しい要素を
もっとも先頭に現れる一つの要素だけ取り除いたリストを返す関数 deleteOne
すべて取り除いたリストを返す関数 deleteAll
をそれぞれ定義せよ。
問 2.6.1 (第 2 章 p.14)
すべての有限リスト xs について、
が成り立つことを xs に関する帰納法で証明せよ。 (どこで帰納法の仮定を使用するか明示せよ。 さらに (++) の定義の等式:
[] ++ ys = ys -- ① (x:xs) ++ ys = x : (xs ++ ys) -- ②を使った場合は、①, ② をラベル付けせよ。 帰納法の仮定を使った場合は、⑨ をラベル付けせよ。 )
問 2.10.2 (第 2 章 p.18)
repeatList [2,5] が [2,5,2,5,2,5,2,5,2,5,…]、
repeatList [1,2,3] が [1,2,3,1,2,3,1,2,3,…]
という無限リストになるような関数 repeatList :: [a] -> [a]
を定義せよ。なお、引数のリストの要素数は任意である。
ヒント: (++) を使用せよ。
問 2.12.3 (第 2 章 p.22)
非負の整数 n を受け取り、
1 ≦ x < y < z ≦ n
の範囲で x2 + y2 = z2
となるすべての x, y, z
の組を生成する関数 chokkaku
:: Integer -> [(Integer,Integer,Integer)]を内包表記を用いて定義せよ。
(挑戦・非必須)(ナイト巡回) 問 2.13.4 (第 2 章 p.26)
ナイトは、右の図 の中央のマスから○印のマスへ
移動できるチェスのコマである。5 × 5マスのチェス盤で、あるマス
(例えば、左上隅)から始めてすべてのマスを 1 回ずつ訪れる経路を求めるプログラムを作成せよ。
Tree 型に対して、次のような関数を定義せよ。
depth :: Tree a -> Integer -- 深さ preorder :: Tree a -> [a] -- 前順走査 inorder :: Tree a -> [a] -- 中順走査 postorder :: Tree a -> [a] -- 後順走査 reflect :: Tree a -> Tree a -- 鏡像例えば、① depth tree4, ② preorder tree4, ③ inorder tree4, ④ postorder tree4, ⑤ reflect tree4 の結果はそれぞれ、 ① 3, ② [2,1,3,4], ③ [1,2,3,4], ④ [1,4,3,2], ⑤ Branch (Branch (Branch Empty 4 Empty) 3 Empty) 2 (Branch Empty 1 Empty) となる。
Q 3.1.1 で定義したじゃんけん (RPS) 型
data RPS = Rock | Scissors | Paper
を、deriving を用いずに、Eq クラスのインスタンスとして宣言せよ。
参考にするプログラム: TypeClassExample.hs
できるだけ短く簡潔におさめて下さい。 コンピュータを使う場合は ΤΕΧ を推奨します。
提出〆切は、12月 10日(木)の「プログラミング言語意味論」授業開始時です。
(オンラインの提出はありません。)
4Q の「プログラミング言語意味論」を受講しない人は、
7F 学科事務前の香川のポストに提出してもらっても構いません。