10/8日(土曜日) Scala 関西があり、そこで「Scalaで学ぶ数学」で登壇した。
そこで、話した感想と、話し切れなかったことについて記事にしておく。
1 + 1 = 2をScalaの型で表現する
話した内容としては、まず、Scalaで1 + 1 = 2の記述をScalaの型によって表現することである。
その後もう、「50%の勝率でn試合すると(n/2)勝する確率」についてを、少しだけしゃべったが時間が無いのでさらっと流した。(これについては後述しておく)
1 + 1 = 2で話たコードの全体だけ記しておく。
object Peano{
sealed class Number
sealed class Zero extends Number
sealed class Succ[N <: Number] extends Number
type One = Succ[Zero]
type Two = Succ[Succ[Zero]]
type Three = Succ[Succ[Succ[Zero]]]
sealed class Eq[S <: Number,T <: Number]
sealed class Add[S <: Number,T <: Number] extends Number
// m = m => m = m
def reflective[S <: Number]
: Eq[S,S] => Eq[S,S]
= (s) => new Eq[S,S]
// m = n => n = m
def symmetric[S <: Number,T <: Number]
: Eq[S,T] => Eq[T,S]
= (s) => new Eq[T,S]
// s = t => t = r => s = r
def transitive[S <: Number,T <: Number,R <: Number]
: Eq[S,T] => Eq[T,R] => Eq[S,R]
= (s) => (t) => new Eq[S,R]
// s = t => succ(s) = succ(t)
def axiom1[S <: Number,T <: Number]
:Eq[S,T] => Eq[Succ[S], Succ[T]]
= (s) => new Eq[Succ[S], Succ[T]]
// s + 0 = s
def axiom2[S <: Number]
: Eq[Add[S,Zero],S]
= new Eq[Add[S,Zero], S]
// s + succ(t) = succ(s + t)
def axiom3[S <: Number, T <: Number]
: Eq[Add[S, Succ[T]], Succ[Add[S, T]]]
= new Eq[Add[S, Succ[T]], Succ[Add[S, T]]]
val proof1 :
Eq[
Add[Succ[Zero],Succ[Zero]],
Succ[
Add[Succ[Zero],Zero]
]
]
= axiom3[Succ[Zero], Zero]
val proof2 :
Eq[
Add[Succ[Zero], Zero],
Succ[Zero]
]
= axiom2[Succ[Zero]]
val proof3 :
Eq[
Succ[Add[Succ[Zero], Zero]],
Succ[Succ[Zero]]
]
= axiom1(proof2)
val proof4 :
Eq[
Add[Succ[Zero], Succ[Zero]],
Succ[Succ[Zero]]
] = transitive(proof1)(proof3)
val proof1_ : Eq[Add[One, One],
Succ[Add[One, Zero]]]
= axiom3[One, Zero]
val proof2_ : Eq[
Add[One, Zero],
One
] = axiom2[One]
val proof3_ : Eq[
Succ[Add[One, Zero]],
Two
] = axiom1(proof2_)
val proof4_ : Eq[
Add[One, One],
Two
] = transitive(proof1_)(proof3_)
}
補足： 50%の勝率でn試合すると(n/2)勝する確率
これはさらっと流したものであるが、「50%の勝率でn試合すると(n/2)勝する確率」の問題があり、これをScalaで考えるとどうなるだろうか? みたいなことについてである。これについては、時間が無く詳しく話してないため、詳しく記す。
方針
普通に、高校数学でやるような計算をそのままプログラミングしてもいいのだが、それだとつまらない。今回はやや遠回りするが、おそらく「プログラミング的」な解決を図る。
まずは、勝ち負けのパターンをプログラミングに列挙する。このとき、「勝ち負けのパターン」をプログラミングで定義し、列挙する形を取る。その後、その定義を使い、勝ち負けのパターンを列挙する。そして、そのあと集計し、確率を出して行く方式にする。
勝ちパターンをどう記述するか?
まずは、プログラミング関係なく、勝ちパターンをどのように表現するか?ということについて考えてみよう。たとえば、10勝して5勝するパターンを記述してみよう。たとえば、
○×方式
○を勝ち、×を負けとして、1 ~ 10試合までの勝ち負けを記して示す方法。
例 ： ○×○○×○×××○
勝ち試合記録方式
何試合あり、勝ったのが何試合目であるか?を記す方法
例 ： 10試合して、1,3,4,6,10試合目に勝った
こちらの方法で、記述した方がスッキリしそうだ。今回は、こちらで考えてみよう。
勝ちパターンをScalaで定義する
さて、勝ちパターンを定義して、記述して行く。
コレクションとして定義する。
まずは、勝ち試合を集めたコレクションとして定義できそうだ。とすれば、
Pattern(10)(1,3,4,6,10)
という形で記述できるようにしてみよう。最初の(10)は、試合数、(1,3,4,6,10)は勝ちパターンを記述している。
このようにすれば、このような定義になりそうだ。
object Pattern{
def apply(numRound:Int)(elems:Int*_) : Pattern =
...
}
class Pattern private (val numRound : Int, val elems : Seq[Int] ) {
...
}
new Pattern(...)とかされたくないので、Patternコンストラクタはprivateにしておき、Patternクラスのコンパニオンオブジェクトに、applyメソッドを定義して、Patternを作るようにしている。
勝ちパターンの特徴
さて、ここで勝ちパターンの特徴を考えてみよう。この2点が考えられる。
- 重複が無い
- 順番が関係ない。
勝ちパターンには重複が無い。たとえば、これとこれは同値である。
Pattern(10)(1,2,3,4) == Pattern(10)(1,2,2,3,4) // true
また、順番も関係が無い。
Pattern(10)(1,2,3,4) == Pattern(10)(4,2,3,1) // true
既存のコレクションを拡張する。
以上の特徴を見たすコレクションをそのまま実装してもいいが、せっかくScalaには豊富なコレクションライブラリが存在する。この既存のコレクションから拡張してみよう。
さて、拡張するコレクションはBitSetである。理由としては、重複が無い、順番も無いことが、共通していることがある。
scala> import scala.collection.BitSet
import scala.collection.BitSet
scala> BitSet(1,2,3) == BitSet(2,1,1,3)
res0: Boolean = true
また、○×方式にとても近い。たとえば、○×○○は、1試合、3試合、4試合が勝ったことを示すが、BitSetは1011は、3,2,0を格納するビットであり、表現方法が近い。
Immutable,Mutable版で共通するPatternトレイトを作成する.
コレクションにはImmutableなコレクションを、Mutableなコレクションが存在するが、Patternコレクションも、Immutable版と、Mutable版も実装する。どちらにも共通するTraitを作成しよう。
trait Pattern extends BitSet {
val numRound : Int
override def toString : String =
s"Pattern(${numRound})(${this mkString ","})"
override def hashCode = (super.hashCode, numRound).##
override def canEqual(other: Any) : Boolean =
other.isInstanceOf[Pattern]
override def equals(other: Any): Boolean =
other match {
case that:Pattern =>
super.equals(that) &&
(that canEqual this) &&
(this.numRound == that.numRound)
case _ => false
}
}
numRoundで試合数を取り、toStringを実装している。そして、等価性についても実装している。オブジェクトの等価性あたりは、コップ本を参照して実装しよう。
Mutable版
さて、Mutable版を実装してみる。
class Pattern private (elems: Array[Long], val numRound : Int)
extends BitSet(elems)
with SetLike[Int, Pattern]
with scala.collection.kansai.math.Pattern
with BitSetLike[Pattern]{
...
}
ここで、重要なのは、ScalaのコレクションはLikeのサフィックスが付いているトレイトである。これは 、いわゆる実装トレイトであり、このトレイトで、コレクションの「同じ結果型」にしている。SetLike[Int, Pattern]は、要素型がIntで、結果型がPatternになるような、Setの実装トレイト、BitSetLike[Pattern]は結果型がPatternになるような、BitSetの実装トレイトとなっている。
もし、たとえば、BitSetLike[Pattern]などをを拡張せずに、BitSetのみを拡張をしたら以下のようになるだろう。
// 実装トレイトを拡張しないバージョン
class Pattern private (elems: Array[Long], val numRound : Int)
extends BitSet(elems) {
....
}
Pattern(1,2,3,4) filter (_ % 2 == 0)
// BitSet(2,4)を返す
なので、BitSetLike[Pattern]を拡張しておいて、BitSetのコレクション実装の再利用しながら、Patternを拡張する。詳しくはコップ本を参照してほしい。
さて、もうすこし実装の詳細に入ってみよう。まずは、CanBuildFrom周りも確認してみよう。
object Pattern {
...
def newBuilder(numRound : Int) : Builder[Int, Pattern] = new GrowingBuilder[Int, Pattern](empty(numRound))
implicit def canBuildFrom: CanBuildFrom[Pattern, Int, Pattern] = new CanBuildFrom[Pattern, Int, Pattern] {
def apply(from: Pattern) = newBuilder(from.numRound)
def apply() = newBuilder(0)
}
}
実装トレイトの他に、ScalaはCanBuildFromによって、「同じ結果型」を維持している。詳しくはコップ本などを参照してほしい。
BitSetLikeの拡張周りも見てみよう。
object Pattern {
....
def fromBitMaskNoCopy(elems: Array[Long], numRounds:Int) : Pattern =
new Pattern(elems, numRounds)
...
}
class Pattern private (elems: Array[Long], val numRound : Int)
extends BitSet(elems)
with SetLike[Int, Pattern]
with scala.collection.kansai.math.Pattern
with BitSetLike[Pattern]{
...
override def fromBitMaskNoCopy(elems: Array[Long]) : Pattern =
Pattern.fromBitMaskNoCopy(elems, numRound)
...
}
BitSetLike[Pattern]の拡張のため、BitSetのfromBitMaskNoCopyをオーバーライドしている。
その他の実装を見てみよう。
class Pattern private (elems: Array[Long], val numRound : Int)
extends BitSet(elems)
with SetLike[Int, Pattern]
with scala.collection.kansai.math.Pattern
with BitSetLike[Pattern]{
...
override def add(elem:Int) : Boolean = {
require(elem <= numRound, s"pattern element must be <= $numRound")
super.add(elem)
}
override def toImmutable =
scala.collection.immutable.math.kansai.Pattern.fromBitMaskNoCopy(elems, numRound)
}
addをオーバーライドして、もし試合数以上の値を加えようとすると例外を投げるようにしている。また、mutable版をImmutable版に変換するメソッドも実装している。
Immutable版
次にImmutable版も見てみよう。基本的にMutable版と同じなのだが、Immutable版では、コンパクトにデータが格納できるような、BitSet1、BitSet2、BitSetNのクラスを、それぞれPattern1、Pattern2、PatternNに拡張している。
object Pattern{
...
class Pattern1(elems: Long, val numRound : Int) extends BitSet1(elems)
with Pattern {
...
}
class Pattern2(elems1 : Long, elems2 : Long, val numRound : Int) extends BitSet2(elems1, elems2)
with Pattern{
...
}
class PatternN(elems : Array[Long], val numRound : Int) extends BitSetN(elems)
with Pattern {
...
}
}
trait Pattern extends BitSet
with BitSetLike[Pattern]
with scala.collection.kansai.math.Pattern{
....
}
immutable版は細々したことはあるのだが、特に重要でもないので省略する。
勝ちパターンを列挙する。
さて以上を使ってPatternコレクションを使って。勝ちパターンを列挙しよう。これは、各自の例題にしておく。
まとめ
この登壇、本記事で伝えたかったことを最後に記す。
- Scalaは楽しい。
以上である。
感想
こちらのレーンがセッションの前が、初心者向けのセッションだったので、なかなかちょっと話しにくいなと思ったが、話たいことを話した。