M.Hiroi's Home Page

お気楽 Scala プログラミング入門

高階関数


Copyright (C) 2014-2024 Makoto Hiroi
All rights reserved.

はじめに

関数型言語は関数を他のデータと同等に取り扱うことができます。つまり、関数を変数に代入したり、引数として渡すことができるのです。また、値として関数を返すこともできるので、関数を作る関数を定義することもできます。関数を引数にとる関数のことを「汎関数 (functional)」とか「高階関数 (higher order function)」と呼びます。Scala は高階関数を簡単に定義することができます。もちろん、値として関数を返すこともできるので、関数を作る関数を定義することも簡単です。

●関数を引数にとる関数

簡単な例として、整数 n から m までの和を求める関数 sumOfInt を作ってみましょう。今回は末尾再帰でプログラムします。次の例を見てください。 

scala> def sumOfInt(n: Int, m: Int, a: BigInt = 0): BigInt =
     | if (n > m) a else sumOfInt(n + 1, m, a + n)
def sumOfInt(n: Int, m: Int, a: BigInt): BigInt

scala> sumOfInt(1, 100)
val res0: BigInt = 5050

scala> sumOfInt(1, 10000)
val res1: BigInt = 50005000

プログラムは簡単なので説明は不要でしょう。それでは、整数の 2 乗の和と 3 乗の和を求めるプログラムはどうなるでしょうか。次の例を見てください。 

scala> def square(x: BigInt): BigInt = x * x
def square(x: BigInt): BigInt

scala> def cube(x: BigInt): BigInt = x * x * x
def cube(x: BigInt): BigInt

scala> def sumOfSquare(n: Int, m: Int, a: BigInt = 0): BigInt =
     | if (n > m) a else sumOfSquare(n + 1, m, a + square(n))
def sumOfSquare(n: Int, m: Int, a: BigInt): BigInt

scala> def sumOfCube(n: Int, m: Int, a: BigInt = 0): BigInt =
     |  if (n > m) a else sumOfCube(n + 1, m, a + cube(n))
def sumOfCube(n: Int, m: Int, a: BigInt): BigInt

scala> sumOfSquare(1, 10000)
val res2: BigInt = 333383335000

scala> sumOfCube(1, 10000)
val res3: BigInt = 2500500025000000

累積変数 a に値を加算する処理で、square を呼び出すと 2 乗の和を、cube を呼び出すと 3 乗の和を求めることができます。関数 sumOfSquare と sumOfCube の違いはこれだけです。ここで、square や cube を引数として渡すことができれば、sumOfSquare や sumOfCube を一つの関数で済ますことができます。次の例を見てください。 

scala> def sumOf(f: BigInt => BigInt, n: Int, m: Int, a: BigInt = 0): BigInt =
     | if (n > m) a else sumOf(f, n + 1, m, a + f(n))
def sumOf(f: BigInt => BigInt, n: Int, m: Int, a: BigInt): BigInt

scala> sumOf(square, 1, 10000)
val res4: BigInt = 333383335000

scala> sumOf(cube, 1, 10000)
val res5: BigInt = 2500500025000000

関数 sumOf の第 1 引数 f に関数を渡します。Scala の場合、関数の型は次の形式で表します。 

(引数の型1, 引数の型2, ...) => 返り値の型

カッコの中に引数の型を書き、=> の後ろに返り値の型を書きます。引数が一つしかない場合はカッコを省略することができます。引数がない場合は () => 返り値の型 となります。

引数 f の型は BigInt => BigInt なので、BigInt を一つ受け取って BigInt を返す関数であることがわかります。渡された関数は、今までと同じ方法で呼び出すことができます。square や cube のかわりに a + f(n) とすることで、関数 f に n を渡して呼び出し、その結果を a に加算することができます。引数に関数を渡す場合も簡単で、引数に関数名を書くだけです。

●多相性

ところで、sumOfInt も sumOf を使って実現することができます。引数 f には自分自身を返す関数を渡せばよいのです。これを「恒等関数 (identity function)」といいます。次の例を見てください。 

scala> def identity[A](x: A): A = x
def identity[A](x: A): A

scala> identity(10)
val res0: Int = 10

scala> identity(10.0)
val res1: Double = 10.0

scala> identity("foo")
val res2: String = foo

関数 identity は引数をそのまま返す関数です。ここで、引数 x の型が A で、返り値の型が A になっていることに注目してください。これを「型パラメータ」[*3] といって、A は任意の型を表します。型パラメータは関数名と引数の間の角カッコの中で指定します。Scala では、型パラメータを A, B, C, D ... のように英大文字で表すのが習慣のようです。

