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

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

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

1. 問3.5.6
   2つの引数 x, xs を受け取り、リスト xs から x と等しい要素を

   1. もっとも先頭に現れる一つの要素だけ取り除いたリストを返す関数 deleteOne
   2. すべて取り除いたリストを返す関数 deleteAll

   をそれぞれ定義せよ。

2. 問3.6.1
   すべての有限リスト xs について、

   1. append xs [] = xs
   2. append (append xs ys) zs = append xs (append ys zs)

   が成り立つことを xs に関する帰納法で証明せよ。 ただし append は、 プリント Ⅲ章 p.12 で定義されている関数である。

3. 問3.11.1（一部）
   Tree 型に対して、次のような関数を定義せよ。

   • preorder  :: Tree a -> [a] — 前順走査
   • inorder   :: Tree a -> [a] — 中順走査
   • postorder :: Tree a -> [a] — 後順走査

   例えば、

     tree4 :: Tree Integer
     tree4 = Branch (Branch Empty 1 Empty) 
                  2 (Branch Empty 3 (Branch Empty 4 Empty))
   

   のとき、 ③ preorder tree4, ④ inorder tree4, ⑤ postorder tree4, の結果はそれぞれ、 ③ [2,1,3,4], ④ [1,2,3,4], ⑤ [1,4,3,2], となる。

4. 問3.13.2
   非負の整数 n を受け取り、 0 ≦ x ≦ y ≦ n となるすべての x, y の組を生成する関数 foo :: Integer -> [(Integer,Integer)]を内包表記を用いて定義せよ。

   ヒント: .. を使うと簡潔になる。

5. （挑戦・非必須） 問3.14.5
   

   1. ソートされた整数のリストのなかで、3つ並びの数、 2つの同じ数を見つけてリストアップする関数 shuntsu, 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個の要素を持つ Int のソートされたリストがマージャンの清一色（チンイーソー）のアガリ形になっているかを判定する関数 chinitsu を定義せよ。

できるだけ短く簡潔におさめて下さい。 コンピュータを使う場合は ΤΕΧ を推奨します。

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