2021年度「プログラミング・パラダイム テスト」

解答上、その他の注意事項

• ノート・プリント・参考書などは持ち込み可である。

• 携帯電話などの通信機能を持つものは持ち込み不可である。

• プログラミング問題を解答するときは、 ネットワークに接続して WWW を閲覧しても良いが、掲示板、チャット、 メールなどで生身の人間と通信することは禁じる。

• テストの配点は50点である。 合格はレポートの得点を加点して、100 点満点中 60 点以上とする。

問題

以下の問に答えよ。

Ⅰ. (Haskell プログラミング問題)

1. （必須）Haskell:
   提出ファイル名: Foo.hs

   引数として与えられる整数のリストの要素のなかに現れる 奇数がすべて正の数であるかどうかを返す関数 foo :: [Integer] -> Bool

   を定義せよ。

   例えば、foo [12,5,-2,0] は True であり、 foo [8,3,2,-7,1] は False であり、 foo [-2,-4,2] は True である。

   この問では map, filter, foldl, foldr などのリストに関するライブラリ関数や内包表記を使わず、 if 〜 then 〜 else 〜 式、算術演算子、 論理演算子、比較演算子、パターンマッチング、ガード、再帰のみを使って定義せよ。

   また、Haskell で“余り”を表す算術演算子 は `mod` である。例えば (-7) `mod` 4（あるい は mod (-7) 4）の値は 1 である。また、`rem` という演算子もあり、オペランドのどちらかが負の ときに `mod` と結果が異なる。例えば、(-7) `rem` 4（あるいは rem (-7) 4）の値は -3 である。

   また、Haskell の“等しくない”を表す演算子は /= である。

2. （必須）Haskell:
   提出ファイル名: Bar.hs

   正の整数 \(n\) を引数として受け、 \(0 \le x \le n,\; x \le y \le 3 x\) を満たす 整数の組 \((x,y)\)で、\(x^2 + y^2\) が 3 で割って 1 余るものを列挙する関数

   bar :: Integer -> [(Integer,Integer)]

   を（リストの内包表記を用いて）定義せよ。

   例えば、bar 2 は [(1,3),(2,3),(2,6)]、bar 3 は [(1,3),(2,3),(2,6),(3,4),(3,5),(3,7),(3,8)] で、 bar 5 は [(1,3),(2,3),(2,6),(3,4),(3,5),(3,7),(3,8),(4,6),(4,9),(4,12),(5,6),(5,9),(5,12),(5,15)] となる。
   （リストの要素の順番はこの通りでなくても良い。）

   なお、\(m\) から \(n\) まで（ただし \(m \le n\)）の整数のリストは、 [m..n] という式で得ることができる。例えば、[0..5] は [0,1,2,3,4,5] である。

   また、Haskell で“余り”を表す算術演算子は `mod` である。例えば 7 `mod` 4（あるいは mod 7 4）の値は 3 である。

Ⅱ. (Haskell プログラミング問題)

1. （選択）Haskell:
   提出ファイル名: Baz.hs

   整数のペアのリストを受け取り、ペアの第 1 成分が第 2 成分より等しいか大きい要素の、第 1 成分の和を求める関数

   baz :: [(Integer,Integer)] -> Integer

   を定義せよ。

   例えば、baz [(2,2),(3,4),(7,0)] は 9 であり、 baz [(-1,-3),(2,4),(5,2)] は 4 であり、 baz [(2,4),(1,2)] は 0 である。

   この問では、再帰呼出しを直接使わずに、 map, filter, foldl, foldr などの標準ライブラリー関数を積極的に使用して定義せよ。

2. （選択）Haskell:
   提出ファイル名: Qux.hs

   正の整数 \(n\) を引数として受け、 \(0 \le x \le y \le n\) を満たす整数の組で \(x + y\) が偶数となるものを列挙する関数

   qux :: Integer -> [(Integer,Integer)]

   を、この問題ではリストの内包表記を用いずに定義せよ。

   なお、map, filter などの標準ライブラリー関数や、以下の unit, bind （標準ライブラリーには含まれていない）は用いてもよい。

   unit :: a -> [a] -- 要素数 1 のリストを返す unit a = a : [] bind :: [a] -> (a -> [b]) -> [b] bind [] _ = [] bind (x:xs) f = (f x) ++ (bind xs f)

   例えば、qux 2 は [(0,0),(0,2),(1,1),(2,2)]、qux 3 は [(0,0),(0,2),(1,1),(1,3),(2,2),(3,3)] で、 qux 4 は [(0,0),(0,2),(0,4),(1,1),(1,3),(2,2),(2,4),(3,3),(4,4)] となる。
   （リストの要素の順番はこの通りでなくても良い。）

   なお、\(m\) から \(n\) まで（ただし \(m \le n\)）の整数のリストは、 [m..n] という式で得ることができる。例えば、[0..5] は [0,1,2,3,4,5] である。

   また、Haskell で“余り”を表す算術演算子は `mod` である。例えば 7 `mod` 4（あるいは mod 7 4）の値は 3 である。