identity の型は A => A なので、任意の型のデータを受け取り、同じ型を返す関数であることがわかります。つまり、Int, Double, String など Scala のデータ型であれば何でも対応することができるのです。このような関数を「多相型関数 (polymorphic function)」といいます。

多相型関数のように、いろいろな型を取ることができる性質のことを「多相性 (polymmprphism)」といいます。多相性は Scala だけではなく、ML 系の言語 (OCaml, SML/NJ) や Haskell の特徴のひとつです。なお、Scala には恒等関数 identity が定義されているので、私たちが実際に定義する必要はありません。

sumOfInt は sumOf と identity を使って次のように実現できます。 

scala> sumOf(identity, 1, 100)
val res3: BigInt = 5050

scala> sumOf(identity, 1, 10000)
val res4: BigInt = 50005000

Scala は型チェックを厳密に行うプログラミング言語ですが、型推論と多相性により柔軟なプログラミングが可能になっています。

-- note --------
[*3] ML 系の言語では「型変数」といいます。

●データの探索

それでは多相性の簡単な例題として、データの探索処理を作ってみましょう。データの探索とは、データの集まりの中から特定のデータを見つける処理のことです。データの探索はプログラムの中で最も基本的な操作の一つです。たとえば配列からデータを探す場合、いちばん簡単な方法は先頭から順番にデータを比較していくことです。これを「線形探索 (linear searching)」といます。次のリストを見てください。 

リスト : データの探索 (sample0302.scala)

object sample0302 {

  def find[A](n: A, buff: Array[A], i: Int = 0): Boolean = {
    if (i == buff.size)
      false
    else if(buff(i) == n)
      true
    else
      find(n, buff, i + 1)
  }

  def position[A](n: A, buff: Array[A], i: Int = 0): Int = {
    if (i == buff.size)
      -1
    else if (buff(i) == n)
      i
    else
      position(n, buff, i + 1)
  }

  def count[A](n: A, buff: Array[A]): Int = {
    var c = 0
    for (x <- buff) {
      if (x == n) c += 1
    }
    c
  }
}

どの関数も多相型関数として定義しています。探索するデータ n と配列 buff の要素の型が同じ A であることに注意してください。関数 find は buff の中から引数 n と等しいデータを探します。再帰定義で配列の要素を一つずつ順番に取り出して n と比較します。等しい場合は true を返します。i が buff の終端に達したならば、n と等しい要素が見つからなかったので false を返します。それ以外は find を再帰呼び出しします。

関数 position は、データを見つけた場合はその位置 i を返し、見つからない場合は -1 を返します。position は最初に見つけた要素の位置を返しますが、同じ要素が配列に複数あるかもしれません。関数 count は等しい要素の個数を数えて返します。局所変数 c を 0 に初期化し、n と等しい要素 x を見つけたら c の値を +1 します。最後に c の値を返します。

簡単な実行例を示します。 

scala> :load sample0302.scala
// defined object sample0302

scala> import sample0302._

scala> val a = Array(1,2,3,4,5,6,7,8)
val a: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7, 8)

scala> val b = Array("foo", "bar", "baz", "oops!")
val b: Array[String] = Array(foo, bar, baz, oops!)

scala> find(1, a)
val res5: Boolean = true

scala> find("baz", b)
val res6: Boolean = true

scala> find("hello", b)
val res7: Boolean = false

scala> position(8, a)
val res8: Int = 7

scala> position("oops", b)
val res9: Int = -1

scala> position("oops!", b)
val res10: Int = 3

scala> position(0, a)
val res11: Int = -1

scala> val c = Array(1,2,3,4,2,3,4,3,4,4)
val c: Array[Int] = Array(1, 2, 3, 4, 2, 3, 4, 3, 4, 4)

scala> count(1, c)
val res12: Int = 1

scala> count(4, c)
val res13: Int = 4

scala> count(5, c)
val res14: Int = 0

このように、線形探索は簡単にプログラムできますが、大きな欠点があります。データ数が多くなると処理に時間がかかるのです。近年、パソコンの性能は著しく向上しているので、線形探索でどうにかなる場合もありますが、データ数が多くて時間がかかるのであれば、高速な探索アルゴリズムを使ったほうがよいでしょう。

ところで、データの探索は基本的な処理なので、Scala のライブラリにもいろいろなメソッドが用意されています。データの有無はメソッド contains でチェックできます。 

scala> a
val res15: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7, 8)

