プログラミングHaskellをScalaで解く(その4)

引き続き、『プログラミングHaskell』の例題と練習問題をScalaで書いてみる。

Graham Hutton - プログラミングHaskell

プログラミングHaskell
Graham Hutton



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で展開しようか考えている。

  • -

追記:プログラミングHaskellをScalaで解く(その5) - DiaryExceptionを書きました。