2012年7月31日火曜日

クラウド温泉3.0 (10) / map, filter, fold

クラウド温泉3.0@小樽のセッション「Monadicプログラミング・マニアックス」で使用するスライドのネタ検討その10です。

パイプライン・プログラミングを構成する要素として以下の2つを説明しました。

Functorが提供する計算文脈におけるパイプラインでは、一般的にmapメソッドに加えてfilterメソッドとfoldメソッドを使うことができます。たとえばListでは以下のようになります。

scala> List(1, 2, 3).filter(_ % 2 == 1).map(_ * 2).fold(0)(_ + _)
res3: Int = 8

このようにメソッドをつないでパイプラインを構築することができるわけです。map, filter, foldメソッドは基本中の基本部品となっています。

for式

mapメソッドとfilterメソッドはfor式の文法糖衣も用意されています。文法糖衣が用意されていることからも基本中の基本であることがわかります。

上記の式の前半は以下になります。

scala> List(1, 2, 3).filter(_ % 2 == 1).map(_ * 2)
res5: List[Int] = List(2, 6)

これはfor式を使って以下のように書くことができます。

scala> for (x <- List(1, 2, 3) if x % 2 == 1) yield x
res4: List[Int] = List(1, 3)

パイプラインの構成部品

map, filter, foldメソッドをパイプラインの構成部品と考えて、パイプラインの観点から整理してみました。

メソッド動作動作イメージコンテナ要素要素数
mapコンテナ上の要素に関数を適用して新しいコンテナに詰め直す。M[A]→M[B]変わらない変わる変わらない
filterコンテナ上の要素を選別して新しコンテナに詰め直す。M[A]→M[A]変わらない変わる減る
foldコンテナをまるごと別のオブジェクトに変換する。M[A]→N変わるなくなるなくなる

説明の都合上コンテナという用語を導入しました。コンテナは計算文脈の実装と考えてもよいですし、パイプライン上に要素を載せて流れる荷車というようにイメージしてもよいでしょう。

このように整理することでパイプラインの構成部品を分類するための軸として以下のものを抽出することができました。

  • コンテナの型の変換 (選択肢: 変わる、変わらない)
  • 要素の型の変換 (選択肢: 変わる, なくなる)
  • 要素数の変化 (選択肢: 変わらない, 減る, なくなる)

バリエーションの組み合わせ的にはmap, filter, foldの3種類以外にも色々と有用な組み合わせがありそうです。

fold

foldメソッドは、コンテナをまるごと別のオブジェクトに変換するので、パイプラインの終端ということになります。

foldメソッドは色々なバリエーションがあります。以下の記事が参考になると思います。

2012年7月30日月曜日

クラウド温泉3.0 (9) / Functorによる計算文脈

クラウド温泉3.0@小樽のセッション「Monadicプログラミング・マニアックス」で使用するスライドのネタ検討その9です。

前回はListを素材にパイプラインの重要な構成要素であるFunctorを取り上げました。

List処理でのmapメソッドは関数型プログラミングの定番中の定番なので、List操作あるいはコレクション操作でのmapメソッドの効用はよく知られていると思います。しかし、mapメソッドをFunctorの観点からみると、「計算文脈」というもっと重要な概念が隠れています。

Option

JavaからScalaに入った当初はOptionはnullの問題を回避するためのオブジェクトで"要素数1の劣化版コレクション"というようなイメージを持つかもしれません。Optionは格納する要素数が1つなので、Listでは有用であったmapメソッドがあってもあまりメリットがあるように感じないでしょう。そもそも存在に気づかないかもしれません。

Optionは「nullの問題を回避するためのオブジェクト」というような脇役の存在ではなく、Monadicプログラミングの花形オブジェクトの一つです。それは、Optionが「計算文脈」を提供するからです。

前回のListの例をOptionに置き換えたものは以下になります。要素数が1なのであまり面白みがありません。

scala> Some(1).map(_ * 3).map(_ + 5)
res7: Option[Int] = Some(8)

scala> Some(1).map(mul3).map(plus5)
res8: Option[Int] = Some(8)

scala> Some(1).map(mul(3, _)).map(plus(5, _))
res9: Option[Int] = Some(8)

scala> Some(1).map(mulc(3)).map(plusc(5))
res10: Option[Int] = Some(8)

ところがOptionがNoneだった場合は話が変わります。OptionがNoneの場合にはmapメソッドで指定した計算がなんであっても答えは必ずNoneになります。

scala> none[Int].map(_ * 3).map(_ + 5)
res14: Option[Int] = None

scala> none[Int].map(mul3).map(plus5)
res15: Option[Int] = None

scala> none[Int].map(mul(3, _)).map(plus(5, _))
res16: Option[Int] = None

scala> none[Int].map(mulc(3)).map(plusc(5))
res17: Option[Int] = None

Optionを「成功と失敗」の計算文脈と考えると、この挙動の意味が分かってきます。OptionがSomeの間はOptionの計算文脈は「成功」でmapメソッドによる計算結果は計算文脈上つまりOption上に残ります。一方、OptionがNoneになるとOptionの計算文脈は「失敗」でmapメソッドによる計算結果は必ずNoneつまり「失敗」になります。

Optionの計算文脈に関する議論は以下の記事が参考になると思います。

その他の計算文脈

また、EitherやValidationの計算文脈としての意味、使用方法は以下の記事が参考になると思います。

計算文脈

計算文脈の観点からパイプライン演算やデータフローを理解するには以下の記事が参考になると思います。

この記事は「Object-Functional Analysis and Design: 次世代モデリングパラダイムへの道標」の一環で、最後のまとめは「Object-Functional Analysis and Designまとめのまとめ」に、続編は「Object-Functional Analysis and Designふたたび」なります。

あくまで私案ですが、ソフトウェア開発方法論におけるデータフロー、パイプライン演算、計算文脈、モナド(ここまでの記事には出てきていませんが)の位置付けを考える上でのヒントになると思います。

ノート

Monadicプログラミングの重要な概念である計算文脈は説明が難しいので、スライドでどうしていくのか要検討という感じです。このあたりはプログラムをたくさん書いて体で覚えていくしかないかもしれません。スライドでは簡単な説明をした後、参考リンクを紹介という形になりそうです。

2012年7月27日金曜日

クラウド温泉3.0 (8) / Functor

クラウド温泉3.0@小樽のセッション「Monadicプログラミング・マニアックス」で使用するスライドのネタ検討その8です。

前回は関数を用いたMonadicプログラミングについて考えました。今回はFunctorを用いたMonadicプログラミングについて考えます。

前回、パイプライン・プログラミングを広義のMonadicプログラミングと定義しました。

今回は、FunctorによるMonadicプログラミングを考えます。FunctorはMonadではありませんが、パイプライン演算に見立てることができます。

mapメソッド

Listなどのコレクションクラスが提供するmapメソッドはコンテナに格納されているオブジェクトに対して計算した結果得られた新たなオブジェクトに詰めなおしたコンテナを生成します。このようなmapメソッドを持つオブジェクトを一般的にFunctorと呼びます。ScalaとFunctorの関係は「Scala で圏論入門」に詳しいです。

mapメソッドの使い方は以下になります。

scala> List(1, 2, 3).map(x => x * 3)
res1: List[Int] = List(3, 6, 9)

mapメソッドをつなぐことでパイプライン処理を記述することができます。

scala> List(1, 2, 3).map(x => x * 3).map(x => x + 5)
res2: List[Int] = List(8, 11, 14)

Scalaでは関数リテラルでの省略記法が提供されているので、これを用いると以下のように書くことができます。 

scala> List(1, 2, 3).map(_ * 3).map(_ + 5)
res3: List[Int] = List(8, 11, 14)

関数

mapメソッドに直接関数リテラルで処理を記述してもよいのですが、再利用可能な部品として関数を用意しておいて、これを指定する使い方がより望ましいでしょう。

関数mul3とplus5を用意します。いずれも引数の数が1つの関数です。

def mul3(a: Int) = a * 3
def plus5(a: Int) = a + 5

これをmapメソッドで使うと以下になります。

scala> List(1, 2, 3).map(x => mul3(x)).map(x => plus5(x))
res11: List[Int] = List(8, 11, 14)

Scalaでは関数リテラルでの省略記法が提供されているので、これを用いると以下のように書くことができます。 こうなるとパイプラインに部品を接続することで処理を組み立てていることが明確になります。

scala> List(1, 2, 3).map(mul3).map(plus5)
res4: List[Int] = List(8, 11, 14)

部分適用

引数の数が2つ以上の関数では部分適用を用いることで、mapによるパイプラインに適用できます。

関数の引数が複数あるケースを考えます。関数mulとplusを用意します。いずれも引数の数が2つの関数です。

def mul(a: Int, b: Int) = a * b
def plus(a: Int, b: Int) = a + b

これをmapメソッドに適用すると以下になります。

scala> List(1, 2, 3).map(mul(3, _)).map(plus(5, _))
res5: List[Int] = List(8, 11, 14)

カリー化

関数がパイプラインの中で使われることが明らかな場合はカリー化しておくと便利です。カリー化した関数pluscとmulcは以下になります。

def mulc(a: Int)(b: Int) = a * b
def plusc(a: Int)(b: Int) = a + b

pluscとmulcを用いてパイプラインを構築すると以下になります。

scala> List(1, 2, 3).map(mulc(3)).map(plusc(5))
res6: List[Int] = List(8, 11, 14)

ノート

広義のMonadicプログラミングをパイプライン・プログラミングと定義し、関数によるパイプライン・プログラミング、Functorによるパイプライン・プログラミングについてみてきました。

他に幾つかパイプライン・プログラミングの候補があるので、次回以降に取り上げる予定です。

スライドでは、パイプライン・プログラミングの実現技術をリストアップした後、これを一つにまとめてプログラミング・スタイルとして整備したいと考えています。

2012年7月26日木曜日

クラウド温泉3.0 (7) / 関数によるMonadicプログラミング

クラウド温泉3.0@小樽のセッション「Monadicプログラミング・マニアックス」で使用するスライドのネタ検討その7です。

前回はMonadicプログラミングの非公式定義を考えました。まとめると以下になります。

Monadを中心としつつも、旧来からあるFunctorによるプログラミング、関数合成、コンビネータなども包含しつつ、パイプライン・プログラミングのスタイルとしてまとめたもの。

