プログラミングHaskellをScalaで解く(その4)
引き続き、『プログラミングHaskell』の例題と練習問題をScalaで書いてみる。
プログラミングHaskell |
P.139 切符番号遊び(the countdown problem)
代数的データ型を用い、任意の個数の自然数で目標値を構成するための演算を発見する。制限等は全て例題と同じとする。
abstract class Op case class Add() extends Op case class Sub() extends Op case class Mul() extends Op case class Div() extends Op def valid(op:Op, x:Int, y:Int):Boolean = { op match { case Add() => true // case Add() => x <= y // for 11.5 case Sub() => x > y case Mul() => true // case Mul() => x != 1 && y != 1 && x <= y // for 11.5 case Div() => x % y == 0 // case Div() => y != 1 && x % y == 0 // for 11.5 } } def apply(op:Op, x:Int, y:Int):Int = { op match { case Add() => x + y case Sub() => x - y case Mul() => x * y case Div() => x / y } }
abstract class Expr case class Val(n:Int) extends Expr case class App(o:Op, l:Expr, r:Expr) extends Expr def values(e:Expr):List[Int] = { e match { case Val(n) => List(n) case App(o, l, r) => values(l) ::: values(r) } } def eval(e:Expr):List[Int] = { e match { case Val(n) => if(n > 0) List(n) else Nil case App(o, l, r) => for(x <- eval(l); y <- eval(r); if valid(o,x,y)) yield apply(o,x,y) } }
式の構成定義と、演算のための関数を定義した。
def subs[A](l:List[A]):List[List[A]] = { // リストの部分リスト l match { case Nil => List(Nil) case (x::xs) => { val yss = subs(xs) yss ::: yss.map(x :: _) } } } def interleave[A](x:A, l:List[A]):List[List[A]] = { // ある要素をリストに挿入した結果のリスト l match { case Nil => List(List(x)) case (y::ys) => (x::y::ys) :: interleave(x,ys).map(y :: _) } } def concat[A](xss:List[List[A]]):List[A] = xss.reduceLeft((xs, x) => xs ::: x) def perms[A](l:List[A]):List[List[A]] = { // リスト要素の順列 l match { case Nil => List(Nil) case (x::xs) => concat( perms(xs).map(interleave(x,_)) ) } }
この3つの関数については、付録Cを参照する前に、例を帰納法のように当てはめて見ると理解が早い。
def choices[A](l:List[A]):List[List[A]] = { concat( subs(l).map(perms(_)) ) } // def choices[A](l:List[A]):List[List[A]] = { for(xs <- l; ys <- perms(xs)) yield ys } // for exercise 11.7.1 def solution(e:Expr, ns:List[Int], n:Int):Boolean = { choices(ns).contains(values(e)) && eval(e) == List(n) } val e:Expr = App( Mul(), App(Add(),Val(1),Val(50)), App(Sub(),Val(25),Val(10)) )
def split[A](l:List[A]):List[(List[A],List[A])] = { l match { case Nil => Nil case List(x) => Nil case (x::xs) => (List(x),xs) :: ( for((ls,rs) <- split(xs)) yield (x::ls,rs) ) } } val ops:List[Op] = List(Add(), Sub(), Mul(), Div()) def combine(l:Expr, r:Expr):List[Expr] = { for(o <- ops) yield App(o,l,r) } def exprs(ns:List[Int]):List[Expr] = { ns match { case Nil => Nil case List(n) => List(Val(n)) case _ => for((ls,rs) <- split(ns); l <- exprs(ls); r <- exprs(rs); e <- combine(l,r)) yield e } } def solutions(ns:List[Int], n:Int):List[Expr] = { for(ns1 <- choices(ns); e <- exprs(ns1); if eval(e) == List(n)) yield e } // solutions(List(1,3,7,10,25,50), 765)
実際に、solutionsで解を得られるのだが、Scalaのインタプリタだと時間が掛かり過ぎで使いものにならない。
type Result = (Expr, Int) def combine1(lx:Result, ry:Result):List[Result] = { val (l,x) = lx val (r,y) = ry for(o <- ops; if valid(o,x,y)) yield (App(o,l,r), apply(o,x,y)) } def results(ns:List[Int]):List[Result] = { ns match { case Nil => Nil case List(n) => if(n > 0) List((Val(n), n)) else Nil case _ => for((ls,rs) <- split(ns); lx <- results(ls); ry <- results(rs); res <- combine1(lx,ry)) yield res } } def solutions1(ns:List[Int], n:Int):List[Expr] = { for(ns1 <- choices(ns); (e,m) <- results(ns1); if m == n) yield e } // solutions1(List(1,3,7,10,25,50), 765)
生成と評価の方法を変えた手段も、Haskellと同様に書け、実行速度も大きく改善した。
P.146 練習問題11.7.2
def isChoice[A](l:List[A], r:List[A]):Boolean = { def remove[A](x:A, l:List[A]):List[A] = { l match { case Nil => Nil case (y::ys) => if(x == y) ys else y :: remove(x,ys) } } l match { case Nil => true case (x::xs) => r match { case Nil => false case _ => r.contains(x) && isChoice(xs, remove(x,r)) } } }
今回はここまで。
残りは、Haskell特有機能とプログラムの一般的な話なので、どうScalaで展開しようか考えている。
- -