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

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


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

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

    ヒント:
  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 型に対して、次のような関数を定義せよ。

    例えば、

      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 の範囲で x2 + y2 = z2 となるすべての x, y, z の組を生成する関数 chokkaku :: Integer -> [(Integer, Integer, Integer)] を内包表記を用いて定義せよ。

  6. (挑戦・非必須) 問3.14.2

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

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

プログラミング言語特論のホームページ
Koji Kagawa