今回は、普通の関数呼出しによるMonadicプログラミングを考えます。普通の関数呼び出しなので当然モナドは使っていません。つまりパイプライン・プログラミングとしての関数呼び出しです。

パイプライン演算子

関数mul3とplus5を用意します。いずれも引数の数が1つの関数です。

def mul3(a: Int) = a * 3
def plus5(a: Int) = a + 5

これを普通に関数呼び出しで使うと以下のようになります。このように引数が一つの関数を連続的に呼び出すケースはパイプライン処理に見立てることができます。

scala> mul3(plus5(10))
res71: Int = 45

Scalazでは関数呼出しによるパイプライン処理を記述するための演算子として「|>」を提供しています。パイプライン演算子と呼ばれています。

このパイプライン演算子を使って上記処理を記述すると以下になります。まさにパイプライン演算ですね。

scala> 10 |> plus5 |> mul3
res73: Int = 45

複数の引数

関数の引数が複数あるケースを考えます。関数mulとplusを用意します。いずれも引数の数が2つの関数です。

def mul(a: Int, b: Int) = a * b
def plus(a: Int, b: Int) = a + b

これを普通に関数呼び出しで使うと以下のようになります。

scala> mul(3, plus(5, 10))
res74: Int = 45

ここで、この演算をScalazのパイプライン演算子で記述しようとすると、はたと困ってしまいます。これは、パイプラインのセマンティクスより、引数を複数持つ関数の呼出しの方がセマンティクスが大きいからです。より汎用的なわけですね。

関数呼び出しは、関数の実行結果をルートとする木構造として考えることができます。ルートからリーフに至る複数あるパスのそれぞれはパイプラインとして考えることができるので、複数のパイプラインを合成したものと考えることができます。

パイプラインのセマンティクスに持ち込むためには、複数あるパスの中の1つを主のパスと定め、このパスを中心にパイプラインを記述していく必要があります。

これを関数の呼び出しで実現するには、上記の複数引数による関数呼び出しを引数の数が1つの関数の関数呼び出しに変換します。なぜなら、関数の結果はひとつなので、これを関数がそのまま受け取るためには引数の数が1つでなければなりません。つまり、引数の数が1つの関数を用意し、これをパイプラインとして結合して動作させることになります。

部分適用

Scalaは関数の引数を部分的に適用した新しい関数を作成する、部分適用という機能を提供しています。部分適用を用いて記述すると以下になります。

scala> 10 |> (plus(5, _: Int)) |> (mul(3, _: Int))
res83: Int = 45

カリー化

関数がパイプラインの中で使われることが明らかな場合はカリー化しておくと便利です。カリー化した関数pluscとmulcは以下になります。

def mulc(a: Int)(b: Int) = a * b
def plusc(a: Int)(b: Int) = a + b

pluscとmulcを用いてパイプラインを構築すると以下になります。随分読みやすくなりました。この例からも分かるようにカリー化のコツは、パイプライン上で受け渡される引数を最後に持ってくることです。

scala> 10 |> plusc(5) |> mulc(3)
res78: Int = 45

便利かどうかは別として、curriedメソッドを用いて関数をその場でカリー化して使用することもできます。

scala> 10 |> (plus _ curried(5)) |> (mul _ curried(3))
res92: Int = 45

2012年7月25日水曜日

クラウド温泉3.0 (6) / Monadicプログラミングの非公式定義

クラウド温泉3.0@小樽のセッション「Monadicプログラミング・マニアックス」で使用するスライドのネタ検討その5です。

本ブログでは「Monadicプログラミング」という用語を使っていますが、Monadicプログラミングやmonadic programmingという用語をウェブで検索しても、ピッタリとした定義は見つかりません。

だいたいMonadを使ったプログラミング・スタイルというのが、最大公約数的な意味のようです。

ただ、Monadの使用の有無をプログラミング・スタイルのスコープにするとMonadを使わないケースは適用範囲外ということになり、適用できるユースケースが限定されます。

そこで、Monadを中心としつつも、旧来かあるFunctorによるプログラミング、関数合成、コンビネータなども包含しつつ、「ある種のプログラミング・スタイル」としてまとめたものを、本ブログおよびクラウド温泉のセッションではMonadicプログラミングと呼ぶことにしたいと思います。

そこで「ある種のプログラミング・スタイル」ですが、パイプライン・プログラミング、パイプラインによって部品を結合したものの上にデータを流していく、というスタイルを指すことにします。

たとえば、「Object-Functional Analysis and Design - 次世代プログラミングパラダイムを考える」の以下のスライドでみられるようなプログラミング・スタイルですね。



この中の後者のパイプラインはMonadは使わずArrowを使っているので、Monadに限定するとスコープに入ってきません。こういったスタイルを包含するためにMonadicプログラミングの意味をMonadを中心としたパイプライン・プログラミングに拡張したいわけです。

Monadを中心としたパイプライン・プログラミングに関する上記スライドに関係して、以下の記事が参考になると思います。このあたりがMonadicプログラミングの典型的な使用例になります。

2012年7月24日火曜日

クラウド温泉3.0 (5) / 永続データ構造としてのケースクラス

クラウド温泉3.0@小樽のセッション「Monadicプログラミング・マニアックス」で使用するスライドのネタ検討その5です。

関数型言語における永続データ構造の運用イメージは「イミュータブルデータ構造は遅いような気がしていたが、別にそんなことはなかったぜ!」のキャッチが秀逸な「20分で分るPurely Functional Data Structures」がとてもいい資料です。

このような本格的な永続データ構造の実現はかなり難易度の高いプログラミングになりそうですが、有名所は専門家が開発したものがクラスライブラリに用意されているので、普通のプログラミングではそれを利用する技術を知っておけば十分です。

逆にアプリケーションのドメインオブジェクトを永続データ構造で実現する場合は、当然アプリケーション側で実装する必要があります。しかし、このような場合は難しいアルゴリズムは不要で、一定のイディオムを活用してサクサク作ってしまえばOKです。Scalaの場合は、性能が出なければ(難しいアルゴリズムは導入せず)そのままミュータブルにしてしまうという奥の手もあるので、最初の取っ掛かりは安全性重視でイミュータブルにしてしまうのがよいでしょう。

で、ドメインオブジェクトを永続データ構造で実現するときのアプローチの一つとしてケースクラスがあります。ケースクラスは「代数的データ型 on Scala」で説明した通り直積(Product)という側面もあり、sealed trait/abstract classと組合せて"直積の直和の総和"として代数的データ型を実現できます。

その一方で、シンプルな永続データ構造であればケースクラスで簡単に実現することができます。

人を表すPersonクラスを例にして実現方法を見ていきましょう。

定義

Personクラスを定義して、インスタンスを作成します。

scala> case class Person(name: String, age: Int)
defined class Person

scala> val taro = Person("Taro", 30)
taro: Person = Person(Taro,30)

永続データ構造として利用

永続データ構造に対する更新は、"「更新不可のオブジェクトを更新する」という矛盾を関数型プログラミングのテクニックで回避する"ことですが、基本的には更新部分の属性のみを変更した新しいオブジェクトを元のオブジェクトから複製することによって実現します。

基本となるアプローチはコンストラクタを使うもので、以下のようにコンストラクタに更新元のオブジェクトの属性値を並べて指定し、更新したい属性のみ新しい値を指定します。この場合はPersonの年齢を変更しています。

scala> val taro31 = Person(taro.name, 31)
taro31: Person = Person(Taro,31)
コピーコンストラクタ

コンストラクタですべてのパラメタを指定するのはプログラミングも大変ですし、デフォルトパラメタなどがある場合、パラメタ指定の抜けなどが発生してバグの元にもなります。このような問題を解決しているのがいわゆるコピーコンストラクタであるcopyメソッドです。

copyメソッドを使って、必要な属性のみを更新したオブジェクトを複製することができます。

scala> val taro31 = taro.copy(age = 31)
taro31: Person = Person(Taro,31)

永続データ構造的な機能追加

年齢の更新がPersonオブジェクトにとって、(1)使用頻度が高い、(2)ドメインモデル上重要な意味を持っている、(3)ドメイン特化のアルゴリズムを持っている、といった事情がある場合には、専用の更新メソッドを追加するのがよいアプローチです。

以下は年齢を加算するメソッドを追加したPersonです。こういった形で更新メソッドを定義し、実装にはcopyメソッドを使うのがイディオムです。

case class Person(name: String, age: Int) {
  def addAge(n: Int) = {
    copy(age = age + n)
  }
}

下のように使用します。

scala> taro.addAge(1)
res70: Person = Person(Taro,31)

ノート

以上で説明したようにケースクラスを用いると永続データ構造を簡単に作成することができます。ポイントとなるのはコピーコンストラクタで、変更対象となる属性のみを指定すると、その他の属性は自動的に設定された複製を作成してくれます。ケースクラスはこのコピーコンストラクタを自動的に定義してくれるのがとても重要な点です。

このように関数型プログラミングでの重要概念である代数的データ型と永続データ構造はどちらもScalaではケースクラスがキーとなる機能でした。

そういう意味で、代数的データ型/永続データ構造という枠組みの中でのケースクラスの活用がScalaプログラミングのコツということですね。

このあたりはScalaプログラミング的には非常に重要ですが、Monadicプログラミングからは距離があるので、セッション内でどの程度触れるのかは要検討です。

  • 代数的データ型&永続データ構造→ケースクラス

で一枚のスライドにまとめてしまうかもしれません。

2012年7月23日月曜日

MindmapModeling「顧客との絆づくり型O2Oで世界にも挑戦する無印良品」

7月21日(土)に横浜モデリング勉強会(facebook group)を行いました。また、会場には(株)アットウェア様の会議室をお借りしました。参加された皆さん、アットウェア様、どうもありがとうございました。

この勉強会で、浅海が作成したモデルを紹介します。モデルはMindmapModelingの手法で作成しました。(勉強会で使用したチュートリアル)

ワークショップの流れ

モデリング勉強会はワークショップ形式で以下の作業を行います。

  • 雑誌記事から情報システムの企画書、提案書、RFPの元ネタとなるモデルを作成する。

その上で、「要求仕様確認、実装可能性確認、開発のベースとなるプログラムを自動生成するモデルを目指」します。詳細は「ワークショップの進め方 (2012-06-16)」になります。

