![切符番号選びのルール
[Int] -> [(Expr, Int)]
整数のリストから、四則演算で作られる式
とその答えのリストが作られる
欲しい数は、その中に「ある」か「ない」
かのどちらか
12](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-12-320.jpg)
![切符番号選び
data Expr = Val Int | App Op Expr Expr
--式
eval :: Expr -> [Int]
--式の評価 (実質Maybe)
--整数の組み合わせを作るため、次から
色々関数を定義します
--Val は適宜省略します
15](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-15-320.jpg)
![切符番号選び
subs :: [a] -> [[a]]
subs [] = [[]]
subs (x:xs) = yss ++ map (x:) yss
where yss = subs xs
--リストの全ての部分集合を作る
--集合のべき乗(2^X)
--subs [1, 2] = [[], [2], [1], [1,2]]
16](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-16-320.jpg)
![切符番号選び
perms :: [a] -> [[a]]
perms [] = [[]]
perms (x:xs) = concat (map (interleave x)
(perms xs))
--集合のpermutation(並び替え)
17](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-17-320.jpg)
![切符番号選び
choices :: [a] -> [[a]]
choices xs = concat (map perms (subs xs))
--全ての部分集合を含んだ順列を作る
18](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-18-320.jpg)
![切符番号選び
solution :: Expr -> [Int] -> Int -> Bool
solution e ns n = elem (values e) (choices ns)
&& eval e == [n]
--式eを構成する数値がリストnsに含まれて
いる かつ 式eを評価すると値nになる
19](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-19-320.jpg)
![切符番号選び
全ての解答を探す関数solutionsを作りたい
solutions :: [Int] -> Int -> [Expr]
--solutions (数のリスト) 正解値-> 数のリスト
が生成元の式で、評価すると正解値になる
もの
-- solutions [1,2,3] 3 = [Val 3, Add 1 2, Add 2 1]
20](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-20-320.jpg)
![切符番号選び
split :: [a] -> [([a],[a])]
split [] = []
split [_] = []
split (x:xs) = ([x],xs):[(x:ls,rs)|(ls,rs) <- split xs]
--集合を全ての場所で２つに割る
-- split [1,2,3,4] = [([1],[2,3,4]), ([1,2],[3,4]),
([1,2,3],[4])]
21](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-21-320.jpg)
![切符番号選び
split :: [a] -> [([a],[a])]
split [] = []
split [_] = []
split (x:xs) = ([x],xs):[(x:ls,rs)|(ls,rs) <- split xs]
--集合を全ての場所で２つに割る
-- split [1,2,3,4] = [([1],[2,3,4]), ([1,2],[3,4]),
([1,2,3],[4])]
22](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-22-320.jpg)
![切符番号選び
combine :: Expr -> Expr -> [Expr]
combine l r = [App o l r | o<-ops]
ops :: [Op]
ops = [Add,Sub,Mul,Div]
--2つの式にすべての演算を適用
--[Add 式1 式2, Sub 式1 式2, Mul 式1 式2, Div
式1 式2]
23](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-23-320.jpg)
![切符番号選び
exprs :: [Int] -> [Expr]
exprs [n] = [Val n]
exprs ns = [e | (ls, rs) <- split ns, l<-exprs ls, r<-
exprs rs, e<-combine l r]
--数値のリストを全て一回ずつ使った式す
べてを返す (本当はこれは遅い(後述) )
24](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-24-320.jpg)
![完成
solutions :: [Int] -> Int -> [Expr]
solutions ns n = [e|ns' <- choices ns, e<-exprs
ns', eval e==[n]]
--与えられた数を生成する式をすべて探す
が、遅い… (4分 @ モダンなマシン)
(Sub 1 2) <- こういう式が途中に出たら打ち
切りたい
25](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-25-320.jpg)
![高速化
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]
--2つのExprに対して、validな演算すべてを
適用
26](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-26-320.jpg)
![高速化
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]
--数値のリストを、すべて使った式を作っ
て評価する
-- [1,2] -> [(Add 1 2, 3), (Mul 1 2, 2)]
27](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-27-320.jpg)
![高速化
solutions' :: [Int] -> Int -> [Expr]
solutions' ns n = [e|ns' <- choices ns, (e,m)<-
results ns' , m==n]
--式を作るうえでvalidでない演算は早めに打
ち切る
--10数秒 @ モダンなマシン
28](https://image.slidesharecdn.com/random-111202222809-phpapp02/85/Programming-Haskell-Chapter-11-28-320.jpg)
More Related Content
What's hot (18)
Viewers also liked (8)
Similar to Programming Haskell Chapter 11 切符番号選び (20)
Recently uploaded (15)
Programming Haskell Chapter 11 切符番号選び
- 1. プログラミングHaskell 11章 切符番号選び @dekosuke
- 2. 概略 ? 数字遊び @ twitter ? 切符番号選び ? 切符番号選びの高速化 2
- 3. 数字遊び ? ランダムな４つの数字から、10を作ろう！ 3
- 4. 数字遊び ? Easy! => 3+2+7-2 4
- 6. 数字遊び ? 累乗で解決！ 6
- 7. 数字遊び さらに難易度上昇 7
- 8. 数字遊び ? 絶対値とルートで解決！？??? 8
- 9. 数字遊び 絶対値とルートで解決！？??? 9
- 10. 数字遊び ? 上のTwitterの数字遊びは、使える演算が明 示されていないあいまいさがある（それ が面白さにつながる点も） ? 使える演算をちゃんと決めよう！ 10
- 11. 切符番号選びのルール ? 正数のリストが与えられる ? リストから好きな数だけ選んで正数を使 い、四則演算を行える ? 計算途中で０以下になってはいけない 11
- 12. 切符番号選びのルール [Int] -> [(Expr, Int)] 整数のリストから、四則演算で作られる式 とその答えのリストが作られる 欲しい数は、その中に「ある」か「ない」 かのどちらか 12
- 14. 切符番号選び data Op = Add | Sub | Mul | Div --演算 valid :: Op -> Int -> Int -> Bool apply :: Op -> Int -> Int -> Int --演算が正当かどうかと、演算を行う関数 --Maybe?... 14
- 15. 切符番号選び data Expr = Val Int | App Op Expr Expr --式 eval :: Expr -> [Int] --式の評価 (実質Maybe) --整数の組み合わせを作るため、次から 色々関数を定義します --Val は適宜省略します 15
- 16. 切符番号選び subs :: [a] -> [[a]] subs [] = [[]] subs (x:xs) = yss ++ map (x:) yss where yss = subs xs --リストの全ての部分集合を作る --集合のべき乗(2^X) --subs [1, 2] = [[], [2], [1], [1,2]] 16
- 17. 切符番号選び perms :: [a] -> [[a]] perms [] = [[]] perms (x:xs) = concat (map (interleave x) (perms xs)) --集合のpermutation(並び替え) 17
- 18. 切符番号選び choices :: [a] -> [[a]] choices xs = concat (map perms (subs xs)) --全ての部分集合を含んだ順列を作る 18
- 19. 切符番号選び solution :: Expr -> [Int] -> Int -> Bool solution e ns n = elem (values e) (choices ns) && eval e == [n] --式eを構成する数値がリストnsに含まれて いる かつ 式eを評価すると値nになる 19
- 20. 切符番号選び 全ての解答を探す関数solutionsを作りたい solutions :: [Int] -> Int -> [Expr] --solutions (数のリスト) 正解値-> 数のリスト が生成元の式で、評価すると正解値になる もの -- solutions [1,2,3] 3 = [Val 3, Add 1 2, Add 2 1] 20
- 21. 切符番号選び split :: [a] -> [([a],[a])] split [] = [] split [_] = [] split (x:xs) = ([x],xs):[(x:ls,rs)|(ls,rs) <- split xs] --集合を全ての場所で２つに割る -- split [1,2,3,4] = [([1],[2,3,4]), ([1,2],[3,4]), ([1,2,3],[4])] 21
- 22. 切符番号選び split :: [a] -> [([a],[a])] split [] = [] split [_] = [] split (x:xs) = ([x],xs):[(x:ls,rs)|(ls,rs) <- split xs] --集合を全ての場所で２つに割る -- split [1,2,3,4] = [([1],[2,3,4]), ([1,2],[3,4]), ([1,2,3],[4])] 22
- 23. 切符番号選び combine :: Expr -> Expr -> [Expr] combine l r = [App o l r | o<-ops] ops :: [Op] ops = [Add,Sub,Mul,Div] --2つの式にすべての演算を適用 --[Add 式1 式2, Sub 式1 式2, Mul 式1 式2, Div 式1 式2] 23
- 24. 切符番号選び exprs :: [Int] -> [Expr] exprs [n] = [Val n] exprs ns = [e | (ls, rs) <- split ns, l<-exprs ls, r<- exprs rs, e<-combine l r] --数値のリストを全て一回ずつ使った式す べてを返す (本当はこれは遅い(後述) ) 24
- 25. 完成 solutions :: [Int] -> Int -> [Expr] solutions ns n = [e|ns' <- choices ns, e<-exprs ns', eval e==[n]] --与えられた数を生成する式をすべて探す が、遅い… (4分 @ モダンなマシン) (Sub 1 2) <- こういう式が途中に出たら打ち 切りたい 25
- 26. 高速化 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] --2つのExprに対して、validな演算すべてを 適用 26
- 27. 高速化 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] --数値のリストを、すべて使った式を作っ て評価する -- [1,2] -> [(Add 1 2, 3), (Mul 1 2, 2)] 27
- 28. 高速化 solutions' :: [Int] -> Int -> [Expr] solutions' ns n = [e|ns' <- choices ns, (e,m)<- results ns' , m==n] --式を作るうえでvalidでない演算は早めに打 ち切る --10数秒 @ モダンなマシン 28
- 29. 高速化 さらに工夫を… ?足し算や掛け算は可換なので (Add 2 3) と (Add 3 2)は片方でいい ?(Mul x 1) は自明なので除去 これらの条件をvalidに入れ込む 29