scala> a.contains(1)
val res16: Boolean = true

scala> a.contains(8)
val res17: Boolean = true

scala> a.contains(0)
val res18: Boolean = false

scala> a.contains(10)
val res19: Boolean = false

scala> a contains 2
val res20: Boolean = true

Scala の場合、引数が一つしかないメソッドは二項演算子のように使うことができます。たとえば、a.contains(2) は a contains 2 としてもかまいません。

見つけた要素の位置を求めたい場合はメソッド indexOf を使います。 

scala> a.indexOf(1)
val res21: Int = 0

scala> a indexOf 8
val res22: Int = 7

scala> a indexOf 10
val res23: Int = -1

メソッド count は高階関数で、引数の関数が真を返す要素の個数を返します。 

scala> def isEven(x: Int): Boolean = x % 2 == 0
def isEven(x: Int): Boolean

scala> a.count(isEven)
val res24: Int = 4

●無名関数

高階関数を使うようになると、数を 2 乗する square のような小さな関数をいちいち定義するのが面倒になります。とくに、その高階関数でしか使わないのであれば、なおさらそう思うでしょう。Scala には Lisp のラムダ式 (lambda) のような「無名関数 (Anonymous Functions)」という名前のない関数が用意されています。

Scala の場合、無名関数は次のように定義します。 

(引数1:型1, 引数2:型2, ...) => 式

関数の型とよく似ていますが、返り値の型を指定することはできません。Scala の型推論に任せるか、あらかじめ関数の型を宣言しておく必要があります。無名関数は関数型のデータ (関数値) を生成して返します。なお、Scala の関数値は多相性がありません。つまり、無名関数は多相型関数として定義することはできないのです。ご注意くださいませ。

Scala は無名関数をそのまま実行することができます。また、関数の引数に無名関数を渡すこともできます。次の例を見てください。 

scala> (x: Int) => x * x
val res0: Int => Int = $Lambda$1053/0x00000008405df840@348ad293

scala> ((x: Int) => x * x)(10)
val res1: Int = 100

scala> def sumOf(f: BigInt => BigInt, n: Int, m: Int, a: BigInt = 0): BigInt =
     | if (n > m) a else sumOf(f, n + 1, m, a + f(n))
def sumOf(f: BigInt => BigInt, n: Int, m: Int, a: BigInt): BigInt

scala> sumOf(x => x, 1, 1000)
val res2: BigInt = 500500

scala> sumOf(x => x * x, 1, 1000)
val res3: BigInt = 333833500

scala> sumOf(x => x * x * x, 1, 1000)
val res4: BigInt = 250500250000

sumOf の引数 f には関数の型が指定されているので、sumOf に渡す無名関数に型を指定する必要はありません。

●カリー化

ところで、関数型言語は関数をデータ型の一つとして扱うことができるので、関数の返り値として関数を返すことができます。この「関数を返す関数」を使うと、関数の引数が一つでも複数の引数を処理することができます。このような関数を「カリー化関数 (curried function)」といいます。

たとえば、(x: Int, y: Int) => x + y の場合、引数 x を受け取ると「引数 y を受け取って x + y を計算する関数」を返し、その関数に引数 y を渡せば x + y を計算することができます。Scala では、次のように定義することができます。 

scala> (x: Int) => (y: Int) => x + y
val res5: Int => Int => Int = $Lambda$1126/0x0000000840621840@151659dd

関数の型が少し複雑になりました。これは引数 Int を受け取り、Int => Int という型の関数を返すことを表しています。これで引数を一つだけ与えれば、関数を返すことになります。もちろん、引数を 2 つ与えれば、それらを加算した結果を返します。つまり、最初の引数を受け取って関数を生成し、その関数に 2 番目の引数を渡して呼び出す、という動作になります。

それでは実際に試してみましょう。 

scala>  ((x: Int) => (y: Int) => x + y)(1)
val res6: Int => Int = $Lambda$1128/0x0000000840623040@1013871e

scala> ((x: Int) => (y: Int) => x + y)(1)(2)
val res7: Int = 3

引数を一つだけ渡すと「引数 y を受け取って x + y を計算する関数」を返します。引数を 2 つ渡すと、それを足し算した値を返します。カリー化関数の場合、引数はカッコに入れて渡してください。

Scala の場合、メソッド curried を使うと通常の関数をカリー化することができます。次の例を見てください。 

scala> def add(x: Int, y: Int):Int = x + y
def add(x: Int, y: Int): Int

