新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

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

第2章:Scala関数型プログラミングの準備

本章の内容

速習Scala言語

以下のScalaコードを読みながら学習していく。
詳細はコード中のコメントに記載。

/* MyModuleというオブジェクト(モジュール)を定義。                                           
 * Scalaのコードはobjectまたはclassに含まれている必要がある。                               
 * オブジェクトとクラスについては後述。                                                     
 */
object MyModule {
  /* absメソッド。引数の絶対値を返す。                                                      
   * 引数nと戻り値の型はInt。                                                               
   * メソッド内部が単一行なので、=のみで結ばれており、                                      
   * 右辺の評価値がそのまま戻り値となる。                                                   
   */
  def abs(n: Int): Int =
    if (n < 0) -n
    else n

  /*                                                                                        
   * formatAbsメソッド。引数の絶対値を含む文字列を返す。                                    
   * 戻り値の型を省略しているが、一般的には外部から使われる                                 
   * 可能性がある場合は戻り値の型を明示的に宣言した方が良い。                               
   * 今回はprivate=MyModuleの外からは呼び出せないので型を省略している。                     
   * またメソッド内部が複数行から成るため、=の右辺が{}で括られている。                      
   */
  private def formatAbs(x: Int) = {
    val msg = "The absolute value of %d is %d"
    msg.format(x, abs(x))
  }

  /*                                                                                        
   * いわゆるmain関数。                                                                     
   * 引数はString型の配列、戻り値はUnit型でなければならない。                               
   * UnitはCやJavaでいうvoidのような働きで、戻り値がUnitということは、                      
   * 意味のある値を返さない=副作用がある=純粋関数でないことを示す。                         
   * 以下のmain関数はコンソールにformatAbs関数の戻り値を出力する。                          
   */
  def main(args: Array[String]): Unit =
    println(formatAbs(-42))
}

上記コードの実行結果が以下。

% scalac MyModule.scala
% scala MyModule
The absolute value of -42 is 42

モジュール、オブジェクト、名前空間

Scalaでは、すべての値をオブジェクトと呼ぶ。
各オブジェクトにはメンバーを1つ以上定義できるが、1つも定義しなくても良い。
メンバーに名前空間を割り当てることを主な目的とするオブジェクトはモジュールとも呼ばれる。

オブジェクトのメンバーにアクセスするには、標準的なドット表記を使用してMyModule.abs(-42)のように表記する。
単一の引数で呼び出す場合はドットとカッコを省略した中置形式でMyModule abs -42と表記できる。
同様に、2 + 4は2.+(4)の糖衣構文である。(Scala演算子の概念はなく、+も有効なメソッド名である)

高階関数

Scalaの構文の基礎を学んだところで、関数型プログラミングを使ってプログラムを記述するための基礎に進む。
関数型では、整数や文字列といった他の型の値と同じように関数も値であり、変数に代入したり引数として渡すことが可能である。
純粋関数型のプログラムでは、他の関数を引数として受け取る関数を記述すると便利なことがよくある。
これは高階関数と呼ばれ、後の章で詳細を説明する。

関数型のループ

さきほどのMyModuleプログラムを書き換え、ある数の階乗を出力するように変更する。
まず、下記の関数factorialを記述する。

  def factorial(n: Int): Int = {
    def go(n: int, acc: Int): Int =
      if (n <= 0) acc
      else go(n-1, n*acc)

    go(n, 1)
  }

ループを関数型で記述する、つまりループ変数を使用しない場合は、再帰関数を使用する
factorial関数では、本体の中で再帰ヘルパー関数goを定義している。
(このようなヘルパー関数では、goまたはloopという名前を使用するのが慣例となっている。
また、Scalaでは別の関数の本体に対してローカルな関数を記述することがよくある。ローカル変数と同じように考えて良い。)

go関数の引数はループの状態、この場合は残余値nと現在の累積会場accである。
ループの次の繰り返しに進む際には、新しいループ状態(n-1, n*acc)を渡してgoを再帰的に呼び出し、
ループを抜ける場合は再帰呼び出しを行う代わりに値accを返す。

