プログラミング・パラダイム　レポート

授業中に一度解いた問題も含まれているかもしれませんが、改めて紙にまとめてください。

プリントの以下の問題を解いて下さい。

問 2.4.10 （第 2 章 p.12）
2つの引数 x, xs を受け取り、リスト xs から x と等しい要素を
- もっとも先頭に現れる一つの要素だけ取り除いたリストを返す関数 deleteOne
- すべて取り除いたリストを返す関数 deleteAll
をそれぞれ定義せよ。
問 2.5.1 （第 2 章 p.14）
すべての有限リスト xs について、
1. xs ++ [] = xs
2. (xs ++ ys) ++ zs = xs ++ (ys ++ zs)
が成り立つことを xs に関する帰納法で証明せよ。（どこで帰納法の仮定を使用するか明示せよ。さらに (++) の定義の等式:
```
  []     ++ ys = ys             -- ①
  (x:xs) ++ ys = x : (xs ++ ys) -- ②
```
を使った場合は、①, ② をラベル付けせよ。帰納法の仮定を使った場合は、⑨ をラベル付けせよ。）
ただし (++) は、プリント第 2 章 p.13 で定義が示されている関数である。
問 2.10.1 （第 2 章 p.21）
take の反対に、リストの最初の n個の要素を取り除く関数 myDrop :: Integer -> [a] -> [a] を定義せよ。

ヒント: (++) を使用せよ。
問 2.11.3 （第 2 章 p.23）
非負の整数 \(n\) を受け取り、 \(1 \le x \lt y \lt z \le n\) の範囲で \(x^2 + y^2 = z^2\) となるすべての x, y, z の組を生成する関数
```
chokkaku :: Integer -> [(Integer,Integer,Integer)]
```
を内包表記を用いて定義せよ。
（挑戦・非必須）（清一色）問 2.12.5 （第 2 章 p.27）
1. ソートされた整数のリストのなかで、3つ並びの数、3つの同じ数、2つの同じ数を見つけてリストアップする関数 shuntsu（順子）、 kotsu（刻子）、 toitsu（対子）をそれぞれ定義せよ。
```
  Prelude> shuntsu [1,3,3,4,5,7,8,9]
  [[3,4,5],[7,8,9]]
  Prelude> toitsu [1,3,3,4,5,7,7,9]
  [[3,3],[7,7]]
```
2. 14個の要素を持つ整数のソートされたリストがマージャンの清一色（チンイーソー）のアガリ形になっているかを判定する関数 chinitsuを定義せよ。ただし、アガリ形とは、順子（3つ並びの数）または刻子（3つの同じ数）が 4つ、対子（2つの同じ数）が 1つ、そろった形である。
（代数的データ型）問 3.1.3 （第 3 章 p.3）

Tree 型に対して、次のような関数を定義せよ。
```
      preorder  :: Tree a -> [a]     -- 前順走査
      inorder   :: Tree a -> [a]     -- 中順走査
      postorder :: Tree a -> [a]     -- 後順走査
```
例えば、 ② preorder tree4, ③ inorder tree4, ④ postorder tree4 の結果はそれぞれ、 ② [2,1,3,4], ③ [1,2,3,4], ④ [1,4,3,2] となる。
（型クラス） Q 3.7.1 （第 3 章 p.9）
組込みのリスト型と等価なデータ型
```
  data MyList a = MyNil | MyCons a (MyList a) 
```
を、deriving を用いずに、Eq クラスと Ord クラスのインスタンスとして宣言せよ。 Ord クラスのメソッドにはいわゆる辞書式の順序を用いよ。

（クラスの定義中にデフォルトの実装が定義されているので、Eq クラスの == メソッドと Ord クラスの <= メソッドだけを定義すれば、他のメソッドの定義は自動的に生成される。）

ヒント: 次のような、リストから MyList への変換を行う関数を定義して、
```
  toMyList :: [a] -> MyList a
  toMyList []     = MyNil
  toMyList (x:xs) = MyCons x (toMyList xs) 
```
いくつかのケースをテストせよ。
```
  toMyList "abc" <= toMyList "abd"  -- True
  toMyList "ab"  <= toMyList "abc"  -- True
  toMyList "ab"  <= toMyList "a"    -- False
  toMyList "ab"  <= toMyList "ba"   -- True
```
参考にするプログラム: TypeClassExample.hs

できるだけ短く簡潔におさめて下さい。コンピュータを使う場合は \(\mathrm{\TeX}\) を推奨します。

提出〆切は、12月 07日（木）の「プログラミング言語意味論」授業開始時です。（オンラインの提出はありません。）
4Q の「プログラミング言語意味論」を受講しない人は、 1 号棟 7 F 学科事務前の香川のポストに提出してもらっても構いません。

プログラミング・パラダイム／プログラミング言語意味論のホームページ

Koji Kagawa

プログラミング・パラダイム レポート

プログラミング・パラダイム　レポート