FunctionalProgramming-爱知県立大学情报科学部.PPT

PROGRAMMING IN HASKELL Chapter 12 - The Countdown Problem * PROGRAMMING IN HASKELL プログラミングHaskell Chapter 11 - The Countdown Problem 切符番号遊び 愛知県立大学 情報科学部 計算機言語論(山本晋一郎?大久保弘崇、2013年)講義資料 オリジナルは http://www.cs.nott.ac.uk/~gmh/book.html を参照のこと * 切符番号遊び (Countdown) とは 英国のテレビで 1982 年から放送されている人気のクイズ番組 フランス版の Des Chiffres et Des Lettres がオリジナル そのクイズ番組に切符番号遊びと呼ばれる数を用いたゲームがあった * Example 1 3 7 10 25 50 以下の数 と算術演算子 + - ? ? を使って値が 765 になる式を作れるか? 765 括弧も使って良い * ゲームのルール 計算の途中結果を含む全ての数は、正の自然数(1, 2, 3, ...) であること 与えられた自然数を 2 回以上使ってはいけない テレビ番組では他のルールもあったが省略する * 先ほどの例では、以下の式は正解の一つ 780 個の正解が存在する 値を 831 に変えると、正解は無い 注意: 831 (25-10) ? (50+1) 765 = * 式を評価する 演算子を表すデータ型 Op: data Op = Add | Sub | Mul | Div 演算子を引数に適用する apply: apply :: Op ? Int ? Int ? Int apply Add x y = x + y apply Sub x y = x - y apply Mul x y = x * y apply Div x y = x `div` y * 演算子を 2 つの自然数に適用した結果が、自然数か否かを判定する述語 valid: valid :: Op ? Int ? Int ? Bool valid Add _ _ = True valid Sub x y = x y valid Mul _ _ = True valid Div x y = x `mod` y == 0 式を表すデータ型 Expr: data Expr = Val Int | App Op Expr Expr 式は、自然数そのものか、 2 つの式への演算子の適用 * eval :: Expr ? [Int] eval (Val n) = [n | n 0] eval (App o l r) = [apply o x y | x ? eval l , y ? eval r , valid o x y] 式の値を求める eval ただし、値は自然数であること: 長さ 1 の自然数リストは成功、空リストは失敗 進行 以下の順序で説明を行う 問題の定式化 正解か否かを判定する述語を定義する わかりやすいが遅いプログラム 全ての式 (解の候補) を順に生成し、正解か否か判定する 効率化の手法 無駄な解候補の生成を減らす * * 問題の形式化 リストから 0 個以上の要素を取り出す方法の順列をリストにする choices: choices :: [a] ? [[a]] For example: choices [1,2] [[],[1],[2],[1,2],[2,1]] * 式の中の全ての自然数をリストにする values: values :: Expr ? [Int] values (Val n) = [n] values (App _ l r) = values l ++ values r 式 e が、自然数リスト ns と目標の自然数 n で与えられる切符番号遊びの正解か判定する述語 solution: solution :: Expr ? [Int] ? Int ? Bool solution e ns n = elem (values e) (choices ns) eval e == [n] 実行例 * * 総当たりな解法 リストを 2 つの非空リストに分割する方法のすべてをリストにする関数 split: split :: [a] ? [([a],[a])] Fo