問 2.5.4 （第 2 章 p.12）
2つの引数 x xs を受け取り、リスト xs から
x と等しい要素を
もっとも先頭に現れる一つの要素だけ取り除いたリストを返す関数 deleteOne
すべて取り除いたリストを返す関数 deleteAll
をそれぞれ定義せよ。
問 2.6.1 （第 2 章 p.14）
すべての有限リスト xs について、
- xs ++ [] = xs
- (xs ++ ys) ++ zs = xs ++ (ys ++ zs)
が成り立つことを xs に関する帰納法で証明せよ。
（どこで帰納法の仮定を使用するか明示せよ。）
ただし (++) は、
プリント第 2 章 p.12 で定義されている関数である。
問 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.2 （第 2 章 p.22）
非負の整数 n を受け取り、
0 ≦ x ≦ y ≦ n
となるすべての x, y
の組を生成する関数 foo
:: Integer -> [(Integer,Integer)]を内包表記を用いて定義せよ。
ヒント: [m ..n ] を使う。
（挑戦・非必須）（ナイト巡回） 問 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) となる。
組込みのリスト型と等価なデータ型
data MyList a = MyNil | MyCons a (MyList a)
を、deriving を用いずに、Eq クラスと Ord クラスのインスタンスとして宣言せよ。Ord クラスのメソッドにはいわゆる辞書式の順序を用いよ。
（クラスの定義中にデフォルトの実装が定義されているので、 Eq クラスの == メソッドと Ord クラスの <= メソッドだけを定義すれば、 他のメソッドの定義は自動的に生成される。）
ヒント: 少なくとも以下のケースをテストせよ。
- toMyList "abc" <= toMyList "xyz" -- True
- toMyList "abc" <= toMyList "abd" -- True
- toMyList "axc" <= toMyList "xbz" -- True
- toMyList "xbz" <= toMyList "axc" -- False
- toMyList "abc" <= toMyList "abcde" -- True
- toMyList "abc" <= toMyList "ab" -- False
- toMyList "" <= toMyList "abc" -- True
- toMyList "abc" <= toMyList "" -- False
ただし toMyList は以下のように定義された補助関数とする。
toMyList :: [a] -> MyList a
toMyList [] = MyNil
toMyList (x:xs) = MyCons x (toMyList xs)
参考にするプログラム: TypeClassExample.hs