この種の自己再帰では、呼び出しが末尾再帰(呼び出し元が再帰呼び出しの値を返す以外は何もしない)である限り、
whileループに対して生成されるものと同じ種類のバイトコード再帰のたびにコールスタックフレームを消費しないコードとしてコンパイルされる。

高階関数の作成

さて、factorialをMyModuleプログラムに追加してみる。

  private def formatAbs(x: Int) = {
    val msg = "The absolute value of %d is %d"
    msg.format(x, abs(x))
  }

  private def formatFactorial(n: Int) = {
    val msg = "The factorial of %d is %d"
    msg.format(n, factorial(n))
  }

  def main(args: Array[String]): Unit = {
    println(formatAbs(-42))
    println(formatFactorial(7))
  }
% scala MyModule
The absolute value of -42 is 42
The factorial of 7 is 5040

factorial関数の結果を出力するためのformatFactorial関数を作成したが、formatAbsとformatFactorialはほぼ同じである。
ここで、これらを一般化したformatResultという関数を作り、適用する関数を引数として受け取ることができる。

  private def formatResult(name: String, n: Int, f: Int => Int) = {
    val	msg = "The %s of %d is %d"
    msg.format(name, n,	f(n))
  }

formatResultメソッド高階関数であり、引数としてfという別の関数を受け取っている。
高階関数のパラメータにはf, g, hのような名前を付けるのが慣例となっている。
 汎用的であるために引数の目的を名前で説明しようがなく、名前を短くすることでコードの構造がわかりやすくなるため。)
ただしfの型はInt => Intである必要があり、つまり整数の引数を期待して、戻り値として整数を返すことを意味する。
よって、abs・factorialどちらの関数もこのformatResultに渡すことができる。

scala> :load MyModule.scala
Loading MyModule.scala...
defined object MyModule

scala> import MyModule.formatResult
import MyModule.formatResult

scala> formatResult("abs", -42, abs)
res38: String = The abs of -42 is 42

scala> formatResult("factorial", 7, factorial)
res39: String = The factorial of 7 is 5040
練習問題

n番目のフィボナッチ数を取得する再帰関数を記述せよ。

というわけで書いてみた。

  def fib(n: Int): Int = {
    @annotation.tailrec
    def go(n: Int, acc: Int): Int =
      if (n <= 1) 0
      else if (n == 2) 1
      else go(n-1, 0)+go(n-2, 0)

    go(n, 0)

  }

出力結果としては正しかったが、末尾再帰ではなくなってしまった。
(末尾呼び出しの除去が成功したかどうかは、tailrecアノテーションをつけることでわかる。
末尾呼び出しの除去ができない場合、コンパイル時にエラーが出る)

というわけで正解は以下。

  def fib(n: Int): Int = {
    @annotation.tailrec
    def loop(n: Int, prev: Int, cur: Int): Int =
      if (n == 0) prev
      else loop(n-1, cur, prev+cur)

    loop(n, 0, 1)
  }

ループの状態に現在の値と一つ前の値を持たせることで問題を解決している。
なお、nが1までループを回して現在の値curを返しても良いように思われるが、
それだとfib(0)を呼び出したときに正しい値が返らないのでダメ。

多相関数:型の抽象化

これまでの関数は単相関数=1つの型のデータのみ操作する関数ばかりだった。
しかし、どのような型が渡されても動作する関数=多相関数を記述したいことがしばしばある。

多相関数の例

以下のfindFirst関数は、配列において指定されたキーが最初に含まれているインデックスを返す。

  def findFirst(ss: Array[String], key: String): Int = {
    @annotation.tailrec
    def	loop(n: Int): Int =
      if (n >= ss.length) -1   // nが配列長を超える=検索対象が存在しない場合は-1を返す
      else if (ss(n) ==	key) n // 配列ssのn番目の要素がキーと等しい場合はnを返す    
      else loop(n+1)  	       // それ以外の場合は次の要素を探す                  

    loop(0)
  }

