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

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


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

  1. 問 2.5.4 (第 2 章 p.13)
    2つの引数 x, xs を受け取り、リスト xs から x と等しい要素を

    をそれぞれ定義せよ。

  2. 問 2.6.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 で定義が示されている関数である。

  3. Q 2.10.2 (第 2 章 p.19)
    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] を定義せよ。なお、引数のリストの要素数は任意である。

    ヒント: (++) を使用せよ。

  4. 問 2.12.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)]
    を内包表記を用いて定義せよ。

  5. (挑戦・非必須)(ナイト巡回) 問 2.13.4 (第 2 章 p.28)
    ナイトは、右の図 move of knight の中央のマスから○印のマスへ 移動できるチェスのコマである。5 × 5マスのチェス盤で、あるマス (例えば、左上隅)から始めてすべてのマスを 1 回ずつ訪れる経路を求めるプログラムを作成せよ。

  6. (代数的データ型) 問 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] となる。

  7. (型クラス) 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}\) link を推奨します。

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

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