比較はモノイド

比較モナドについて考察されている一連のエントリに感銘を受けて、私も比較について考えてみました。

• 比較モナド - terazzoの日記
• 続・比較モナド - terazzoの日記
• 続・続・比較モナド〜復讐編〜 - terazzoの日記

まず、考察対象として「比較結果」と「比較操作」に分けて考えます。比較結果というのは、比較後に返ってくる値(例：Java の Comparator の compare における 負・零・正)を言います。比較操作というのは、比較する関数(あるいは関数オブジェクト)自体(例：Java の Compartor 自体)を言います。

比較結果モノイド

比較結果というのは、2つの比較対象に対して、その片方が他方よりも「小さいのか」「等しいのか」「大きいのか」を示す値です。例えば、Perl の 比較演算子 <=> や Java の Comparator において、左辺が小さいことを負の整数で、左辺と右辺が等しいことを 0 で、左辺のほうが大きいことを正の整数で示すときの「負の整数」「0」「正の整数」のことを指します。

比較結果をモノイドとして扱っている言語では、整列などの操作が驚くほどスマートに記述できます。

例題として、ブログのエントリを整列する問題を考えてみましょう。日付の降順で並べ、もし日付が同じ場合はエントリ毎のIDの昇順で並べるという問題です。なお、ブログのエントリを示すクラスのフィールドには、そのエントリが書かれた日付(pubDate)と、一意の整数型識別子(id)があるものとします。

これを Java で書くと、こんな感じでごつごつとしてしまいますね。

  List<Entry> entries = ...// Entry が複数詰まっている

  Collections.sort(entries, new Comparator<Entry>() {
    public int compare(Entry e1, Entry e2) {
      if (!e1.pubDate.equals(e2.pubDate)) {
        return e2.pubDate.compareTo(e1.pubDate);
      } else {
        return new Integer(e1.id).compareTo(e2.id);
      }
    }
  });

下記に示すように groovy や Rubyだと事情は少し改善されますが、相変わらず条件分岐があってややこしかったり、あるいは、やや技巧的であったりという感じがしなくもないです。
（また、技巧的として示した側のコードは比較演算子が{-1, 0, +1}を返してくれず、単に{負, 零, 正}を返すような、そんなお行儀の悪い比較対象には使えません。とりわけ、Ruby の場合は、-1, 0, +1 を返すことが推奨されているだけで、-1, 0, +1 である保証はないです。つまり、-1 や +1 ではなくて、単なる負の数や単なる正の数が返ってきても、返す側は「正常動作」なので、技巧的なほうのコードが動く保証はないです。）

  #-- 普通に書いてみたコード
  entries.sort { |e1, e2|
    if e1.pubDate != e2.pubDate
      e2.pubDate <=> e1.pubDate
    else
      e1.id <=> e2.id
    end
  }

  #-- やや技巧的なコード。（<=>が返す値の範囲は{負, 零, 正} ではなく 必ず{-1, 0, +1}を返してくれることを期待）
  entries.sort { |e1, e2|
     2 * (e2.pubDate <=> e1.pubDate) + (e1.id <=> e2.id)
  }

逆に歴史的に古い perl のほうがむしろ、本質が見事に表現できます。pubDate で比較してそれでも決まらなければ id で比較するという本質が。

  sort { my ($e1, $e2) = @_;
    ($e2->{pubDate} <=> $e1->{pubDate}) || ($e1->{id} <=> $e2->{id})
  } @entries;

追記 2011-06-20

当初、上記の Rubyコード はGroovyコードであり、また、「GroovyやRubyでは」と記していましたが、この部分を修正しました。コメント欄で id:deve68 さんがご指摘の通り、?: 演算子を使えばスマートに解決できます。

  entries.sort { e1, e2 ->
    (e2.pubDate <=> e1.pubDate) ?: (e1.id <=> e2.id)
  }

(追記ここまで、他の追記・削除箇所は>ins<による下線や>del<による打消線で示しました)

で、Perl やGroovyだと上手く書ける理由を突き詰めると、比較演算子 <=> の結果がモノイドだからだと思いました。整数を比較結果とみなしたとき、|| が半群の二項演算になっていて、0が単位元なのですよっ！

もう少し説明を試みると、モノイドというのは、単位元を持つ半群のことです。

半群というのは、2つの要素(つまり、ここでは比較結果)を2項演算でくっつけ1つの要素にできる2項演算(ここでは ||)が定義されている集合(ここでは比較結果である「負の整数」「0」「正の整数」)です。また、その半群における単位元とは、相手の要素と2項演算でくっつけても、相手の要素が変化しない要素のことです。ここでは、0のことです。

Perl の || という演算子の挙動って、現代的観点からみても驚くほどきちんと考えられていて、単にOR(論理和) というだけでなく、およそ「和」の動作を一般化したものになっています。例えば、scala における Option モナドの orElse 動作に相当する動作も、Perl の || には含まれています。 (null || value)と書けば、ちゃんと value が返ってきますね。ちなみに、この orElse って、仮に Maybe/Optionモナド の MonadPlus版なるものがあるとすれば、確実に plus === orElse と定義するのが理にかなっているくらい Plus なんですよ。

で、scala の話になりますが、scala標準って、驚くほどイケテイいない。scala.math.Ordering#compare によって返される比較結果の何がイケていないかと言えば、これが、もう驚くほど Java なんですね。いや、返る実体は Java も Perl も Groovy も、はたまた、C の strcmp でさえも同じで、整数の負・零・正なんですが、その返ってくる値をどう見做すのかがダメダメでして、scala 標準は、Perlに全然及ばない。少なくとも私の scala 実力においては、scala でのスマートなコードは思い浮かばないです。sorted の implicit な引数に Ordering を明示的に渡すのもスマートではない。sortWith は less か否かを Boolean で返すだけなので(minimalism の点では、私は好きだけれど)、Ordering や Comparator の相性が微妙ですよね。なんか、もう scala の整列の恥部という感じがしなくもないので、なんか、そういうコードを載せる気がしません。(普段は、そういうコードを書いていますけれどね。)

