を推奨します。授業中に一度解いた問題も含まれていますが、改めて紙にまとめてください。
プリントの以下の問題を解いて下さい。
問 3.5.2
真偽値のリスト [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
となるように計算する。
真偽値のリスト [Bool]を 2進数と見なして、対応する整数を計算 する関数 fromBinRev :: [Bool] -> Integer を定義せよ。ただし、先 の問とは逆順に真偽値がならんでいると仮定せよ。例えば、 fronBinRev [True,True,False,True] は 1 + 2 × (1 + 2 × (0 + 2 × 1)) = 11(10) となる。
リストを昇ベキの順に表された多項式と見なし、多項式の値を計算する関数
evalPoly :: [Double] -> Double -> Double を定義せよ。例えば、
[1,2,3,4]というリストは
1 + 2 x + 3 x2 + 4 x3
という多項式と見なし、
evalPoly [1,2,3,4] 10の値は
（
1 + 2 × 10 + 3 × 102 + 4 × 103 = ）
4321 になる。
問 3.6.1
すべての有限リスト xs について、
が成り立つことを xs に関する帰納法で証明せよ。
（どこで帰納法の仮定を使用するか明示せよ。）
ただし (++) は、
プリント Ⅲ章 p.12 で定義されている関数である。
問3.10.2
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]
を定義せよ。なお、引数のリストの要素数は任意である。
ヒント: (++) を使用せよ。
問 3.13.3
非負の整数 n を受け取り、
1 ≦ x < y < z ≦ n
の範囲で、x2 + y2 = z2
となるすべての x, y, z
の組を生成する関数 chokkaku
:: Integer -> [(Integer,Integer,Integer)]を内包表記を用いて定義せよ。
例えば、chokkaku 20の値は、
[(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17),(12,16,20)]となる。
（リスト内の順番はこの例と異なっていても良い。）
（挑戦・非必須） 問 3.14.5
ソートされた整数のリストのなかで、3つ並びの数、 2つの同じ数を見つけてリストアップする関数 shuntsu（順子）, kotsu（刻子）、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 を定義せよ。 ただし、アガリ形とは、順子（3つ並びの数）または 刻子（3つの同じ数）が 4つ、対子（2つの同じ数）が 1つ、そろった形である。
できるだけ短く簡潔におさめて下さい。
コンピュータを使う場合は
ΤΕΧ を推奨します。
提出〆切は、12月 12日（木）の「プログラミング言語意味論」授業開始時です。
（オンラインの提出はありません。）
4Q の「プログラミング言語意味論」を受講しない人は、
7F 学科事務前の香川のポストに提出してもらっても構いません。