上記の例では、配列・キーともにString(の配列)に限定されている。
しかし、Int型の配列から等しいIntの値を探す場合でも、A型の配列からAを検索する場合でもほとんど同じコードが書けるはずである。
特定のA値を評価するための関数を受け取るようにすることで、findFirstをより汎用的に記述できる。

  def findFirst2[A](as: Array[A], p: A => Boolean): Int = {
    @annotation.tailrec
    def loop(n: Int): Int =
      if (n >= as.length) -1 // nが配列長を超える=検索対象が存在しない場合は-1を返す        
      else if (p(as(n))) n   // 配列の要素を評価する関数pの値がtrueならnを返す      
      else loop(n+1)         // それ以外の場合は次の要素を探す                            

    loop(0)
  }

Stringの代わりにパラメータとして型A(一般的には大文字1つの短い名前を付ける)を受け取るようにする。
また、指定されたキーの等価チェックをハードコーディングする代わりに、評価する関数を受け取るようにしている。
以下のように呼び出すことで、どのような型にも対応可能である。

scala> var arr = Array("Hoge", "Fuga", "Var")
arr: Array[String] = Array(Hoge, Fuga, Var)

scala> findFirst2[String](arr, "Var".equals)
res46: Int = 2

scala> var arr = Array(100, 200, 300)
arr: Array[Int] = Array(100, 200, 300)

scala> findFirst2[Int](arr, 200.equals)
res47: Int = 1
練習問題

指定された比較関数に従ってArray[A]がソートされているか調べるisSortedを実装せよ。
ということで書いてみた。

  def isSorted[A](as: Array[A], ordered: (A,A) => Boolean): Boolean = {
    @annotation.tailrec
    def	loop(n:	Int): Boolean =
      if (n+1 >= as.length) true  // 配列長を超えたらソートされている=trueを返す
      else if (ordered(as(n), as(n+1)))	loop(n+1) // 隣り合う2つがソートされていたら次へ    
      else false // そうでなければソートされていない=falseを返す                

    loop(0)
  }

  def gt(n1: Int, n2: Int): Boolean =
    if (n1 <= n2) true
    else false

ついでに比較関数として、整数が昇順であることを比較する関数gtを作った。
isSortedを使ってみた様子は以下のとおり。

scala> var arr = Array(1, 2, 5, 7, 9)
arr: Array[Int] = Array(1, 2, 5, 7, 9)

scala> isSorted[Int](arr, gt)
res65: Boolean = true

scala> var arr = Array(1, 5, 2, 0, 4)
arr: Array[Int] = Array(1, 5, 2, 0, 4)

scala> isSorted[Int](arr, gt)
res66: Boolean = false
無名関数を使った高階関数の呼び出し

高階関数を使用する際には、既存の名前付きの関数を指定するのではなく、それらを無名関数または関数リテラルとして呼び出せると便利なことがよくある。
たとえば、findFirst関数を以下のようにテストできる。

scala> findFirst2(Array(7, 9, 13), (x: Int) => x == 9)
res68: Int = 1

(x: Int) => x == 9という構文は関数リテラル=無名関数と呼ばれる。
この関数を名前付きメソッドとして定義する代わりに、この構文を使ってインラインで定義することができる。
この関数は、Int型のxという引数を1つ受け取り、xが9に等しいかどうかを示すBoolean値を返す。

一つ前の練習問題で、比較用の関数gtを使ったが、これも無名関数で以下のように置換できる。

scala> isSorted[Int](Array(1, 3, 5), (n1: Int, n2: Int) => n1 <= n2)
res69: Boolean = true

型に従う実装

多相関数を実装する場合、可能な実装の範囲が大幅に制限される。
例えば以下のpartial1関数、

def partial1[A,B,C](a: A, f: (A,B) => C): B => C

は引数として値と引数2つの関数を受け取り、引数1つの関数を返す関数である。
さて、この高階関数の実装は、型シグネチャに従って1つの実装に絞られる。