scala> add _
val res8: (Int, Int) => Int = $Lambda$1134/0x0000000840627040@25e24908

scala> (add _).curried
val res9: Int => Int => Int = scala.Function2$$Lambda$1136/0x0000000840628840@3891b430

scala> val addCurry = (add _).curried
val addCurry: Int => Int => Int = scala.Function2$$Lambda$1136/0x0000000840628840@7890324e

scala> addCurry(10)
val res10: Int => Int = scala.Function2$$Lambda$1138/0x000000084062f040@a1c4f69

scala> addCurry(10)(20)
val res11: Int = 30

関数名にアンダーバー ( _ ) を付けて呼び出すと、その関数値を取り出す [*4] ことができます。関数値にメソッド curried を適用すると、カリー化関数に変換することができます。変数 addCurry にカリー化関数をセットします。addCurry(10) とすると、Int => Int の関数を返し、addCurry(10)(20) とすると、足し算した値 30 を返します。

たとえば、関数 sumOf をカリー化すると次のようになります。 

scala> val sumOfCurry = (sumOf _).curried
val sumOfCurry: (BigInt => BigInt) => Int => Int => BigInt => BigInt = 
scala.Function4$$Lambda$1141/0x000000084062e840@dc6a186

そして、この sumOfCurry を使うと、sumOfInt, sumOfSquare, sumOfCube を簡単に定義することができます。 

scala> val sumOfInt = sumOfCurry (x => x)
val sumOfInt: Int => Int => BigInt => BigInt = scala.Function4$$Lambda$1143/0x000000084062d040@19e5e846

scala>  val sumOfSquare = sumOfCurry (x => x * x)
val sumOfSquare: Int => Int => BigInt => BigInt = scala.Function4$$Lambda$1143/0x000000084062d040@e7423bb

scala> val sumOfCube = sumOfCurry (x => x * x * x)
val sumOfCube: Int => Int => BigInt => BigInt = scala.Function4$$Lambda$1143/0x000000084062d040@43e55cfb

scala> sumOfInt(1)(100)(0)
val res12: BigInt = 5050

scala> sumOfSquare(1)(100)(0)
val res13: BigInt = 338350

scala> sumOfCube(1)(100)(0)
val res14: BigInt = 25502500

このように、カリー化された関数の一部の引数に値を与えて、残りの引数を受け取る関数を生成することを「部分適用 (partial application)」といいます。カリー化関数は部分適用が簡単にできるのでとても便利です。

ただし、この場合はデフォルト引数 a が機能しないので、次のように引数の順番を変えたほうが使いやすくなるでしょう。 

scala> def sumOf(f: BigInt => BigInt, a: BigInt, n: Int, m: Int): BigInt =
     | if (n > m) a else sumOf(f, a + f(n), n + 1, m)
def sumOf(f: BigInt => BigInt, a: BigInt, n: Int, m: Int): BigInt

scala> val sumOfInt = (sumOf _).curried(x => x)(0)
val sumOfInt: Int => Int => BigInt = scala.Function4$$Lambda$1099/0x0000000840610040@45b32dfe

scala> sumOfInt(1)(1000)
val res0: BigInt = 500500
-- note --------
[*4] 多相型関数の場合、アンダーバー ( _ ) で関数値を取り出すと、その関数値は多相型関数ではなくなります。次の例を見てください。 
scala> def identity[A](x: A): A = x
def identity[A](x: A): A

scala> val f = identity _
val f: Any => Any = Lambda/0x00007fc0405a2f48@200e6029

scala> f(10)
val res22: Any = 10

scala> f(1.2345)
val res23: Any = 1.2345

多相型関数を関数値に変換するとき、Scala は型推論により型パラメータを適切な型に変換します。この場合、Any という特別な型 (全ての型のスーパータイプ) に変換されるため、Scala のデータであればどんな型でも引数に渡すことができます。

●部分適用

Scala の場合、カリー化関数でなくても部分適用を行うことできます。次の例を見てください。 

scala> def add(x: Int, y: Int): Int = x + y
def add(x: Int, y: Int): Int

scala> val add10 = add(10, _: Int)
val add10: Int => Int = $Lambda$1145/0x0000000840105040@3ff26c9

scala> add10(100)
val res2: Int = 110

scala> val add20 = add(_ : Int, 20)
val add20: Int => Int = $Lambda$1147/0x0000000840106040@3c20e9d6

scala> add20(200)
val res3: Int = 220