テーマ

モデリングの対象は、東洋経済誌の記事「顧客との絆づくり型O2Oで世界にも挑戦する無印良品」です。

後編を主の文章としましたが、前編もあわせて読んだ方がモデリングに必要な情報は収集しやすいようです。

O2Oは『MindmapModeling「KDDIがO2O事業を検討、無印良品やファミマが参加し実証実験」』でもテーマに取り上げました。クラウド時代のビジネスとITの接点として重要な分野になりそうです。

用語の収集と整理

まず用語の収集と整理します。

MindmapModelingに慣れてくると、用語がだいたいどこの枝に収まるのかわかるようになるので、用語を拾いながら、ラフなモデルを作っていきます。


今回の記事は、かなりざっくりした内容でO2Oの一般的な運用例という感じでした。そういう意味で「無印商品」が先駆者の一人ということだと思いますが、KDDIの記事と比べて新規性はあまり感じられず、O2Oだと大体こういう感じかな、という用語が採取されました。

物語

次の作業は「物語」です。

モデルは中心軸がないと単なる「用語」の集りなのでまとまりがでてきません。何らかの目的を実現するための構造を抽出したいわけですが、この「目的」と「目的を実現するための構造」を掬いとるためのツールとして有効なのが「物語」です。オブジェクト・モデリングの概念ではビジネス・ユースケースということになります。

「物語」を中心軸と定め、「物語」のスコープで用語を取捨選択、組織化し、足りない用語を補っていきます。

その手順は:

  1. 物語の名前をつける。目的(goal)が明確になる名前がよい。
  2. 物語の主人公、相手役、脇役などの登場人物を定める。
  3. 物語で使用する道具を定める。
  4. 出来事または脚本の列として脚本を記述する。

となります。2の登場人物と3の道具は最初から完全なものはできないので暫定的なものを定め、4の脚本の作業を通して洗練させていきます。


今回は、システムのインフラ部はO2Oでどのシステムも同じになりそうで、ここを精密にモデリングしても面白いものになりそうにありません。そこで、「無印良品」の物語をモデリングして、これをO2Oの観点で組織化してO2Oのインフラに合わせていくという方向性でモデリングを進めました。

物語を精密に組織化していこうとすると、現状のユースケース技術だと少し力不足かなという印象です。このあたりはメタモデルの機能拡張が必要に感じました。

最終型

前述の方針でさらに洗練を進めたモデルが以下になります。


時間切れでモデルはここまでとなりました。

「無印良品」の物語をシステム側で分析可能なデータとして蓄積していくメカニズムとして「道具」の「顧客時間」が使えそうなことが分かってきました。この「顧客時間」を会計システムの仕分け的なアプローチで、一つのイベントをシステムのいろいろな観点で同時にラベリングして、成分値も記録していくという実現方式です。どういう成分値のポートフォリオをどういうバランスで採取していくのかを時間をかけてじっくり検討していくと面白そうです。

O2O

MindmapModeling「KDDIがO2O事業を検討、無印良品やファミマが参加し実証実験」』に続いてO2Oは2回目ですが、インフラ部分の要素はほぼ共通で、パッケージなりクラウドサービスなりで実現することが可能な技術という印象です。そうなると、モデリングについてはインフラ部分の設計はあまりニーズがなく、ビジネスそのものをITシステムに接続するためのモデルが重要になりそうです。いわゆるERPのフィットギャップ分析のようなものですね。

さらに考えていくと、上流のモデルからプログラムの自動生成でO2Oフレームワーク向けのコードが生成されれば理想的です。

完全な自動生成は無理としても、ビジネス・モデルを記述したものから、特定のスコープは自動生成、それ以外はスクラッチで開発といった開発の流れが見えてきます。

クラウド時代に入って、色々な技術が新たに登場してきますが、業務アプリのインフラ側は新技術の登場から一定期間後にパッケージやクラウドサービスで提供されることを考えると、業務アプリ側の立場としては個々のインフラ技術を細かく追いかけていくのは効率的なアプローチではないかもしれません。それより、クラウドプラットフォームの特性をざっくりと把握して、これを業務とつなげていくモデリング技術の重要性がより高まるのではないかと感じました。

次回

8月は一回お休みして次回は9月中旬(第3週土が候補)です。

今回と同じく「ワークショップの進め方 (2012-06-16)」の手順で、「雑誌記事から情報システムの企画書、提案書、RFPの元ネタとなるモデルを作成する」を行う予定です。

2012年7月20日金曜日

クラウド温泉3.0 (4) / 永続データ構造

クラウド温泉3.0@小樽のセッション「Monadicプログラミング・マニアックス」で使用するスライドのネタ検討その4です。

セッションはMonadicプログラミングがテーマですが、その前提として関数型プログラミングがあります。関数型プログラミングの基本構成要素も色々ありますが、オブジェクト指向プログラマの認知度が低いと思われるものに代数的データ型と永続データ構造があります。

関数型プログラミングの基本構成要素として、前々回前回代数的データ型を説明しました。

もう一つ重要な基本構成要素として永続データ構造があります。

「永続」というと「永続性」という概念があり永続データや永続オブジェクトといった用語は広く使われています。オブジェクト指向プログラマが「永続」と聞くと、普通は永続データや永続オブジェクトの永続を想起すると思います。

関数型プログラミングの永続データ構造は全くの別物なので注意が必要です。

永続データ構造

Wikipediaによると『永続データ構造(えいぞくデータこうぞう、英: Persistent data structure)は、変更される際に変更前のバージョンを常に保持するデータ構造である。このようなデータ構造は、更新の際に元のデータ構造を書き換えるのではなく、新たなデータ構造を生成すると考えられ、イミュータブルなデータ構造の構築に利用可能である』と定義されています。

(やや不正確ですが)簡単にいうとイミュータブルオブジェクトでデータ構造を構築したものと考えると分かりやすいと思います。イミュータブルオブジェクトは「不変」すなわち「更新不可」のオブジェクトです。更新不可のオブジェクトでデータ構造を構築すると、データの更新ができなくて困るのではないかと疑問に思ってしまいますが、関数型プログラミングではこの問題を回避するテクニックが用意されており、案外大丈夫なのです。

イミュータブルオブジェクトでデータ構造を構築すると以下のメリットがあります。

  • データが変更されないのでバグが出にくい。
  • 並行プログラミングでロックが必要なくなる。
  • 過去のデータと現在のデータをマルチバージョン的な切り口で使用できる。

「更新不可のオブジェクトを更新する」という矛盾を関数型プログラミングのテクニックで回避することで、これらのメリットを享受することができるようになります。

特に重要なのは並行プログラミングとの相性がよい事です。並行プログラミングでのバグの多くは排他漏れによるデータのアクシデンタルな更新ですが、「データが変更されない」のでこの問題は起きません。「並行プログラミングでロックが必要なくなる」というのも大きいですし、「過去のデータと現在のデータをマルチバージョン的な切り口で使用できる」ことで多重性能を上げることにも寄与します。

Monadicプログラミング」の狙い」の一つとして並行プログラミングを挙げましたが、永続データ構造も同様に並行プログラミングに向けてのキーテクノロジといえます。

List

楽々Scalaプログラミング」では永続データ構造としてListの例を説明しました。

Listは典型的な永続データ構造なので、Listの使い方に習熟することが永続データ構造をマスターする近道となります。

fold

Listが典型ですが永続データ構造を効率よく操作するためには、ちょっとしたテクニックが必要で、その一つが畳込み処理を行うfold処理をめぐるプログラミング戦略です。

このあたりの事情は「foldの選択」でも説明しました。

スライド

永続データ構造について色々と書いてきましたが、セッションではこれを一枚のスライドにまとめてざっくりと触れるという感じになると思います。

楽々Scalaプログラミング」と同様にList処理を例に説明するかもしれませんが、時間的な制約があるのでごく簡単に触れるのみにする可能性が高そうです。

ノート

セッションは、「これからScalaプログラミングを始めたい」から「Scalaを始めたばかりで関数型プログラミングへの取り組み方法が分からない」といった、Javaプログラマを念頭に置いています。(もちろん、本当のJavaプログラマである必要はなくて、Java的なOOPを一通り使えるプログラマ、ぐらいの意味です。)

セッションではMonadicプログラミングの面白いところ、具体的な効用といったものをフィーチャしたいわけですが、細かい議論をするためには、その前提として関数型プログラミングの基礎知識が必要です。この「関数型プログラミングの基礎知識」を説明しだすと、それだけでひとつのセッションになるので、そのあたりをどうするのかが悩みどころです。

そういう意味で、セッションはMonodicプログラミングのコードを見てもらって、そのコードゴルフ的なシルエットを鑑賞?してもらいつつ、Monadicプログラミングの狙いや効用を説明していく感じになりそうです。

ただ、これだけだと不親切なので、Monadicプログラミングに必要な前提知識をリストアップしておきたいのですが、オブジェクト指向プログラマに馴染みの薄い概念として代数的データ型や永続データ構造は有力な候補かなと考えています。

2012年7月19日木曜日

クラウド温泉3.0 (3) / 代数的データ型 on Scala

クラウド温泉3.0@小樽のセッション「Monadicプログラミング・マニアックス」で使用するスライドのネタ検討その3です。

前回は代数的データ型について考えました。

ボクの非公式理解では、代数的データ型は:

  • 直積の直和の総和

です。

代数的データ型は以下のように、オブジェクト指向のインヘリタンスと対置する位置付けにある、関数型のかなり重要な構成要素であることが確認できました。

  • オブジェクト指向はクラスでインヘリタンス
  • 関数型は代数的データ型で選択

この代数的データ型ですが、Scalaではケースクラスで実装するのがイディオムになっています。

ケースクラス

以下のようにケースクラスPersonを定義します。これがそのまま代数的データ型となります。

scala> case class Person(name: String, age: Int)
defined class Person

代数的データ型は「直積の直和の総和」ですが、その単純形である「直積」そのものも代数的データ型です。ケースクラスはコンストラクタに並んだ要素の直積と見立てることが可能です。このためケースクラスを定義すれば、そのまま代数的データ型ということになります。

直積

