プログラミング 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 ++ ")"
これで見た目も解釈しやすい式の形で表示されるので結果の確認が楽になりました。