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

今日は総当たり法の写経をしました。

リスト内包表記が頻繁に使われるということ以外そんなに目新しいこともないですね。再帰を使って書くと楽だと感じられるようになってきました。しかし時間はとてもかかります。

ただ Expr が Show を実装してないのでそのままだと ghci で結果をチェックできません。deriving Show を Op と Expr の宣言に付けておきました。

split :: [a] -> [([a],[a])]
split [] = []
split [_] = []
split (x:xs) = ([x], xs) : [(x:ls,rs) | (ls, rs) <- split xs]

ops :: [Op]
ops = [Add, Sub, Mul, Div]

combine :: Expr -> Expr -> [Expr]
combine l r = [App o l r | o <- ops]

exprs :: [Int] -> [Expr]
exprs [] = []
exprs [n] = [Val n]
exprs ns = [e | (ls, rs) <- split ns,
                l <- exprs ls,
                r <- exprs rs,
                e <- combine l r]

solutions ns n = [e | nsp <- choices ns,
                      e <- exprs nsp,
                      eval e == [n] ]