Scalaでは直積を表すトレイトProductが定義されています。以下のように、ケースクラスPersonはProductでもあります。なんとケースクラスは意味上だけではなく、Scalaの型システム上も直積になっているというわけです。

scala> var a: Product = Person("Taro", 30)
a: Product = Person(Taro,30)

Scalaの代表的な直積の表現はタプルですが、このタプルも以下のようにProductとなっています。

scala> var b: Product = ("Taro", 30)
b: Product = (Taro,30)
選択

代数的データ型を「直積の直和の総和」として、直積そのものの実現はケースクラスで可能なことを説明しました。

それでは「直和の総和」はどう実現すればよいでしょうか。

これは、以下のようにsealed trait(またはsealed abstract class)とケースクラスの組み合わせがイディオムになっています。

sealed trait A
case class B() extends A
case class C() extends A
case class D() extends A

「直和の総和」の実現にインヘリタンスを使っていますが、オブジェクト指向的なインヘリタンスと違うのは、ベースクラスをsealedにすることで、サブクラスが後から追加されないことが保証されている点です。

このことで「直和」を表現しています。さらに複数のサブクラスを並べることで「直和の総和」を表現しています。

Scalaはオブジェクト指向の核の上に、関数型を載せている二段構成の言語システムになっているので、型システムはオブジェクト指向が核になります。このためオブジェクト指向の型システムを使って代数的データ型を実現すると全体の整合性が取れるということだと思います。

代数的データ型は選択と組み合わせて使用します。選択はScalaではmatch式で記述します。

先ほどの代数的データ型Aは以下のようにして選択を適用することができます。match式では「抜け漏れ」があるとコンパイル時に「match is not exhaustive!」の警告が出ます。

def f(a: A) = {
  a match {
    case b: B => xxx
    case c: C => xxx
    case d: D => xxx
  }
}
代数的データ型として気をつけること

前の説明で、「クラスのインヘリタンス」と「代数的データ型の選択」を対置しましたが、ケースクラスでは「代数的データ型の選択」の実現に「クラス(トレイト)のインヘリタンス」を使うというややねじれた構造になっています。しかし、これはScala言語の構成に適した実現方式ということであって、オブジェクト指向のクラスの機能を積極的に使うという意図ではない、という点は留意しておくとよさそうです。

ケースクラスは代数的データ型として使用するが想定されているクラスですが、文法的にそのことを強制する制約はないので、普通のクラスとして色々な機能を追加することができます。しかし、関数型プログラミングの中で代数的データ型としての用途を意識するケースでは、こういったオブジェクト指向的な機能の濫用は避けるのが賢明です。

列挙型

代数的データ型の応用として列挙型を表現する事ができます。この場合はケースクラスではなく、ケースオブジェクトを使うとよいでしょう。ケースオブジェクトを使うと、「Sunday()」ではなく「Sunday」という形で列挙型を使うことができるようになります。また、オブジェクトの生成を抑制する効果もあります。

ScalaではEnumというオブジェクトが用意されていますが、使い勝手が悪いので列挙型はケースオブジェクトを使うのを軸に考えるとよいと思います。ケースオブジェクトを使うことで「代数的データ型」的な効果(match式の抜け漏れチェックなど)も期待できます。

sealed trait DayWeek
case object Sunday extends DayWeek
case object Monday extends DayWeek
case object Tuesday extends DayWeek
case object Wednesday extends DayWeek
case object Thursday extends DayWeek
case object Friday extends DayWeek
case object Saturday extends DayWeek

列挙型の実現は、ケースオブジェクトではなく普通のオブジェクトを使うことも可能です。

sealed trait DayWeek
object Sunday extends DayWeek
object Monday extends DayWeek
object Tuesday extends DayWeek
object Wednesday extends DayWeek
object Thursday extends DayWeek
object Friday extends DayWeek
object Saturday extends DayWeek

ただ、ケースオブジェクトの方が以下のようなメリットがあるので、普通はケースオブジェクトにしておくとよいでしょう。

  • Productを継承して型システム上も直積つまり代数的データ型になる。
  • toStringで「Sunday」や「Monday」といった文字列が表示されるようになる。
  • Serializableになる。

スライド案

代数的データ型、ケースクラス、ケースオブジェクトについて考えてきましたが、Monadicプログラミングのテーマでセッション1時間に収めることを考えると、このあたりはほとんど触れることはできなさそうです。

「代数的データ型」のタイトルのスライドに以下のプログラムを載せておく感じかな。

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

sealed trait A
case class B() extends A
case class C() extends A
case class D() extends A

sealed trait DayWeek
case object Sunday extends DayWeek
case object Monday extends DayWeek
case object Tuesday extends DayWeek
case object Wednesday extends DayWeek
case object Thursday extends DayWeek
case object Friday extends DayWeek
case object Saturday extends DayWeek

2012年7月18日水曜日

クラウド温泉3.0 (2) / 代数的データ型

クラウド温泉3.0@小樽のセッション「Monadicプログラミング・マニアックス」で使用するスライドのネタ検討その2です。

関数型プログラミングの基本構成要素の一つに代数的データ型があります。Wikipediaによる定義は以下です。

ボク自身は計算機科学や数学の素養がないので、Wikipediaの定義が厳密には何を指しているのか十分に理解ができているとはいえないのですが、ボクと同じ立ち位置にいる非計算機科学系のプログラマの方には、ボクがプログラミング時に使用している非公式な理解が不正確なものであっても有益ではないかと思います。

その前提で、以下でScalaでの代数的データ型について考えます。

非公式な理解

ボクが代数的データ型を意識するときは、以下の定義を念頭に置いています。

  • 直積の直和の総和

直積は、「A×B×C」というように記述する複数の要素を組にしたものです。Scalaではタプルが直積の代表的な記述方式です。

直和は、「互いに交わらない、つまり共通部分が空集合であるような二つの集合の和集合」です。「A∪B」でAとBでダブリがない場合が該当します。ScalaではEitherが直和の代表的な記述方法です。

「直積の直和」は以下のようにイメージしています。

T = (A × B × C) ∪ (D × E)

直和は2つの和集合なので、これを複数の集合の和集合に拡張して考える必要があります。ここでは、これを総和と表現しています。

「直積の直和の総和」は以下のようにイメージしています。

T = (A × B × C) ∪ (D × E) ∪ (F × G × H)

「直積の直和の総和」であるTは以下の意味を持ちます。

  • Tは(A × B × C)の組、(D × E)の組、(F × G × H)の組のいずれかで、それ以外の値は持たない。

直和であることでダブリがないことに加えて「それ以外の値は持たない」となるわけですが、この性質が本質的に重要です。「それ以外の値は持たない」ので、選択処理で抜け漏れが発生することが絶対にないことを保証することができます。Scalaの場合は、コンパイル時にmatch式に対して「match is not exhaustive!」という警告を出すといった動きになります。

関数型プログラミングとオブジェクト指向プログラミング

最近のプログラミング言語は、関数型言語もオブジェクト指向言語も相互に影響を受けて便利そうな機能は同様に使えることが多く、境界線は曖昧です。例題レベルの簡単なプログラムだと、どちらも同じようにコーディングできることも多いでしょう。

このため、関数型プログラミングとオブジェクト指向プログラミングの本質的な違いは何かというのはかなり難しい問題ですが、JavaやScalaでプログラミングしている中で、情況証拠的に分かってきたのは「インヘリタンスの有無」がその本質ではないかということです。これは「動的に解決される多相性の有無」ということもできます。言葉を変えると、コンパイル時に抜け漏れが起きないことを保証できるのが関数型言語で、保証できないのがオブジェクト指向言語という表現もできます。

逆に、静的に解決される多相性は(オブジェクト指向でも有効ですが)関数型言語の守備範囲で、型クラスがこの代表的な機能になります。

もちろん、抜け漏れがあるオブジェクト指向言語が劣るとういうことではなく、動的にシステムを拡張できるという重要な性質の裏返しということです。プラグインをコンポーネントとして追加してアプリケーションを拡張する、といったアプローチはオブジェクト指向ならではということですね。

まとめると、オブジェクト指向では型(クラス)に毎に適用するロジックを切り替える処理はクラスのインヘリタンスによる多相性で実現します。これを関数型では以下のいずれかで実現します。

  • 代数的データ型に対する選択
  • 型クラス

型クラスはちょっとビッグな機能で日々のプログラミングで気軽に定義して使うものではないので、ざっくりといってしまうと、以下のように考えることができます。

  • オブジェクト指向はインヘリタンス
  • 関数型は代数的データ型で選択

そう考えていくと、代数的データ型は関数型プログラミングをする上で、かなり重要な機能であることが分かります。また、Scalaで関数型プログラミングを行う場合は、インヘリタンスは使わず「代数的データ型で選択」に持っていくことが正しい作法ということになりそうです。

Scala

と、ここからScalaの実装に入りたいところですが、長くなってしまったので次回にします。

2012年7月17日火曜日

「Monadicプログラミング」の狙い

クラウド温泉3.0@小樽のセッション「Monadicプログラミング・マニアックス」で使用するスライドのネタ検討その1です。

セッションはMonadicプログラミングがテーマですが、そもそもMonadicプログラミングをすると何がよいのか、ということをまず明らかにしておかないといけません。

ひとつは、プログラミングが簡潔になる、部品の再利用性が上がる、といった日々のプログラミングの効率に関するメリットです。これは、使ってみると日々実感するわけですが、使っていない人にはあまり響かない切り口と思います。

そういう意味では、ボクも当初それほど興味はなく、簡潔⇒コードゴルフ的なコードになってしまうというデメリットもあるので、積極的に採用しなくてもよいのではないかと思っていました。旧世代のプログラマとしては、永続データ構造をベースとした富豪プログラミングに対する違和感もあります。

ボクがScalaを始めた動機はDSL(Domain Specific Language)で、内部DSLのホスト言語としてScalaは非常に有効であることが確認できました。これをオブジェクト指向言語+αで使えば十分と考えていたわけです。

並行プログラミング

ところが、以下のスライドを見て考えが変わりました。

これはScalazでの並行関数型プログラミングを説明したものですが、特にComposing concurrent functionsのあたりをみて、並行プログラミングはこちらの方向に進むのではないかと感じました。つまり、モナドの基盤の上に並行プログラミングの部品を構築しているプログラミング・モデルです。

