プログラミング言語特論 第1回レポート

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

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

1. 問3.5.3
   真偽値のリスト [Bool] を 2進数と見なして、対応する整数を計算 する関数 fromBin :: [Bool] -> Integer を定義せよ。例えば、 fromBin [True, True]は 3、 fromBin [True, False, True, False] は 10になる。

   ヒント:
   • 引数の数を一つ増やした補助関数が必要になる。
   • ホーナーの方法を使う。例えば fromBin [True, False, True, False] は ((1 × 2 + 0) × 2 + 1) × 2 + 0、 fromBin [True, True, False, True] は ((1 × 2 + 1) × 2 + 0) × 2 + 1 となるように計算する。

2. 問3.5.4
   真偽値のリスト [Bool]を 2進数と見なして、 対応する整数を計算する関数 fromBinRev :: [Bool] -> Integer を定義せよ。ただし、先の問とは逆順に真偽値がならんでいると仮定せよ。

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

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

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

4. 問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], となる。

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

6. （挑戦・非必須） 問3.14.2
   

   • ソートされた整数のリストのなかで、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]]
     

   • 14個の要素を持つIntのソートされたリストがマージャンの清一色（チンイーソー）のアガリ形になっているかを判定する関数 chinitsuを定義せよ。

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

提出〆切は、1月12日の授業開始時です。（オンラインの提出はありません。）