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

今日は 11.4 「生成と評価の方法を変える」ということで生成する式の枝刈りを含める部分の写経しました。

今度の combine' は結果が自然数にならない式を除外するので高速になりました。今回もリスト内包表記をばりばり使ってます。

type Result = (Expr, Int)

combine' :: Result -> Result -> [Result]
combine' (l,x) (r,y) = [(App o l r, apply o x y) | o <- ops,
                                                   valid o x y]

results :: [Int] -> [Result]
results []  = []
results [n] = [(Val n, n) | n > 0]
results ns = [res | (ls, rs) <- split ns,
                    lx <- results ls,
                    ry <- results rs,
                    res <- combine' lx ry]

solutions' :: [Int] -> Int -> [Expr]
solutions' ns n = [e | ns' <- choices ns,
                       (e,m) <- results ns',
                       m == n ]

あと結果の式が deriving Show のままだととても読みにくいので show を実装してみました。

data Op = Add | Sub | Mul | Div
instance Show Op where
  show Add = "+"
  show Sub = "-"
  show Mul = "*"
  show Div = "/"

data Expr = Val Int | App Op Expr Expr

instance Show Expr where
  show (Val n) = show n
  show (App op l r) = "(" ++ show l ++ " " ++ show op ++ " " ++ show r ++ ")"

これで見た目も解釈しやすい式の形で表示されるので結果の確認が楽になりました。