このプログラミング・モデルの上で並行プログラミングを行うためには、Monadicプログラミングが必須になります。

Scalazを本格的に調べ始めたのは、これがきっかけです。

データフロー

そしてもう一つ、Monadicプログラミングの適用分野としているのがデータフローです。

OFAD

個人的に最も興味のあるテーマは、モデリング+プログラミングを融合した技術領域です。本ブログの名前の「Modegramming」の由来にもなっています。

モデリングについては、ビジネス・モデリングの下半分から分析、設計までの一気通貫をプログラミングと連続性を持たせた形でどう実現するのかが興味の対象です。

OOAD/OOP時代のボクなりの結論は本にまとめることができました。

今興味を持っているのは、実装技術と実行環境がそれぞれ関数型言語(正確にはオブジェクト+関数)とクラウド・プラットフォームに進化していく中で、モデリング技術がどの方向に進化していくことになるのか、という点です。

基本な考察は「Object-Functional Analysis and Designふたたび」などで行なっていますが、データフローがひとつの鍵になるかなと考えています。

DSL

データフローは、以前からg3(g3 (クラウド温泉@小樽))を軸にDSL化を模索していて、いくつか検討や試作を行なっています。

当初はUNIXのパイプライン的なメカニズムをベースにデータフローを記述することを考えていたのですが、最近はMonadicなアプローチが面白そうと考えるようになってきました。

ひとつは、Monadicプログラミングは一種のパイプライン・プログラミングということが分かってきたことです。パイプラインのメカニズムをフレームワークで用意するより、Monadicな基盤の上に構成した方がより汎用性が高まります。

もう一つは、Monoidの適用です。データフローの処理をストリームの畳込みと考えると、データフローのプロセスをMonoidとして抽象化する方向性も有効そうです。データ処理の詳細を記述するためのDSLという観点では、Monoidの枠組みは便利に使えそうという感触もあります。

以上の点から、Monadicプログラミングをデータフロー記述のベースとして期待しているわけです。

スライド

Monadicプログラミングの具体的な適用分野として、並行プログラミングとデータフローが有力な候補ということを説明しました。どちらもクラウドコンピューティングで重要な技術となりそうなので、そいういう意味ではMonadicプログラミングはクラウドコンピューティングにつながっている技術ということになります。

スライドには以下の3項目を書いて、このあたりの話をしていく感じになるかもしれません。

  • ロジック記述
  • 並行プログラミング
  • データフロー

クラウド温泉的にもよい流れですね。

2012年7月13日金曜日

クラウド温泉3.0@小樽

今年もクラウド温泉の季節がやってきました。

今回もかなり濃い内容になりそうで楽しみです。ustreamなしのオフレコなので、かなり踏み込んだ話を聞けるのもクラウド温泉の醍醐味ですね。

今回は2つほどスライドを用意する予定です。

  • Monadicプログラミング・マニアックス
  • OFP & OFADについて(仮)

連休明けぐらいから、この2つのスライドについて:

で行ったような感じで、準備がてらブログに内容をあげていきたいと思います。この時は、以下のようなまとめを作りましたが、今回も作ることになると思います。

Monadicプログラミング・マニアックス

「Monadicプログラミング・マニアックス」というタイトルにしていますが、内容的にはScalazを使った関数型プログラミング入門という感じになると思います。現時点でScalaとScalazを使っている事自体がマニア、ということで。

内容的には、去年のJJUGで使った「楽々Scalaプログラミング」を起点にMonadicプログラミングの技やプログラミング戦略を色々書いていこうと思います。

http://www.slideshare.net/asami224/scala-9728001

キーワード: モナド、モノイド、型クラス、代数的データ型、永続データ構造、並列プログラミング、SQL。

OFP & OFADについて(仮)

こちらは、二日目午後に小樽商大会議室で行うフリーディスカッション「OFP & OFADについて」のネタ投入用のスライドです。基本的には「Object-Functional Analysis and Design: 次世代モデリングパラダイムへの道標」をそのまま使う予定ですが、OFADについて少し書き足したいこともあるので内容を追加できればと思っています。

このスライド起点の議論はOFADよりのものを想定していますが、これとは別にOOPとFP、OFPを軸にした議論もあると思うのでそちらも楽しみです。OOPもJavaのように実用志向で手続き型寄りのものが主流になっていますが、元祖オブジェクト指向でメッセージングのメタファを持つSmalltalkやJavaScriptのようなプロトタイプベースなど色々なバリエーションがあります。

個人的には業務アプリのプログラミングパラダイムはOOPからOFPにパラダイムシフトしていくと思っているのですが、このタイミングでOOPやFPの原点に立ち戻って議論することで、新しいOFP像を垣間見ることができればと期待しています。

2012年7月12日木曜日

Scala Tips / Validation (36) - Reducer

Validation (35) - Monoid」でValidationをMonoidとして定義したので、Reducerで直接使うことができるようになりました。

たとえば、以下のように使用することができます。

scala> List(1.success[NT], 2.success[NT], 3.success[NT]).foldReduce(implicitly[Foldable[List]], Reducer(x => x))
res20: scalaz.Validation[ValidationNELThrowables.NT,Int] = Success(6)

Monoid - 新規作成」、「Reducer (5) - 演算Monoid」では、Monoid Averageを使ってPersonの集まりの平均年齢を計算しました。今回は、Monoid化したValidationを適用してみます。

MonoidであるAverageは以下になります。

case class Average(total: Int, count: Int) {
  def +:(a: Int) = Average(total + a, count + 1)
  def :+(a: Int) = Average(total + a, count + 1)
  def +(a: Average) = Average(total + a.total, count + a.count)
  def value: Float = if (count == 0) 0 else total.toFloat / count
}

trait Averages {
  implicit def AverageZero: Zero[Average] = zero(Average(0, 0))
  implicit def AverageSemigroup: Semigroup[Average] = semigroup((a, b) => a + b)
}

object Averages extends Averages

Personの定義とテスト用のインスタンスは以下になります。

case class Person(name: String, age: Int)
val taro = Person("Taro", 35)
val hanako = Person("Hanako", 28)
val saburo = Person("Saburo", 43)

type NT = NonEmptyList[Throwable]

val persons = List(taro.success[NT], hanako.success[NT], saburo.success[NT])

使ってみる

Validationに格納されているPersonの属性ageの集まりから平均値を計算します。このためにValidation[Person]をValidation[Average]にしてReduce処理を行うReducerをfoldReduceメソッドに適用します。

scala> val a = persons.foldReduce(implicitly[Foldable[List]], Reducer(_.map(x => Average(x.age, 1))))
a: scalaz.Validation[NT,Average] = Success(Average(106,3))

scala> a.map(_.value)
res28: scalaz.Validation[NT,Float] = Success(35.333332)

ノート

今回の応用例は実際には以下のようにsequenceメソッドやtraverseメソッドを使う方法の方が簡単です。

sequenceメソッドを使う場合は、sequenceメソッドでList[ValidationNEL[Throwable, Person]]をValidationNEL[Throwable, List[Person]]に変換した後、List[Person]から平均年齢を求めます。

persons.sequence[VNT].map(x => x.map(_.age).sum.toFloat / x.length)

traverseメソッドを使う場合は、traverseメソッドでList[ValidationNEL[Throwable, Person]]をValidationNEL[Throwable, Int]に変換した後、List[Int]から平均年齢を求めます。

persons.traverse[VNT](_.age).map(x => x.sum.toFloat / x.length)

いずれもList[ValidationNEL[Throwable, Person]]の形をList[Person]やList[Int]というアルゴリズムを適用しやすい形にする戦略です。

そういう意味では、今回も含めReducerを使う一連の記事は日々のプログラミングで使用するイディオムとしてはすぐには活用できないかもしれません。

Reducer (5) - 演算Monoid」ではMonoidとReducerで以下の抽象化が行われることを説明しました。

ドメインオブジェクト
任意のオブジェクト(Person)
Monoid
汎用の演算+値の対を表現したモノイド(Average)
Reducer
汎用のモノイドの集まりを畳込みで1つのモノイドに集約する戦略&ドメインオブジェクトとモノイドを結びつける

今回はさらに以下の要素が加わっています。

Monad(またはApplicative)かつMonoid
汎用の計算文脈(Validation) かつMonoid。計算文脈がMonoidとして畳込み演算の対象とできる。

これらの4つの要素から構成されるメカニズムが今回のテーマというわけです。

「Monad(またはApplicative)かつMonoid」に格納された「ドメインオブジェクト」に対して、汎用演算を行う「Monoid」部品と汎用の畳込み戦略部品を結びつけるのが「Reducer」である、という構造になります。これをListなどのFoldableに対してfoldReduceメソッドで適用します。

構造が複雑なだけに、平均値の計算のような簡単な応用ではオーバースペックですが、もっと複雑な応用ではピッタリとハマるユースケースもあるのではないかと思います。

個人的には「Monad(またはApplicative)かつMonoid」としてPromiseのような並列演算のモナドを使うような応用を一つのターゲットとして考えています。この場合、sequenceメソッドやtraverseメソッドを使うと計算の開始時点で同期が発生してしまい、つまらない結果になりそうです。Promiseをそのまま維持する形で計算を進め、最後に一括して同期を行うようなことをする場合には、Reducerのようなメカニズムが有効に働くかもしれません。このあたりが今後の研究課題です。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年7月11日水曜日

Scala Tips / Validation (35) - Monoid

Validation (34) - Semigroup」ではValidationをSemigroup化しました。その結果、演算子|+|が使用できるようになりました。

しかしSemigroup化しただけではMonoidの機能を十分に活用することはできません。たとえばsumrメソッドはMonoidが対象なので、以下のようにエラーになってしまいます。この他foldMapメソッドなどSemigroupではなくMonoidを対象にしたメソッドは多数存在しているので、できればSemigroupではなくMonoid化しておくのが得策です。

scala> List(1.success[NT], 2.success[NT], 3.success[NT]).sumr
<console>:19: error: could not find implicit value for parameter m: scalaz.Monoid[scalaz.Validation[ValidationNELThrowables.NT,Int]]
              List(1.success[NT], 2.success[NT], 3.success[NT]).sumr
                                                                ^

