プログラミング Haskell 第11章 切符番号遊び その4

今日は 11.5 「代数的な性質をいかす」ということで、交換法則(x+y=y+x)と単位元(x*1=x, x/1=x と結果が変わらない)の性質を考慮して同一の式と見做せるものを除外することでより効率的な探索をするようにしました。

といっても変更するのは式を受けつけるかどうか判定する valid を以下のように変更しただけです。

valid :: Op -> Int -> Int -> Bool
valid Add x y = x <= y
valid Sub x y = x > y
valid Mul x y = x /= 1 && y /= 1 && x <= y
valid Div x y = y /= 1 && x `mod` y == 0

みつかる式の数自体減るので当然ですがまた速くなりました。

続いて練習問題もやります。

• 11-1)

choices をリスト内包表現で。リストのリストを concat のかわりに展開するのは生成子を連ねるだけでいいですね。

choices :: [a] -> [[a]]
choices xs = [y | x <- subs xs, y <- perms x]

• 11-2)

問題文には明示されていなかったので、最初の引数のリストの要素が2つめの引数のリストの要素の部分集合になっていたら True を返すことにして、実装上の都合で最初が空リストなら True になるようにしています。

isChoice :: Eq a => [a] -> [a] -> Bool
isChoice [] _ = True
isChoice xs [] = False
isChoice xs (y:ys) = isChoice (eliminate xs y) ys where
                       eliminate xs y = [x | x <- xs, x /= y]

• 11-3)

split が空リストを許容するというのは引数ではなくて結果に ([], [...]) みたいなタプルも許すという意味だと思います。
この時空リストは split を呼ぶ exprs では結果に影響せず無駄な処理が増えるだけなので、パフォーマンスが悪化するだけだと思います。

• 11-4 は ghci でチェックしてみるだけなので省きます。

• 11-5)

valid を以下のように変更します。

valid :: Op -> Int -> Int -> Bool
valid Add x y = x <= y
valid Sub x y = True
valid Mul x y = x /= 1 && y /= 1 && x <= y
valid Div x y = y /= 1 && x `mod` y == 0

整数に拡張するということは負の値を許容するということですが、 Sub の条件が変化するだけですね。

• 11-6 も省きます

11章はここまでです。次は 12章「遅延評価」です。Haskell の大きな特徴のひとつである遅延評価がトピックなので期待です。