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

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

プログラミングHaskell
Graham Hutton

P.119 型宣言

typeによって型に別名を与える手段としての、型宣言の手法は既に示した。

type String = List[Char]
type Pos = (Int, Int)
type Board = List[Pos]

但し、Haskellと同様、再帰を扱うことは出来ない。

scala> type Tree= (Int, List[Tree])
<console>:4: error: illegal cyclic reference involving type Tree
       type Tree= (Int, List[Tree])
                             ^

Haskellと同様、型宣言を多相的にすることが出来る。

type Parser[A] = String => List[(A, String)]

type Assoc[K, V] = List[(K, V)]
def find[K,V](k:K, t:Assoc[K,V]):V = (for((k1, v) <- t; if k == k1) yield v).head

P.120 新しい型宣言

新しい型を宣言するには、abstract classとそれを継承したcase classを用いる。一般に、代数的データ型と呼ばれるものになる。

abstract class Move
case class Left() extends Move
case class Right() extends Move
case class Up() extends Move
case class Down() extends Move

def move(m:Move, p:Pos):Pos = {
    m match {
        case Left() => (p._1 - 1, p._2)
        case Right() => (p._1 + 1, p._2)
        case Up() => (p._1, p._2 - 1)
        case Down() => (p._1, p._2 + 1)
    }
}

def moves(ml:List[Move], p:Pos):Pos = {
    ml match {
        case Nil => p
        case (m::ms) => moves(ms, move(m, p))
    }
}

def flip(m:Move):Move = {
    m match {
        case Left() => Right()
        case Right() => Left()
        case Up() => Down()
        case Down() => Up()
    }
}

Moveが型コンストラクタに当たり、Left()/Right()/Up()/Down()がデータコンストラクタに当たる。ここのデータコンストラクタは単に名前の集合として扱えるので、『ふつうのHaskellプログラミング』でいう「列挙型スタイル」に該当する。

データコンストラクタは case class により作ることから分かるように、match-caseで用いるために宣言するのが一般的になる。

ところで、Haskellと同じように書こうとして、データコンストラクタの空括弧()を省略して書くと、warningが出る。

$ scala
scala> case class Left extends Move
warning: there were deprecation warnings; re-run with -deprecation for details
defined class Left
<C-d>
$ scala -deprecation
scala> case class Left extends Move
<console>:1: warning: case classes without a parameter list have been deprecated;
use either case objects or case classes with `()' as parameter list.
       case class Left extends Move
                       ^
<console>:1: warning: case classes without a parameter list have been deprecated;
use either case objects or case classes with `()' as parameter list.
case class Left extends Move
                ^