ScalazのMonoidはZeroとSemigroupの両型クラスを継承しています。前回はValidationの型クラスSemigroupインスタンスを作成してValidationを型クラス化しました。これに加えて型クラスZeroインスタンスを作成すれば、ValidationのZero化が行われ、同時にMonoid化も達成されます。

Validationの型クラスZeroインスタンスを追加したコードが以下になります。暗黙値VNTZeroとしてValidation[NonEmptyList[Throwable], A]に対する型クラスZeroインスタンスを定義しています。

trait ValidationNELThrowables {
  type NT = NonEmptyList[Throwable]
  type VNT[A] = Validation[NT, A]

  implicit def VNTZero[A: Zero]: Zero[VNT[A]] = zero(mzero[A].success)
  implicit def VNTSemigroup[A: Semigroup]: Semigroup[VNT[A]] = semigroup((a, b) => { (a, b) match {
    case (Success(va), Success(vb)) => Success(va |+| vb)
    case (Success(va), Failure(_)) => Success(va)
    case (Failure(_), Success(vb)) => Success(vb)
    case (Failure(ea), Failure(eb)) => Failure(ea |+| eb)
  }})
}

object ValidationNELThrowables extends ValidationNELThrowables

VNTZeroでは、Validation[NonEmptyList[Throwable], A]がZeroであるためには、格納するオブジェクトもZeroであることを条件にしています。そしてValidation[NonEmptyList[Throwable], A]の零元は、格納するオブジェクトの零元を作成し、これをSuccessに格納にしたものになります。

動かしてみる

Validation (34) - Semigroup」でValidationのSemigroup化、そして今回ValidationのZero化を行いました。SemigroupかつZeroのオブジェクトは自動的にMonoidとなります。つまりValidationをMonoidとして使用できるようになったわけです。その結果Monoidを対象としたさまざまなメソッドでValidationを使用できるようになりました。

sumrメソッドを使った結果は以下になります。

scala> List(1.success[NT], 2.success[NT], 3.success[NT]).sumr
res25: scalaz.Validation[ValidationNELThrowables.NT,Int] = Success(6)

foldMapメソッドも普通に使えるようになりました。

scala> List(1, 2, 3).foldMap(_.success[NT])
res39: scalaz.Validation[NT,Int] = Success(6)

ノート

Optionの型クラスZeroインスタンスの仕様では零元としてNoneが返されます。

scala> mzero[Option[Int]]
res2: Option[Int] = None

Optionの型クラスSemigroupインスタンスの仕様では、NoneとSomeをモノイド演算(演算子|+|)するとSomeとなります。このためNoneは零元(単位元)として機能しています。

scala> 1.some |+| 2.some
res9: Option[Int] = Some(3)

scala> 1.some |+| none
res10: Option[Int] = Some(1)

scala> none |+| 2.some
res11: Option[Int] = Some(2)

scala> 1.some |+| 2.some
res12: Option[Int] = Some(3)

Validationの実装でも、この選択を取ってもよいのですが:

Failure(NonEmptyList(java.lang.Throwable: zero))

が単位元というのも少し違和感があるので、今回の実装では:

scala> mzero[VNT[Int]]
res17: ValidationNELThrowables.VNT[Int] = Success(0)

となるようにしました。

Scalazの選択が前者の方式になっているので、数学的にはその方が筋がよい可能性がありますが、そのあたりの事情はよくわかりません。情報をいただけると助かります。

>>*<<メソッド

Validationが格納するオブジェクトがMonoidで、Validationのコンテナの結合戦略がOR演算である場合、Validationの>>*<<メソッドを使うことができます。(「Validation (26) - fold monoid or」)

このためSemigroupの実装は>>*<<メソッドを使うとより簡潔になります。>>*<<メソッドを使って改良したValidationNELThrowablesは以下になります。

trait ValidationNELThrowables {
  type NT = NonEmptyList[Throwable]
  type VNT[A] = Validation[NT, A]

  implicit def VNTZero[A: Zero]: Zero[VNT[A]] = zero(mzero[A].success)
  implicit def VNTSemigroup[A: Semigroup]: Semigroup[VNT[A]] = semigroup((a, b) => a >>*<< b)
}

object ValidationNELThrowables extends ValidationNELThrowables

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年7月10日火曜日

Scala Tips / Validation (34) - Semigroup

ScalazのOptionはMonoidとしても動作します。Option内にMonoidを格納している場合、Optionを|+|演算することでOption内に格納しているMonoidも自動的に|+|演算が適用されます。

scala> 1.some |+| 2.some
res10: Option[Int] = Some(3)

scala> 1.some |+| none
res11: Option[Int] = Some(1)

scala> none |+| 2.some
res12: Option[Int] = Some(2)

scala> none[Int] |+| none[Int]
res14: Option[Int] = None

とても便利な機能ですが、残念ながらValidationはこの機能をもっていません。

そこでValidationそのものをMonoidとして使用することを考えてみましょう。

Monoidの前段階としてSemigroupがあります。Semigroupは半群を表す型クラスです。Monoidの演算子|+|はSemigroupで定義されています。

ValidationをMonoid化するための準備として、ValidationをSemigroup化します。

ValidationNELThrowables

ValidationをSemigroup化するための実装として以下を作成しました。トレイトValidationNELThrowablesまたはオブジェクトValidationNELThrowablesに暗黙パラメタとして定義されているValidationNELのSemigroup型クラスインスタンスを読み込んで使用します。

trait ValidationNELThrowables {
  type NT = NonEmptyList[Throwable]
  type VNT[A] = Validation[NT, A]

  implicit def VNTSemigroup[A: Semigroup]: Semigroup[VNT[A]] = semigroup((a, b) => { (a, b) match {
    case (Success(va), Success(vb)) => Success(va |+| vb)
    case (Success(va), Failure(_)) => Success(va)
    case (Failure(_), Success(vb)) => Success(vb)
    case (Failure(ea), Failure(eb)) => Failure(ea |+| eb)
  }})
}

object ValidationNELThrowables extends ValidationNELThrowables

Validationのコンテナ自身を結合する戦略としてはAND演算とOR演算がありますが、ここではOptionの仕様にあわせてOR演算を採用しています。

使ってみる

準備として型クラスインスタンスを読み込みます。

scala> import ValidationNELThrowables._
import ValidationNELThrowables._

Success同士のモノイド演算を行うと、Success内に格納されているMonoid同士にモノイド演算が適用されます。

scala> 1.success[NT] |+| 2.success[NT]
res1: scalaz.Validation[ValidationNELThrowables.NT,Int] = Success(3)

一方がSuccess、もう一方がFailureの場合はSuccessの方が使用されます。

scala> 1.success[NT] |+| new IllegalArgumentException("bad").failNel
res2: scalaz.Validation[ValidationNELThrowables.NT,Int] = Success(1)

scala> (new IllegalArgumentException("bad").failNel[Int]: Validation[NT, Int]) |+| 2.success[NT]
res19: scalaz.Validation[ValidationNELThrowables.NT,Int] = Success(2)

両方がFailureの場合はFailureになります。

scala> (new IllegalArgumentException("bad 1").failNel[Int]: Validation[NT, Int]) |+| new IllegalArgumentException("bad 2").failNel[Int]
res21: scalaz.Validation[ValidationNELThrowables.NT,Int] = Failure(NonEmptyList(java.lang.IllegalArgumentException: bad 1, java.lang.IllegalArgumentException: bad 2))
型の指定

「new IllegalArgumentException("bad").failNel[Int]」はValidation[NT, Int]と型が合わないらしく演算の左側に持ってくると以下のようにエラーとなります。

scala> new IllegalArgumentException("bad").failNel[Int] |+| new IllegalArgumentException("bad").failNel[Int]
<console>:19: error: could not find implicit value for parameter s: scalaz.Semigroup[scalaz.Scalaz.ValidationNEL[java.lang.IllegalArgumentException,Int]]
              new IllegalArgumentException("bad").failNel[Int] |+| new IllegalArgumentException("bad").failNel[Int]
                                                               ^

この問題を回避するためには「(new IllegalArgumentException("bad").failNel[Int]: Validation[NT, Int])」と型を指定する必要があるようです。

以下のように関数引数の場合は、「new IllegalArgumentException("bad").failNel[Int]」はValidation[NT, Int]と認識されます。

def f[A: Monoid](a: VNT[A], b: VNT[A]): VNT[A] = {
  import ValidationNELThrowables._
  a |+| b
}

このため、以下のように型指定をしなくても動作します。プログラミング時にはこの形に持ち込めば、余分な型指定を回避することができます。

scala> f(1.success, 2.success)
res4: ValidationNELThrowables.VNT[Int] = Success(3)

scala> f(1.success, new IllegalArgumentException("bad").failNel)
res7: ValidationNELThrowables.VNT[Int] = Success(1)

scala> f(new IllegalArgumentException("bad").failNel, 2.success)
res6: ValidationNELThrowables.VNT[Int] = Success(2)

scala> f(new IllegalArgumentException("bad 1").failNel[Int], new IllegalArgumentException("bad 2").failNel[Int])
res9: ValidationNELThrowables.VNT[Int] = Failure(NonEmptyList(java.lang.IllegalArgumentException: bad 1, java.lang.IllegalArgumentException: bad 2))

ノート

あるクラスをSemigroupにすることが可能になるためには、型パラメータが1つであることという条件があります。Validationの型パラメータ数は2で、これがValidationがMonoidとして定義されていない理由の一つだと思います。

幸いなことに本ブログではValidationのFailure側はNonEmptyList[Throwable]を基本に考えているので、型パラメータの一つをNonEmptyList[Throwable]に固定することができます。このため、ValidationをMonoid化するための条件が整っています。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年7月9日月曜日

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

2012年7月6日金曜日

Scala Tips / Option (13) - Monoid 短絡OR

前回はScalazのOptionはMonoidとしても使用できる事を説明しました。

scala> 1.some |+| 2.some
res10: Option[Int] = Some(3)

scala> 1.some |+| none
res11: Option[Int] = Some(1)

scala> none |+| 2.some
res12: Option[Int] = Some(2)

scala> none[Int] |+| none[Int]
res14: Option[Int] = None

scala> List(1.some, 2.some, 3.some, 4.some).sumr
res32: Option[Int] = Some(10)

scala> List(1.some, 2.some, none, 4.some).sumr
res20: Option[Int] = Some(7)