関数の引数で、実引数以外に _:型 を渡すと、実引数を部分適用した関数を生成することができます。val add10 = add(10, _: Int) であれば、第 1 引数を 10 に指定して部分適用するので、add10 は引数に 10 を加算する関数として動作します。val add20 = add(_: Int, 20) であれば、第 2 引数に 20 を指定して部分適用するので、add20 は引数に 20 を加算する関数として動作します。

部分適用を行う場合、関数の引数をカッコで分けて定義すると便利です。次の例を見てください。 

scala> def sub(x: Int)(y: Int): Int = x - y
def sub(x: Int)(y: Int): Int

scala> val f = sub(10)_
val f: Int => Int = $Lambda$1150/0x0000000840633840@35e7fcf2

scala> f(20)
val res4: Int = -10

scala> val g = sub(_: Int)(20)
val g: Int => Int = $Lambda$1151/0x0000000840637840@3dedc8b8

scala> g(100)
val res5: Int = 80

引数を分けて書くと、第 1 引数の値を指定するときは、sub(10)_ だけで部分適用を行うことができます。ただし、第 2 引数の値を指定するときは、第 1 引数の型を指定しないといけません。

sumOf を部分適用して sumOfInt, sumOfSquare, sumOfCube を定義することができます。 

scala> def sumOf(f: BigInt => BigInt)(a: BigInt)(n : Int, m: Int): BigInt =
     | if (n > m) a else sumOf(f)(a + f(n))(n + 1, m)
def sumOf(f: BigInt => BigInt)(a: BigInt)(n: Int, m: Int): BigInt

scala> val sumOfInt = sumOf(x => x)(0)_
val sumOfInt: (Int, Int) => BigInt = $Lambda$1098/0x0000000840604040@4214ae8f

scala> sumOfInt(1, 1000)
val res0: BigInt = 500500

scala> val sumOfSquare = sumOf(x => x * x)(0)_
val sumOfSquare: (Int, Int) => BigInt = $Lambda$1108/0x0000000840615840@10e9a5fe

scala> sumOfSquare(1, 1000)
val res1: BigInt = 333833500

scala> val sumOfCube = sumOf(x => x * x * x)(0)_
val sumOfCube: (Int, Int) => BigInt = $Lambda$1110/0x0000000840617840@69a90b81

scala> sumOfCube(1, 1000)
val res2: BigInt = 250500250000

このように、sumOf の引数を分けて定義することで、部分適用を簡単に行うことができます。

●関数の合成

最後に、関数 f(x) と g(x) を合成して新しい関数 h(x) を作ることを考えてみましょう。関数 h(x) を次のように定義します。 

1. h(x) = g( f(x) )
2. h(x) = f( g(x) )

たとえば、f(x) = 2 * x + 1, g(y) = y * y + 3 * y とすると、1 の h(x) は次のようになります。 

h(x) = g( f(x) )
     = (2 * x + 1) * (2 * x + 1) + 3 * (2 * x + 1)
     = 4 * x * x + 4 * x + 1 + 6 * x + 3
     = 4 * x * x + 10 * x + 4

実際のプログラムは数式を展開するのではなく、f(x) の評価結果を g(x) に渡すだけなので簡単です。Scala には関数合成を行うメソッド andThen と compose が用意されています。 

f.andThen(g) => g(f(x))
f.compose(g) => f(g(x))

andThen と compose は関数値に対して動作することに注意してください。def で定義した関数は、(関数名 _) で関数値に変換する必要があります。

簡単な例を示しましょう。 

scala> def foo(x:Int):Int = 2 * x + 1
def foo(x: Int): Int

scala> def bar(y:Int):Int = y * y + 3 * y
def bar(y: Int): Int

scala> bar(foo(4))
val res3: Int = 108

scala> val baz = (foo _).andThen(bar _)
val baz: Int => Int = scala.Function1$$Lambda$1120/0x0000000840105840@24536f07

scala> baz(4)
val res4: Int = 108

scala> val baz1 = (bar _).compose(foo _)
val baz1: Int => Int = scala.Function1$$Lambda$1123/0x000000084061c040@48619f15

scala> baz1(4)
val res5: Int = 108

関数 foo と bar を定義します。foo と bar の合成は bar( foo( x ) ) と表すことができます。実際に 4 を計算すると 108 になります。この関数は andHten と compose で合成することができます。(foo _).andThen(bar _) の返り値を変数 baz に束縛すると、baz を合成関数として使うことができます。

今回はここまでです。次回は「リスト」と「パターンマッチング」について説明します。

初版 2014 年 7 月 26 日
改訂 2024 年 12 月 17 日