読者です 読者をやめる 読者になる 読者になる

新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。気づけば社会人3年目に突入。

学習記録:Scala関数型デザイン 第7章

第7章:純粋関数型の並列処理(続き)

コンビネータを最も汎用的な形式に改良する

関数型の設計は反復的な作業になる。APIを書き出し,プロトタイプを実装した後は,
シナリオの複雑さや現実性を徐々に引き上げながら実際に使ってみることになる。
しかし,すぐに実装にとりかかる前に,必要なコンビネータを最も汎用的な形式に改良できるか調べてみることを勧める。

例として,以下の関数choiceを試してみる。

// フォークする2つの計算のどちらかを関数に選択させる
// condがtrueになる場合はtを,falseになる場合はfを実行する
def choice[A](cond: Par[Boolean])(t: Par[A], f: Par[A]): Par[A]

この実装は,condの結果を待ってブロックした後,その結果に基いてtかfを実行するだけである。

def choice[A](cond: Par[Boolean])(t: Par[A], f: Par[A]): Par[A] =
  es =>
    if (run(es)(cond).get) t(es) // condの結果を待ってブロックしている
    else f(es)

これで良しと先に進む前に,このコンビネータが何をしているのか少し考えてみよう。
condにより計算を選択することは一見合理的に見えるが,選択肢が2つに限定されていることは少し不自然に思える。
N個の計算から選択できた方が当然便利なはずである。

Exercise 7.11
  • N個の計算から選択するchoiceNを実装し,それをベースにchoiceを再実装せよ。

choiceNは以下のようになる。

  // nを実行した結果に基いてchoicesから並列計算を選択する           
  def choiceN[A](n: Par[Int])(choices: List[Par[A]]): Par[A] =
    es => {
      val res = run(es)(n).get
      run(es)(choices(res))
    }   

nを実行した結果のIntがresに入るので,choices(res)はList[Par[A]]のindexがresの値が渡されることになる。
これをベースにchoiceを実装すると,以下のようになる。

  // mapでPar[Boolean]を0か1のPar[Int]に変換し,choicesとしてList(t, f)を渡す
  def choiceViaChoiceN[A](cond:	Par[Boolean])(t: Par[A], f: Par[A]): Par[A] =
    choiceN(map(cond)(bool => if (bool) 0 else 1))(List(t, f))

mapを使ってList[Boolean]をList[Int]に変換し,第2引数にはList(t, f)を渡している。

ここまでの流れで,コンビネータchoiceをchoiceNに改良したところ,
結果的により汎用的になり,choiceでサポートされていなかった他のユースケースにも対応できるようになった。
しかし,ここで止まらずにさらに汎用的なコンビネータに改良できるか確かめてみよう。

Exercise 7.12

choiceNもやや不自然で,Listからの選択が具体的すぎる。

  • 例えば,計算のリストの代わりにそれらのMapを使った場合はどうなるか実装せよ。
def choiceMap[K,V](key: Par[K])(choices: Map[K, Par[V]]): Par[V]
    es => {
      val k = run(es)(key).get
      run(es)(choices(k))
    }

選択肢の集合をMapとして符号化するのも,Listと同じで具体的すぎるように思える。
choiceMapの実装を見ると,MapのAPIがあまり使用されていないことがわかる。
また,choiceとchoiceNの実装を改めて調べてみると,choiceでは引数のペアがBoolean => Par[A]型の関数として,
choiceNではリストがInt => Par[A]型の関数として使われているだけであることがわかる。

これらを1つにまとめる更に汎用的なシグネチャを作成してみると,以下のようになる。

def chooser[A,B](pa: Par[A])(choices: A => Par[B]): Par[B]
Exercise 7.13
  • このchooserを実装し,それを使ってchoiceとchoiceNを実装せよ。
  // choicesをA => Par[B]型の変数に変更している。 
  def chooser[A,B](pa: Par[A])(choices: A => Par[B]): Par[B] =
    es => {
      val res = run(es)(pa).get
      run(es)(choices(res))
    }

  // chooserを元にchoiceを実装                                                      
  def choiceViaChooser[A](cond: Par[Boolean])(t: Par[A], f: Par[A]): Par[A] =
    chooser(cond)(bool => if (bool) t else f)

  // chooserを元にchoiceNを実装                                             
  def choiceNViaChooser[A](n: Par[Int])(choices: List[Par[A]]): Par[A] =
    chooser(n)(i => choices(i))

これで,非常に汎用的なコンビネータchooserが出来上がった。
しかし,このレベルまで一般化するとchooserはもはや最適な名前であるとは言いがたい。
これは関数型ライブラリではよく見かける関数であり,通常はbindまたはflatMapという名前が付いている。

  // chooserの関数名を変えただけ
  def flatMap[A,B](pa: Par[A])(choices: A => Par[B]): Par[B] =
    es => {
      val res = run(es)(pa).get
      run(es)(choices(res))
    }

さて,このflatMapは最もプリミティブな関数なのだろうか。それとも更に一般化できるだろうか。
flatMapという名前は,この演算を2つのステップに分解できることを匂わせている。
Par[A]にf: A => Par[B]をマップングしてPar[Par[B]]を生成し,続いてこの入れ子をPar[B]にフラッティング=平坦化する。

ここで興味深いのは,更に単純なコンビネータを追加するだけでよいという事実が判明することである。
このコンビネータは,Xに何が選択されたとしても,Par[Par[X]]をPar[X]に変換すうる。これをjoinと呼ぶことにする。

Exercise 7.14
  • joinを実装せよ。joinを使ってflatMapを,またflatMapを使ってjoinを実装することは可能か。
  // Par[Par[A]]をPar[A]に変換する。                                    
  def join[A](a: Par[Par[A]]): Par[A] =
    es => run(es)(run(es)(a).get())

  def joinViaFlatMap[A](a: Par[Par[A]]): Par[A] =
    flatMap(a)(p => p)

  def faltMapViaJoin[A,B](pa: Par[A])(choices: A => Par[B]): Par[B] =
    join(map(pa)(choices))

まとめ

本章では,並列処理と非同期処理を純粋関数方式で定義するためのライブラリを設計した。
本章の主な目的は,関数型の設計プロセスへの扉を開き,遭遇するであろう問題を明らかにすることである。

4〜6章では関心の分離,実行するインタープリタから計算の記述を切り離すという概念を扱った。
本葬では,この原理をライブラリの設計に応用した。並列処理はデータ型Parの値として表現され,
それらを実行するスレッドを実際に生成していたのは別個のインタープリタrunである。

次章では全く別のドメインを取り上げ,そのドメインAPIに向かって関数型の設計に関する新たな教訓を学ぶ。