Optionのコンテナ側の畳込み戦略はOR演算でした。この場合は、Noneでないものをすべて足し込むという振舞いになります。

短絡OR

コンテナ側の畳込み戦略として短絡評価も考えられます。

短絡評価では、最初に有効となった値が使用されます。

Scalazでは短絡評価のモノイド演算を行うOptionとしてFirstOptionを提供しています。OptionのfstメソッドでFirstOptionを取得できます。

scala> 1.some.fst
res42: scalaz.FirstOption[Int] = Some(1)

FirstOption同士を演算子|+|でモノイド演算すると以下のように最初に登場したSomeが使用されます。

scala> 1.some.fst |+| 2.some.fst
res15: scalaz.FirstOption[Int] = Some(1)

scala> 1.some.fst |+| none.fst
res44: scalaz.FirstOption[Int] = Some(1)

scala> none.fst |+| 2.some.fst
res45: scalaz.FirstOption[Int] = Some(2)

scala> none[Int].fst |+| none[Int].fst
res48: scalaz.FirstOption[Int] = None

短絡ORは畳込みで使用すると効果がみえてきます。いずれの場合も最初に登場した(先頭に近い)Someが使用されます。

scala> List(1.some, 2.some, 3.some, 4.some).map(_.fst).sumr
res35: scalaz.FirstOption[Int] = Some(1)

scala> List(1.some, 2.some, none, 4.some).map(_.fst).sumr
res37: scalaz.FirstOption[Int] = Some(1)

scala> List(none, 2.some, 3.some, 4.some).map(_.fst).sumr
res36: scalaz.FirstOption[Int] = Some(2)

LastOption

短絡ORとは反対に、最後に登場したSomeを使いたいケースもあるかもしれません。Scalazはその用途に使用できるLastOptionを提供しています。

OptionのlstメソッドでLastOptionを取得できます。

scala> 1.some.lst
res49: scalaz.LastOption[Int] = Some(1)

LastOption同士を演算子|+|でモノイド演算すると以下のように最後に登場したSomeが使用されます。

scala> 1.some.lst |+| 2.some.lst
res18: scalaz.LastOption[Int] = Some(2)

scala> 1.some.lst |+| none.lst
res51: scalaz.LastOption[Int] = Some(1)

scala> none.lst |+| 2.some.lst
res52: scalaz.LastOption[Int] = Some(2)

scala> none[Int].lst |+| none[Int].lst
res53: scalaz.LastOption[Int] = None

LastOptionをsumrメソッドで使用すると以下の振舞いになります。いずれも最後のSomeが畳込み結果となります。

scala> List(1.some, 2.some, 3.some, 4.some).map(_.lst).sumr
res38: scalaz.LastOption[Int] = Some(4)

scala> List(1.some, 2.some, none, 4.some).map(_.lst).sumr
res39: scalaz.LastOption[Int] = Some(4)

scala> List(none, 2.some, 3.some, 4.some).map(_.lst).sumr
res40: scalaz.LastOption[Int] = Some(4)

scala> List(1.some, 2.some, 3.some, none).map(_.lst).sumr
res41: scalaz.LastOption[Int] = Some(3)

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年7月5日木曜日

Scala Tips / Option (12) - Monoid

ScalazのOptionはMonoidとしても定義されています。

Scalazの型クラス」で説明したように型クラスMonoidは型クラスZeroと型クラスSemigroupを継承しています。

Semigroup

Monoidの性質のうちSemigroupが提供しているのは演算子|+|によるモノイド演算です。

Optionは、格納するオブジェクトがMonoidである場合、Monoidとして動作します。

両方のOptionがSomeの場合、格納されているMonoid同士に演算子|+|で演算した結果がSomeに格納されます。

scala> 1.some |+| 2.some
res10: Option[Int] = Some(3)

どちらか一方がNoneの場合は、Someの方が演算子|+|の演算結果となります。

scala> 1.some |+| none
res11: Option[Int] = Some(1)

scala> none |+| 2.some
res12: Option[Int] = Some(2)

両方共Noneの場合はNoneになります。

scala> none[Int] |+| none[Int]
res14: Option[Int] = None

Zero

Monoidはmzero関数で単位元(零元)を生成することができます。

Optionの場合は以下になります。

scala> mzero[Option[Int]]
res19: Option[Int] = None

Option[Int]の単位元としては、「Some(0)」が返ってきた方がよい場合もあると思いますが、現実装ではNoneが返ります。

使ってみる

OptionがMonoidであることを利用すると、以下のように直接sumrメソッドを適用することができます。

scala> List(1.some, 2.some, 3.some, 4.some).sumr
res32: Option[Int] = Some(10)

scala> List(1.some, 2.some, none, 4.some).sumr
res20: Option[Int] = Some(7)

OptionのMonoidの場合はOptionのコンテナ側の畳込みがOR演算的な処理になるので、Noneは無視されてSomeのみが畳み込まれます。

sequence

比較のためにsequenceメソッドを使ってみましょう。

scala> List(1.some, 2.some, 3.some, 4.some).sequence[Option, Int].map(_.sum)
res28: Option[Int] = Some(10)

scala> List(1.some, 2.some, none, 4.some).sequence[Option, Int].map(_.sum)
res27: Option[Int] = None

この場合は、1つでもNoneがあると結果もNoneになります。Optionのコンテナ側の畳込みがAND演算的な処理になります。

Applicative

Applicative Functorとして畳込む場合も、sequenceメソッドと同様にAND演算になります。

scala> List(1.some, 2.some, 3.some, 4.some).foldRight(0.some) { (x, a) => (x |@| a)(_ + _)}
res34: Option[Int] = Some(10)

scala> List(1.some, 2.some, none, 4.some).foldRight(0.some) { (x, a) => (x |@| a)(_ + _)}
res29: Option[Int] = None
mzeroは注意が必要

OptionをMonoidとして畳み込む時に注意が必要なのはmzero関数の結果がNoneになってしまう点です。このため、以下のようにApplicativeを使った畳込みの初期値に指定すると、畳込み結果が必ずNoneになってしまいます。

scala> List(1.some, 2.some, 3.some, 4.some).foldRight(mzero[Option[Int]]) { (x, a) => (x |@| a)(_ |+| _)}
res31: Option[Int] = None

scala> List(1.some, 2.some, none, 4.some).foldRight(mzero[Option[Int]]) { (x, a) => (x |@| a)(_ |+| _)}
res30: Option[Int] = None

ノート

Optionのようなコンテナは、畳込みのコンテナ側の演算としてOR演算とAND演算の選択肢があります。

OptionをMonoidとして畳み込むとOR演算、sequenceやApplicative Functorを使うとAND演算になることが分かりました。この振舞いの違いは、用途別のイディオムとして活用できますね。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年7月4日水曜日

Scala Tips / Reducer Index

Reducerが一段落したので記事の一覧表をまとめておきます。

項目内容
ReducerIntProductReducerを素材にReducerの基本的な使い方
Reducer (2) - ListListReducerを素材に非可換MonoidでのReducerの振舞い
Reducer (3) - モノイド化非Monoidに対してReducerでモノイド演算を行う
Reducer (4) - 自前Reducer自前でReducerを用意する
Reducer (5) - 演算Monoid汎用MonoidをReducerでドメインオブジェクトに結びつける
GeneratorGeneratorで畳込み戦略、汎用Monoid、ドメインオブジェクトを結びつける

Reducerの操作対象であるMonoidについて以下の記事が前提となります。

IntProductReducerで使っているMonoidであるIntMultiplicationは以下の記事で説明しています。

以下は以前のScala Tipsの一覧です。

Either

項目内容
Either値の取得
Either (2) - flatMapflatMapで文脈の切替
Either (3) - getOrElsegetOrElseでデフォルト値を指定
Either (4) - getOrElse, FlatMapflatMapで変換後にgetOrElse
Either (5) - Exceptionscala.util.control.Exceptionで例外ハンドリング
Either (6) - Left, RightLeftとRightの生成
Either (7) - forfor式で変換
Either (8) - for, getOrElsefor式で変換後にgetOrElse
Either (9) - 二項演算二項演算の説明
Either (10) - 二項演算,AND「Either:AND」×「値:任意の関数で計算」
Either (11) - ApplicativeEitherに対するApplicative
Either (12) - Applicativeの記述方法Eitherに対するApplicative(続き)
Either (13) - 二項演算,AND,Monoid「Either:AND」×「値:Monoid」
Either (14) - 二項演算,AND,PlusEither:AND」×「値:Plus」
Either (15) - 二項演算,OR「Either:OR」×「値:任意の関数で計算」
Either (16) - 二項演算,OR,Monoid「Either:OR」×「値:Monoid」
Either (17) - 二項演算,OR,Plus「Either:OR」×「値:Plus」
Either (18) - Booleanと相互変換EitherとBooleanの相互変換
Either (19) - Optionと相互変換EitherとOptionの相互変換
Either (20) - Validationと相互変換EitherとValidationの相互変換
Either (21) - BifunctorEitherにBifunctorを適用

Option

項目内容
Option値の取得
Option (2)nullをOptionに持ち上げる方法
Option (3)map
Option (4)withFilter
Option (5)collect
Option (6)flatMap
Option (7)for式
Option (8)getOrElse
Option (9)withFilter, map, getOrElse
Option (10) - ExceptionflatMap, Exceptionハンドリング
Option (11) - Some/NoneSomeとNoneの記述方法
nullnullを値に持ち上げる方法

Optionについては以下の記事も参考になると思います。

2012年7月3日火曜日

Scala Tips / Generator

Reducerの使い方の一つとして、FoldableのfoldReduceメソッドを使う方法があります。ListやStreamといったSeqもFoldableですから、一般的にはSeqのfoldReduceメソッドを使う方法と考えてもよいでしょう。

foldReduceメソッドは手軽で良いのですが、あえて言えば畳込み戦略が固定化(通常は右畳込み戦略)されているのが懸念事項です。

そこで、畳込み戦略を選択するためのメカニズムとして用意されているのがGeneratorです。GeneratorはReducer向けに要素の集まりと畳込み戦略をカプセル化したオブジェクトです。Reducerを使って畳込みを行います。