そこで、試しに、あえて、普段は絶対に書かないような書き方をしてみます。

  // 正常動作するけれど、書き手の意図が分かりにくいウンコード
  entries.sortBy { e => e.pubDate -> (-1-e.id) }.reverse

もちろん、このコードもダメ。何がダメかというと、一見しただけでは何がしたいか不明だし、拡張性に乏しいからですね。また、譬え、このコード片を見て意図が一目瞭然で拡張の仕方も想定できる人ばかりの世界であったとしても、比較毎に Tuple2 を生成するしreverseするしでパフォーマンスが悪いです。

そこで、満を持して登場するのが ScalaZライブラリです。

ScalaZ の何がすごいかっていうと、「比較結果はモノイドだ」って明示的に言明しちゃってるのですね。正確には、まず、比較可能なものに対しては Order という型クラスを定義する約束になっているんですね。で、Order のインスタンスメソッド order による比較結果に専用の代数的データ型(scalaz.Ordering = LT | EQ | GT)を作っているんですね。うーん型安全ですね。さらに、こいつに対する型クラス Semigroup と Zero が備わっている（すなわち、scalaz.Ordering が単位的半群≡モノイドである）のですよ。

つまり、こんなことが、できるんです。

  entries.sorted(OrderOrdering(order{ (e1: Entry, e2: Entry) =>
    (e2.pubDate ?|? e1.pubDate) |+| (e1.id ?|? e2.id)
  }))

要点はここです：

  (e2.pubDate ?|? e1.pubDate) |+| (e1.id ?|? e2.id)

?|? は、比較演算子。Order型クラスが備わっている任意の型のインスタンス同士を比較する演算子メソッド。比較結果は、scalaz.Ordering (scala.math.Orderig[T] とは別物)。で、この scalaz.Ordering はモノイドであり、くっつける演算が |+| なんです。EQが単位元なのであることを念頭におけば、「片方が EQ であれば、他方の結果を返す；どちらもEQでないならば、左側（すなわち優先側）を返す」ということは、ほとんど自明かつ自然。

しかも、Perl と違って、scala/scalazは型安全なんです（＞＜）

比較操作モノイド

で、ここまでは、比較結果(= LT, EQ, GT とか -1, 0, +1 とか)をモノイドと見做すとウレシイ（し、実際 scalaz では モノイド）ということについてでした。

次に、比較操作(= Comparator とか <=> とか)は、何なの（どのように見做せば世界がシンプルに見えるの、うまく回るの）っていう話です。

まずは、たたき台として、とりあえずモノイドにしてみました。

比較操作の半群のための2項演算は、将来的に apply されたとき(= 比較操作が行われたときに)、左辺が EQ を返すならば右辺に判断を委譲し、左辺がGT/LTを返すならばその結果を返す、そんな比較操作を返す。ここで、単位元は EQ。というような感じです。

// Order(scalaz の比較器)をモノイドにするための型クラス
trait OrderAsMonoid {
  // 半群を与える
  implicit def OrderSemigroup[T]: Semigroup[Order[T]] = semigroup {
    (o1, o2) => order{ (x, y) => o1.order(x, y) |+| o2.order(x, y) }
  }
  // 単位元を与える
  implicit def OrderZero[T]: Zero[Order[T]] = zero(order{(x, y) => EQ})
}

上記のように Order に対するモノイド型クラスを定義すると、下記のような感じのことができます。

import scalaz._
import scalaz.Scalaz._
import java.util.Date

object OrderMonoidTest extends App with OrderAsMonoid with OrderLow {
  // Entry を pubDate の降順で並べる Order
  val orderEntryByPubDateDesc: Order[Entry] =
    order {(e1, e2) => e2.pubDate ?|? e1.pubDate}
  
  // Entry を id の昇順で並べる Order
  val orderEntryByIdAsc: Order[Entry] =
    orderBy {_.id}
  
  // OrderAsMonoid により、今や Order 自体がモノイドなので、Order 自体を |+| により結合可能
  val orderEntryByPubDateDescOrElseByIdDesc =
    orderEntryByPubDateDesc |+| orderEntryByIdAsc
  
  // scala の sorted を呼び出すために、scalaz.Order を scala.math.Ordering に変換
  val theOrderAsScalaOrdering =
    Order.OrderOrdering(orderEntryByPubDateDescOrElseByIdDesc)
  
  val sortedEntries = EntryManager.entries.sorted(theOrderAsScalaOrdering)
}

比較結果をモノイドとみる感じというのは、自分の中ではかなりいい感じじゃないかと思っています。（無論、モノイドという見方がよい見方というだけであって、他の見方が悪いわけではないです。もっといい見方もあるかもしれませんし、よい or よくない、というのは時と場合に依る部分もあると思いますし）

で、比較操作をモノイドとみる感じというのは、まだ自分の中でさえ納得できていない部分があります。というのは、素直に考えて、Comparator は、T型 => 比較結果型 への Functor とみるのが自然であり、Functor に対していろいろ制約を追加していくのが王道だというような気がするからです。（ちなみに、Functor から出発していろいろなものが追加していくと、追加するものによっては Monad になります）

ちょっと、最後のほうがグダグダになってしまいました＾＾；