まず、戻り値はB => Cなので、この型を返す実装である必要がある。
ということで、B型の引数を受け取る関数リテラルを記述する。

def partial1[A,B,C](a: A, f: (A,B) => C): B => C = 
  (b: B) => ???

現時点では、「B型の値bを受け取る関数を返す」ということしか示しておらず、
この無名関数の実装は???となっている。
では、この無名関数が返す値は何かと言われると、型シグネチャ(B => C)からC型の値である必要がある。
Cは関数fの戻り値の型なので、Cを取得するにはfにAとBを渡すしかない。
よって、

def partial1[A,B,C](a: A, f: (A,B) => C): B => C = 
  (b: B) => f(a, b)

上記が正解となる。
ただし、ここでbの型は型シグネチャから推測できるので、型アノテーション: Bは不要である。
よって、実装としては b => f(a, b)でOK。

練習問題:カリー化

カリー化(currying)では、引数2つの関数fが、fを部分的に適用する引数1つの関数に変換される。

def curry[A,B,C](f: (A, B) => C): A => (B => C)

この実装を記述せよ。

まずは戻り値の型から考えていく。
戻り値の型はA => (B => C)なので、A型を引数とし、(B => C)の関数を返す関数である。
というわけで、まずはA型の引数を受け取る関数リテラルを記述する。

def curry[A,B,C](f: (A, B) => C): A => (B => C) =
  (a: A) => ???

???部分には(B => C)の関数、つまりB型を引数にC型の戻り値を返す関数が入る。
ここで、Cは関数fの戻り値として得られるので、以下のように書ける。

def curry[A,B,C](f: (A, B) => C): A => (B => C) =
  (a: A) => (b: B) => f(a, b)

で、少し前に書いた通り、aとbの型は型シグネチャ(A => (B => C))から推測できるので、省略可能。

def curry[A,B,C](f: (A, B) => C): A => (B => C) =
  a => b => f(a, b)

これで完成。
また、=>は右結合なので、A => (B => C)はカッコを外してA => B => Cと書いてもOK。

練習問題:アンカリー

カリーによる変換を逆向きに行うuncurryを実装せよ。

def uncurry[A,B,C](f: A => B => C): (A, B) => C

さきほどと同様に、戻り値の型から、まずは(A, B)を引数とする関数リテラルを記述。

def uncurry[A,B,C](f: A => B => C): (A, B) => C = 
  (a, b) => ???

???部分にはC型が入る。
ここで、Cは関数f(a)の戻り値(B => C)にbを引数として入れた戻り値なので、以下のように書ける。

def uncurry[A,B,C](f: A => B => C): (A, B) => C = 
  (a, b) => f(a)(b)
練習問題:compose

2つの関数を合成する高階関数を実装せよ。

def compose[A,B,C](f: B => C, g: A => B): A => C

同様に戻り値の型から導出する。
まずはAを引数とする関数リテラルを記述。

def compose[A,B,C](f: B => C, g: A => B): A => C = 
  a => ???

???部分にはC型が入る。
ここで、Cは関数fにB型を引数とした際の戻り値である。
また、Bは関数gにA型を引数とした際の戻り値であるので、これらを組み合わせて以下のように書ける。

def compose[A,B,C](f: B => C, g: A => B): A => C = 
  a => f(g(a))

なお、このcomposeはScalaの標準ライブラリでFunction1(引数1つの関数のインタフェース)のメソッドとして定義されている。

まとめ

Scala言語の基礎と関数型プログラミングの初歩的な概念を紹介した。
ループの表現に始まり、高階関数、多相関数を記述する方法について説明した。
多くの場合は「型に従う」ことで正しい実装を導出できるようにするため、多相関数の実装はしばしば大幅に制限される。

所感

ループで再帰を使ったり、関数を引数にして戻り値が関数だったりというのはまだまだ慣れない。
引数や戻り値の(f: B => C, g: A => B): A => Cみたいな記述は読めるようになってきた。パズルみたいで面白い。
しかし、これらを使うことによって何が嬉しいのかもまだよくわからない感じ。