Reducerは任意のオブジェクトを任意のMonoidと結びつけて、畳込み処理を行うための抽象といえます。また、GeneratorはReducerを任意の畳込み戦略に結びつけて畳込み処理を行うための抽象といえます。つまり、ReducerとGeneratorを併用することで、ドメインオブジェクト、Monoidの汎用部品、畳込み戦略の汎用部品を適材適所で組合せて使用することができるようになります。

今回はこのGeneratorの使い勝手を試して見ることにします。

課題は「Reducer (4) - 自前Reducer」、「Reducer (5) - 演算Monoid」と同じもの使うことにします。これにGeneratorを適用します。

課題

Personの集まりから平均年齢を計算します。ケースクラスPersonは以下のものとします。

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

Personの集まりを以下の通り定義します。

scala> val taro = new Person("Taro", 35)
taro: Person = Person(Taro,35)

scala> val hanako = new Person("Hanako", 28)
hanako: Person = Person(Hanako,28)

scala> val saburo = new Person("Saburo", 43)
saburo: Person = Person(Saburo,43)

scala> val persons = List(taro, hanako, saburo)
persons: List[Person] = List(Person(Taro,35), Person(Hanako,28), Person(Saburo,43))

準備

Reducer (5) - 演算Monoid」では、MonoidとしてAverageを、ReducerとしてPersonAgeAverageReducerを使用しました。それぞれ以下になります。

case class Average(total: Int, count: Int) {
  def +:(a: Int) = Average(total + a, count + 1)
  def :+(a: Int) = Average(total + a, count + 1)
  def +(a: Average) = Average(total + a.total, count + a.count)
  def value: Float = if (count == 0) 0 else total.toFloat / count
}

trait Averages {
  implicit def AverageZero: Zero[Average] = zero(Average(0, 0))
  implicit def AverageSemigroup: Semigroup[Average] = semigroup((a, b) => a + b)
}

object Averages extends Averages
object PersonAgeAverageReducer extends Reducer[Person, Average] {
  override def unit(c: Person) = Average(c.age, 1)
  override def cons(c: Person, m: Average) = c.age +: m
  override def snoc(m: Average, c: Person) = m :+ c.age
}

Generator

Generatorは畳込み戦略の抽象で、汎用の畳込み戦略の部品を用意できるメカニズムを備えていますが、現状で用意されている部品は以下の3つです。

Generator#FoldrGenerator
Foldableに対する右畳込み
Generator#FoldlGenerator
Foldableに対する左畳込み
Generator#FoldMapGenerator
Foldableに対するfoldMap畳込み

ここではFoldrGeneratorを使うことにします。

FoldrGeneratorを取得したあと、reduceメソッドにReducerとしてPersonAgeAverageReducerを、オブジェクトの集まりとしてPersonのListを指定すると以下に示すように平均を示すAverageオブジェクトが返されます。

scala> val g = Generator.FoldrGenerator[List]
g: scalaz.Generator[List] = scalaz.Generator$$anon$1@5fdde23d

scala> val a = g.reduce(PersonAgeAverageReducer, persons)
a: Average = Average(106,3)

scala> a.value
res27: Float = 35.333332

FoldrGeneratorの取得とreduceメソッドによる演算を一行にまとめると以下になります。

scala> Generator.FoldrGenerator[List].reduce(PersonAgeAverageReducer, persons)
res26: Average = Average(106,3)

scala> Generator.FoldrGenerator[List].reduce(PersonAgeAverageReducer, persons).value
res27: Float = 35.333332

ノート

Reducer (5) - 演算Monoid」で説明したようにfoldReduceメソッドの使い方は大きく以下の2つがあります。

scala> val avg = persons.foldReduce(implicitly[Foldable[List]], PersonAgeAverageReducer)
avg: Average = Average(106,3)
scala> val avg = {
     | implicit val r = PersonAgeAverageReducer
     | persons foldReduce
     | }
avg: Average = Average(106,3)

前者はimplicitlyを使うのが煩雑です。後者はわざわざ暗黙パラメタを使うのが大げさな感じがしますし、プログラムの見通しも悪くなりそうです。

そういう意味で、Generatorの使い勝手がよければGeneratorを使うのを基本戦略にしてもよいのですが、Generatorが際立って簡潔に書けるわけでもありません。

また、事前に定義されているGeneratorは、前述したようにFoldableの基本機能を使用する3つだけなので、豊富な汎用部品が用意されているという状況でもありません。

このため、状況に応じて好みで選択することになりますが、ボクの場合はfoldReduceメソッドとimplicitlyを使う方式を選ぶことが多くなりそうです。

畳込み戦略の選択

foldReduceメソッドでは、第一引数に指定するFoldableによって畳込み戦略が決まります。具体的にはFoldableのfoldMapメソッドの畳込み戦略が使用されます。Foldableのデフォルトの実装ではfoldMapは右畳込みを使用するのようなっていて、ListやSeqの場合に使われる型クラスインスタンスTraversableFoldableもこれを踏襲しています。つまり、foldReduceメソッドは概ね右畳込みを行うと考えておいてよいでしょう。

foldの選択」で説明した通りで普通の使い方では、右畳込み戦略が最良の選択でネガティブインパクトもほとんどないので、デフォルトの戦略としては妥当です。このため、普通はReducerはfoldReduceメソッドと組合せて使うと考えておけば十分でしょう。

複数の畳込み戦略の中から、状況に応じて畳込み戦略を切り替えるようなケースで、Generatorを用いる価値が出てきます。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4

2012年7月2日月曜日

Scala Tips / Reducer (5) - 演算Monoid

Monoid - 新規作成」では平均値を表現するモノイドAverageをScalazのMonoidとして作成しました。

case class Average(total: Int, count: Int) {
  def +:(a: Int) = Average(total + a, count + 1)
  def :+(a: Int) = Average(total + a, count + 1)
  def +(a: Average) = Average(total + a.total, count + a.count)
  def value: Float = if (count == 0) 0 else total.toFloat / count
}

trait Averages {
  implicit def AverageZero: Zero[Average] = zero(Average(0, 0))
  implicit def AverageSemigroup: Semigroup[Average] = semigroup((a, b) => a + b)
}

object Averages extends Averages

このAverage MonoidとReducerを組み合わせてモノイドではないオブジェクトPersonの平均年齢を求める処理を考えます。

ドメイン・オブジェクトと用途毎のモノイドをReducerで組み合わせるという使い方です。

課題は「Reducer (4) - 自前Reducer」と同じものです。これを専用Reducerを使って実現します。

課題

Personの集まりから平均年齢を計算します。ケースクラスPersonは以下のものとします。

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

Personの集まりを以下の通り定義します。

scala> val taro = new Person("Taro", 35)
taro: Person = Person(Taro,35)

scala> val hanako = new Person("Hanako", 28)
hanako: Person = Person(Hanako,28)

scala> val saburo = new Person("Saburo", 43)
saburo: Person = Person(Saburo,43)

scala> val persons = List(taro, hanako, saburo)
persons: List[Person] = List(Person(Taro,35), Person(Hanako,28), Person(Saburo,43))

PersonAgeAverageReducer

ドメイン・オブジェクトであるPersonと、汎用的なモノイドであるAverageを、モノイド演算による畳込み演算という切り口で結びつけるReducerとしてPersonAgeAverageReducerを作ります。

object PersonAgeAverageReducer extends Reducer[Person, Average] {
  override def unit(c: Person) = Average(c.age, 1)
  override def cons(c: Person, m: Average) = c.age +: m
  override def snoc(m: Average, c: Person) = m :+ c.age
}

Reducerは、「あるクラス」と「あるクラス」に対する別モノイド演算を定義した「別のクラス」を結びつける演算を行うオブジェクトです。元のクラスである「あるクラス」をC、「追加のモノイド演算」と「あるクラス」を結びつける「別のクラス」をMと表記することにします。

PersonAgeAverageReducerは、CがPerson、MがAverageになります。MonoidではないクラスPersonに対して、平均値の計算のための値とモノイド演算の対をパッケージングしたMonoidであるオブジェクトAverageを結びつけます。

使ってみる

それではPersonAgeAverageReducerを使ってPersonの集まりの平均年齢を計算してみましょう。

scala> val avg = persons.foldReduce(implicitly[Foldable[List]], PersonAgeAverageReducer)
avg: Average = Average(106,3)

scala> avg.value
res18: Float = 35.333332

Reducerを暗黙パラメタにすることで、foldReduceでimplicitlyの指定を減らすことができます。

scala> val avg = {
     | implicit val r = PersonAgeAverageReducer
     | ps.foldReduce
     | }
avg: Average = Average(106,3)

scala> avg.value
res19: Float = 35.333332

暗黙パラメタはプログラムの表層からは見えなくなるので予想外のバグを引き起こす危険性もあり使い方には注意が必要ですが、うまくハマるとかなり便利です。

適材適所で使い分けるとよいでしょう。

このケースの場合には、個人的には冗長でもimplicitlyを使って、暗黙パラメタを2つとも陽に指定する方式の方が良いかなと思います。

ノート

今回の課題は、以下のように普通にやっても簡単にかけるので、わざわざMonoidやReducerを持ち出す必要はありません。

scala> ps.map(_.age.toFloat).sum / ps.length
res21: Float = 35.333332

説明のために簡単な処理を課題として用いているからですが、もうちょっと込み入ったロジックであれば、使い所がありそうな予感がします。

お互いに疎の関係にある以下の2つのオブジェクトがあります。

  • 任意のオブジェクト(Person)
  • 任意の演算+値の対を表現したモノイド(Average)

また、以下の頻出の汎用的な演算があります。

  • モノイドの集まりを畳込みで1つのモノイドに集約する

この3つの要素を一つにまとめるためのオブジェクトがReducerということになります。

別の言い方をすると「モノイドの集まりを畳込みで1つのモノイドに集約する」をターゲットに「任意のオブジェクト」の"ある値"を「モノイド」に結びつけるのがReducerということです。「モノイド」として今回は汎用部品である平均値を考えましたが、他にも中央値や標準偏差といった部品も考えられます。

汎用部品としてのモノイドが整備されてくれば、これをアプリケーションのドメイン・オブジェクトと結びつけてロジックを組みたいケースも増えてくるでしょう。そういった状況になればReducerが活用できる場も増えてくるかもしれません。

諸元

  • Scala 2.9.2
  • Scalaz 6.0.4