Scala Tips / Monoid (2) - 中央値

「Monoid - 新規作成」では平均値を素材にMonoidを新規作成する方法について説明しました。

アルゴリズムをMonoidとして用意するというアプローチは、アルゴリズムを再利用する選択肢を広げます。このアプローチをイディオム化する試みとして今回は中央値のMonoidを作成してみます。

Median

中央値の計算をMonoid化したものを以下のMedianとして実装しました。中央値を求めるアルゴリズムは、色々あるみたいですがここでは単純に全要素をソートした後にインデックスで中央値を取ってくる方法を使っています。

case class Median[T <% Double](numbers: List[T]) {
  def +:(a: T) = Median(a :: numbers)
  def :+(a: T) = Median(numbers :+ a)
  def +(a: Median[T]) = Median(a.numbers ::: numbers)
  def value: Double = Median.median(numbers)
  def apply(): Double = value
}

trait Medians {
  implicit def MedianZero[T <% Double]: Zero[Median[T]] = zero(Median(Nil))
  implicit def MedianSemigroup[T <% Double]: Semigroup[Median[T]] = semigroup((a, b) => a + b)

  def median[T <% Double](numbers: Seq[T]): Double = {
    if (numbers.size == 0) {
      Double.NaN
    } else if (numbers.length % 2 == 0) {
      val sorted = numbers.map(implicitly[T=>Double]).sorted
      val c = numbers.length / 2
      (sorted(c - 1) + sorted(c)) / 2.0
    } else {
      val sorted = numbers.map(implicitly[T=>Double]).sorted
      sorted(numbers.length / 2)
    }
  }    
}

object Median extends Medians {
  def apply[T <% Double](): Median[T] = Median(Nil)
}

View Bound

計算対象がInt固定だと面白くないので、Doubleに暗黙変換できる型はすべて使用可能なようにView Boundで指定しました。View Boundは武田ソフトさんの「View Bound/Context Bund」が詳しいです。「Monoid - 新規作成」はIntに固定していたので、今回はこの点が新たな工夫になっています。

アルゴリズム

平均値の場合は、平均値の計算に必要な値は総計と要素数なので、新しい要素を加えるたびにこの2つ値を再計算しておくという作戦を取りました。

一方、今回使用する中央値のアルゴリズムでは入力した要素をすべて記憶していることが前提になっています。ここは工夫によって記憶量を減らすことができそうです。

メソッド

ケースクラスMedianは以下のメソッドを提供しています。

メソッド	機能
+:	要素を左から追加
:+	要素を右から追加
+	Medianの加算
value	中央値の取得
apply	中央値の取得

applyメソッドは、機能的にはvalueメソッドと同じですが、文法糖衣用に用意しています。

アルゴリズムの再利用

中央値を求める関数をトレイトMediansに定義しオブジェクトMedianにも取り込んでいます。こうすることによって、アルゴリズムをシンプルに関数として使用できるようにしています。

関数

まず中央値のアルゴリズムを確認します。Medianオブジェクトのmedianメソッドの動作は以下になります。

scala> Median.median(List(1, 2, 3, 4, 5, 6))
res27: Double = 3.5

基本動作

Medianの基本動作は以下になります。

scala> (1 +: (2 +: (3 +: Median[Int]()))).value
res13: Double = 2.0

scala> val a = (1 +: (2 +: (3 +: Median[Int]()))) + (((Median[Int]() :+ 4) :+ 5) :+ 6)
a: Median[Int] = Median(List(4, 5, 6, 1, 2, 3))

scala> a.value
res15: Double = 3.5

scala> a()
res16: Double = 3.5

scala> List(1, 2, 3, 4, 5, 6).foldRight(Median[Int]())((x, a) => x +: a).value
res25: Double = 3.5

Monoid

MedianをMonoidとして使う場合は、Monoid化する設定を読み込みます。

scala> import Median._
import Median._

MedianをMonoidとして動作させると以下のようになります。mzero関数や|+|演算子を使用することができます。

scala> (1 +: (2 +: (3 +: mzero[Median[Int]]))).value
res19: Double = 2.0

scala> val a = (1 +: (2 +: (3 +: mzero[Median[Int]]))) |+| (((mzero[Median[Int]] :+ 4) :+ 5) :+ 6)
a: Median[Int] = Median(List(4, 5, 6, 1, 2, 3))

scala> a.value
res17: Double = 3.5

scala> a()
res18: Double = 3.5

scala> List(1, 2, 3, 4, 5, 6).foldRight(mzero[Median[Int]])((x, a) => x +: a).value
res26: Double = 3.5

MedianはMonoidなのでfoldMapメソッドを使うこともできます。

scala> List(1, 2, 3, 4, 5, 6).foldMap(x => Median[Int](List(x))).value
res22: Double = 3.5

Reducer

Reducerの動作を確認するために、平均値でも使ったPersonを使用します。

case class Person(name: String, age: Int)

捜査対象としてPersonのListを定義します。

val taro = Person("Taro", 35)
val hanako = Person("Hanako", 28)
val saburo = Person("Saburo", 43)

val persons = List(taro, hanako, saburo)

関数

まずmedianメソッドで計算する方法です。PersonのListをIntのListに変換後、medianメソッドを呼び出します。

scala> Median.median(persons.map(_.age))
res9: Double = 35.0

Reducer

Reducerを使う場合、MedianをMonoid化する設定を行います。

scala> import Median._
import Median._

Personの属性ageをMonoidに結びつけるためにReducerを使用します。「Reducer (4) - 自前Reducer」の方法を使ってReducerを直接作成してfoldReduceメソッドに指定しています。より効率的に動作するReducerが必要な場合は「Reducer (5) - 演算Monoid」のPersonAgeAverageReducerのような専用Reducerを定義するとよいでしょう。

scala> persons.foldReduce(implicitly[Foldable[List]], Reducer((p: Person) => Median(List(p.age)))).value
res10: Double = 35.0

Reducerを暗黙パラメタとして定義するとfoldReducerメソッドをより簡潔に使えるようになります。ただし暗黙パラメタはプログラムの見通しが悪くなるので使用には注意が必要です。

scala> implicit val r = Reducer((p: Person) => Median(List(p.age)))
r: scalaz.Reducer[Person,Median[Int]] = scalaz.Reducers$$anon$3@441357d7

scala> persons.foldReduce.value
res11: Double = 35.0

ノート

ケースクラスMedian、コンパニオン・オブジェクトMedian、トレイトMediansで中央値を計算するアルゴリズムを関数およびMonoidとして定義しました。

再利用可能なアルゴリズムを書いた時に、関数とMonoidの両方で提供すると再利用の選択肢が広がりそうです。今回のMedianは、そのための実装パターンのたたき台として使えるのではないかと思います。

諸元

• Scala 2.9.2
• Scalaz 6.0.4