<console>:5: warning: case classes without a parameter list have been deprecated;
use either case objects or case classes with `()' as parameter list.
       case class Left extends Move
                       ^
defined class Left

『ふつうのHaskellプログラミング』の「共用体スタイル」もScalaで書ける。

abstract class Shape
case class Circle(radius:Double) extends Shape
case class Rect(length:Double, height:Double) extends Shape

def square(n:Double):Shape = Rect(n,n)
def area(s:Shape):Double = {
    s match {
        case Circle(r) => Math.Pi * Math.pow(r, 2)
        case Rect(x, y) => x * y
    }
}

HaskellのMaybe a型は、Scalaでは abstract class Option[A]として定義されている。

これが『ふつうのHaskellプログラミング』の「構造体スタイル」に当たる。

abstract class MyOption[A]  // == Maybe a
case class MySome[A](e:A) extends MyOption[A]   // == Just a
case class MyNone extends MyOption[Nothing]     // == Nothing

P.122 再帰型

typeによる型宣言と異なり、{abstract, case} classによる新しい型宣言は再帰的に出来る。

abstract class Nat
case class Zero() extends Nat
case class Succ(n:Nat) extends Nat

def nat2int(m:Nat):Int = {
    m match {
        case Zero() => 0
        case Succ(n) => 1 + nat2int(n)
    }
}

def int2nat(i:Int):Nat = {
    i match {
        case 0 => Zero()
        case _ => Succ(int2nat(i - 1))
    }
}

// def add(m:Nat, n:Nat):Nat = int2nat(nat2int(m) + nat2int(n))

def add(m:Nat, n:Nat):Nat = {
    m match {
        case Zero() => n
        case Succ(mm) => Succ(add(mm,n))
    }
}

自然数の加算をSuccの再帰構造で表現出来ることが分かる。

次に、型に関する演習の定番である、木構造を扱う。

abstract class Tree
case class Leaf(i:Int) extends Tree
case class Node(l:Tree, i:Int, r:Tree) extends Tree

val t:Tree = Node(Node(Leaf(1), 3, Leaf(4)), 5, Node(Leaf(6), 7, Leaf(9)))

def occurs(m:Int, t:Tree):Boolean = {
    t match {
        case Leaf(n) => m == n
        case Node(l,n,r) => m == n || occurs(m,l) || occurs(m,r)
    }
}

def flatten(t:Tree):List[Int] = {
    t match {
        case Leaf(n) => List(n)
        case Node(l,n,r) => flatten(l) ::: List(n) ::: flatten(r)
    }
}

P.126 恒等式検査

P.138 練習問題10.8.5も同時に解く。

abstract class Prop
case class Const(b:Boolean) extends Prop
case class Var(c:Char) extends Prop
case class Not(p:Prop) extends Prop
case class And(p1:Prop, p2:Prop) extends Prop
case class Imply(p1:Prop, p2:Prop) extends Prop
// for exercise 10.8.5
case class Or(p1:Prop, p2:Prop) extends Prop
case class Equal(p1:Prop, p2:Prop) extends Prop

val p1:Prop = And(Var('A'), Not(Var('A')))
val p2:Prop = Imply(And(Var('A'), Var('B')), Var('A'))
val p3:Prop = Imply(Var('A'), And(Var('A'), Var('B')))
val p4:Prop = Imply(And(Var('A'), Imply(Var('A'), Var('B'))), Var('B'))

type Subst = Assoc[Char, Boolean]

def eval(s:Subst, p:Prop):Boolean = {
    p match {
        case Const(b) => b
        case Var(x) => find(x, s)
        case Not(p) => !(eval(s, p))
        case And(p1, p2) => eval(s, p1) && eval(s, p2)
        case Imply(p1, p2) => eval(s, p1) <= eval(s, p2)
        // for exercise 10.8.5
        case Or(p1, p2) => eval(s, p1) || eval(s, p2)
        case Equal(p1, p2) => eval(s, p1) == eval(s, p2)
    }
}

def vars(p:Prop):List[Char] = {
    p match {
        case Const(b) => Nil
        case Var(x) => List(x)
        case Not(p) => vars(p)
        case And(p1, p2) => vars(p1) ::: vars(p2)
        case Imply(p1, p2) => vars(p1) ::: vars(p2)
        // for exercise 10.8.5
        case Or(p1, p2) => vars(p1) ::: vars(p2)
        case Equal(p1, p2) => vars(p1) ::: vars(p2)
    }
}

def bools(n:Int):List[List[Boolean]] = {
    n match {
        case 0 => List(Nil)
        case _ => bools(n -1).map(false :: _) ::: bools(n - 1).map(true :: _)
    }
}

def rmdups[A](l:List[A]):List[A] = {  // P.116
    l match {
        case Nil => Nil
        case (x::xs) => x :: rmdups(xs.filter(_ != x))
    }
}

def substs(p:Prop):List[Subst] = {
    val vs = rmdups(vars(p))
    bools(vs.length).map(vs.zip(_))
}

def isTaut(p:Prop):Boolean = (for(s <- substs(p)) yield eval(s, p)).reduceLeft(_ && _)

P.131 仮想マシン

まずは評価優先順位の無いマシン。P.138 練習問題10.8.7も解く。

abstract class Expr
case class Val(n:Int) extends Expr
case class Add(e1:Expr, e2:Expr) extends Expr
// for exercise 10.8.7
case class Mult(e1:Expr, e2:Expr) extends Expr

def value(e:Expr):Int = {
    e match {
        case Val(n) => n
        case Add(e1, e2) => value(e1) + value(e2)
        case Mult(e1, e2) => value(e1) * value(e2)
    }
}

次に、より正確な数式処理仮想マシンを付け加える。P.138 練習問題10.8.7も解く。

object VirtualMachine {

    abstract class Op
    // case class EVAL(e:Expr) extends Op
    // for exercise 10.8.7
    case class EVALA(e:Expr) extends Op
    case class EVALM(e:Expr) extends Op
    case class ADD(n:Int) extends Op
    // for exercise 10.8.7
    case class MULT(n:Int) extends Op
    type Cont = List[Op]

    def eval(e:Expr, c:Cont):Int = {
        e match {
            case Val(n) => exec(c, n)
            case Add(e1, e2) => eval(e1, EVALA(e2)::c)
            case Mult(e1, e2) => eval(e1, EVALM(e2)::c)
        }
    }

    def exec(c:Cont, n:Int):Int = {
        c match {
            case Nil => n
            case (EVALA(y)::cc) => eval(y, ADD(n)::cc)
            case (EVALM(y)::cc) => eval(y, MULT(n)::cc)
            case (ADD(m)::cc) => exec(cc, (m + n))
            case (MULT(m)::cc) => exec(cc, (m * n))
        }
    }

    def value(e:Expr):Int = eval(e, Nil)
}

ここで、object VirtualMachineを導入した。それはevalとexecが再帰関数となっており、トップレベルにこの2つの関数を書いた場合、関数未定義エラーとなるからである。object あるいは class のメソッドとすると、この問題は解決する。

P.137 練習問題10.8.3 と 10.8.4

ヒントを活用して、leaves関数とhalve関数をローカル関数として定義している。

abstract class Tree
case class Leaf(n:Int) extends Tree
case class Node(l:Tree, r:Tree) extends Tree

def balanced(t:Tree):Boolean = {
    def leaves(t:Tree):Int = {
        t match {
            case Leaf(n) => 1
            case Node(l, r) => leaves(l) + leaves(r)
        }
    }
    t match {
        case Leaf(n) => true
        case Node(l,r) => ((leaves(l) - leaves(r)).abs <= 1) && balanced(l) && balanced(r)
    }
}

def balance(ns:List[Int]):Tree = {
    def halve[A](l:List[A]):(List[A], List[A]) = l.splitAt(l.length / 2)
    ns match {
        case List(x) => Leaf(x)
        case _ => { val (xs,ys) = halve(ns); Node(balance(xs), balance(ys)) }
    }
}

今回はここまで。

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