1. 再帰(Recursion)
1. 再帰呼出し
2. 木構造のデータ型 + matchによるパターンマッチで再帰を使う例
3. 末尾最適化(Tail call optimization)
2. 無名関数(ラムダ抽象)
3. レキシカルスコープ(Lexical scope, 静的スコープ)
4. クロージャ(Closure)
1. クロージャの使い方いろいろ
2. クロージャでif関数っぽいものを作る
3. クロージャで作るリスト
5. 高階関数(High-order function)
6. 関数合成
7. 部分関数(Partial function)
8. まとめ

Scalaについて勉強した時のメモ(その1)です。関数の扱い方について。

※ 元々はmarkdownで書いていたテキストの転載。

再帰(Recursion)

• 再帰とは自分自身を自分自身の中に持つような構造。
  • 再帰 - Wikipedia
  • 関数型プログラミングでは、再帰的なデータ型と(関数の)再帰呼出しがよく使われる。

再帰呼出し

• 呼び出し元の関数が自分自身を呼び出すこと。
• Scalaでの再帰呼出し。次のような階乗を行う関数の場合。

def fact1(n: Int): Int = if (n < 1){
  1
} else {
  n * fact1(n - 1)
}

• Scalaでのループはコレクション関数を使用が(多分)殆どなので、再帰呼出しはあまり使わないが、稀に使う。
• 再帰呼出しは(一般に)関数型プログラミングとの相性が良い。
  • 変数に再代入しないため、変数を常にimmutableにしたままループが書ける。
  • 再帰的なデータ型に対して、関数の再帰呼出しは相性が良い。(再帰的なデータ型を定義し、再帰呼出しで再帰的にトラバースできる)
  • プログラムを帰納的(余帰納的)に定義できる。
• 木構造のような再帰的なデータ型や、分割統治法を使ったアルゴリズムの場合は、再帰を使うとわかりやすいコードが書ける。
  • 分割統治法
    • 大きな問題を小さな部分問題に分割し、個々の小さな部分問題を解決しながら、 その部分問題の解答結果のマージを繰り返し、最終的に元の問題を解くようなアルゴリズム。
    • 分割統治法 - Wikipedia
    • 次のクイックソートが典型例。
  • クイックソート(あるいは、関数型プログラミングにおける偽のクイックソート)
    • Javaでクイックソート: 【Java】クイックソートのアルゴリズムのテスト - Qiita
    • Scalaで関数型プログラミングのスタイルのクイックソート

def quicksort[A](ls: Seq[A])(implicit ord: Ordering[A]): Seq[A] = ls match {
    case Nil => Nil
    case a::as => (quicksort(as.filter(ord.lt(_, a)))
                   ++ Seq(a) ++ quicksort(as.filter(ord.gteq(_, a))))
}

これは普通の関数同様に実行する。

scala> quicksort(List(5, 6, 7, 4, 3, 10, 2, 8, 0, 3))
res38: Seq[Int] = List(0, 2, 3, 3, 4, 5, 6, 7, 8, 10)

• 上記は偽のクイックソート(理由はググッて下さい)。

木構造のデータ型 + matchによるパターンマッチで再帰を使う例

木構造で、木の末尾をLeaf、枝をNodeとしてcase classで定義する。

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A]

木に対する走査の処理。 具体的にどのように走査した結果を得るかは、抽象化する。f: (A, A) => Aの箇所。

def sum[A](t: Tree[A], f: (A, A) => A): A = t match {
  case Leaf(a) => a
  case Node(l, r) => f(sum(l, f), sum(r, f))
}

以下のように使用する。

scala> val d = Node(Node(Leaf(10), Leaf(20)), Leaf(1))
d: Node[Int] = Node(Node(Leaf(10),Leaf(20)),Leaf(1))

scala> sum(d, (a:Int, b:Int) => a + b)
res36: Int = 31

以下は、String型で文字列を返す例。

scala> val e = Node(Node(Leaf("a"), Leaf("b")), Leaf("c"))
e: Node[String] = Node(Node(Leaf(a),Leaf(b)),Leaf(c))

scala> sum(e, (a: String, b: String) => "(" ++ a ++ " " ++ b ++ ")")
res44: String = ((a b) c)

末尾最適化(Tail call optimization)

• 関数型言語で行われるコンパイラの処理の一種。
• 末尾再帰形式は関数呼び出し時に、stackを必要としないような再帰呼出しの形式。
  • 自分自身を再帰的に呼び出す際にその呼び出し以外の処理が残っていない形で自分自身を呼び出すような関数呼び出し形。
• 再帰呼出しは、コンパイル時に「末尾再帰」形式になっている場合、コンパイル時に(whileのような)スタックを消費しないループに変換される。
  • ループに変換されない場合、通常の関数呼び出しの連鎖となり、stackを消費してしまい、StackOVerFlowErrorになってしまう。
  • ループ回数が多い場合(JVMの場合、1000〜数千回以上)の場合は、末尾再帰形式でループを記述しないと、StackOverFlowになる。
    • 個人的な経験則だと1000回未満のループだと、SOFにはならない事が多い。(勿論、実装による部分が大きい)
  • 大量にループを繰り返す場合は末尾再帰が必須となる。
  • stackを消費しすぎないタイプのループの場合は、この限りではない。(関数呼び出しで消費したStackが戻される場合など。)
• Scalaの再帰は末尾最適化をする場合としない(できない)場合。
  • 末尾再帰形式になっていない場合は、末尾最適化が行われない。

次のような階乗を行う関数の場合。(10の階乗(fact(10))は、10! = 1 2 3 4 5 6 7 8 9 * 10)

def fact1(n: Int): Int = if (n < 1){
  1
} else {
  n * fact1(n - 1)
}

次の例は、自分自身を呼び出しのみ、かつ末尾再帰形式になっている場合。

def fact2(n: Int, a: Int): Int = if (n < 1){
  a
} else {
  fact2(n - 1, n * a)
}

計算結果を保持する変数(アキュームレータ)を一つ追加している。 末尾再帰に書き直す場合は、計算結果を保持する引数を用意し、そこに副作用の役割を担わせることも多い。 これは「変化するmutableな変数」を表している。(引数で副作用(再代入)を引き回すスタイル)

以下のコードではfact2(10, 1)の計算しか行っていないが、例えば、fact1(10000)とfact2(10000, 1)では、 fact1の場合、StackOverFlowになってしまうが、fact2ではコンパイラの最適化(末尾再帰最適化)によりStackOverFlowにならない。

scala> fact2(10, 1)
res39: Int = 3628800

• 末尾再帰では基本的に綺麗なプログラムを書こうと考えない事がポイント(末尾再帰の時点で大して綺麗に書けてない)。
  • whileループを無理矢理、再帰に書き換えるような勢いが大切。
  • 内容によっては既に末尾再帰形式の関数になっているような関数もある。
• Scalaでは相互再帰は末尾最適化をしない。

例えば以下のようなプログラム、

def odd(n: Int): Boolean = if (n = 1) {
  true
} else {
  even(n - 1)
}

def even(n: Int): Boolean = if (n = 0) {
  true
} else {
  odd(n - 1)
}

は、oddとevenを相互に呼び出し、自分自身の末尾で関数を呼び出す。 この形式はfact2と同様に、末尾に関数呼び出し以外の処理は残っていないが、末尾最適化されない。

• 相互再帰や複雑な再帰呼出しは、Trampolineという末尾最適化と同様のスタックを消費しない書き方がある。
  • スタックレスScala
• 原理主義的に再帰のみでゴリゴリimmutableなコードも書けるが、
  • そもそもScalaなら可能な限りコレクションを使ってループを書くべき。
  • 可読性や後でメンテナンスすることを考えるなら、Scalaの場合はwhile文やfor文が現実的な選択肢かも知れない。
    • 関数を呼び出す側から見た時に、参照透過な関数になっていればOKという考え方もアリとみなす。
• 結論としては、関数型プログラミングでのループは再帰やfor/whileのような構文ではなく、 mapやfilterといったコレクション関数を使うのが一般的。
  • 大半のループはコレクション関数(のメソッドチェーン)で記述した方が、可読性が高く、メンテナンスもしやすい簡潔なコードが書ける。

無名関数(ラムダ抽象)

scala> val f = ((a: Int) => a + 1)
f: Int => Int = $$Lambda$4017/598382925@72f0dff7

scala> f(1)
res19: Int = 2

scala> f(2)
res20: Int = 3

• おなじみの無名関数。大体、無名関数かラムダ式でググったら出てくる。ラムダ式とはあんまり言わない(方がいい)(※個人の意見です)。
• 第一級オブジェクトとしての関数(データとして扱う事が出来る関数): 関数を渡す、値として保持できる。
• 無名関数の式が評価されると、関数オブジェクトが生成される。
  • 関数オブジェクトは、コンストラクタによって生成される他のJavaオブジェクトと同様に扱えるオブジェクト (型となるクラスを持ち、インスタンスとして扱われるように)なる。
• オブジェクトなのでデータを持たせる事もできる。(後述のクロージャを参照)
• C言語の関数のポインタと何が違うのか? / JavaのStrategyパターンと何が違うのか。
  • 関数のポインタと違い、データ(値)を保持する。
  • JavaのStrategyパターンと違い、インターフェースを必要としない。
• map/filter/reduce(fold)関数や、その他様々な高階関数に渡す時によく使用する。(後述の高階関数を参照)

レキシカルスコープ(Lexical scope, 静的スコープ)

• "Scope"とは範囲のこと。"Lexical"とはLiterallyくらいの意味で深い意味はない。
• レキシカルスコープとは、静的に、ある変数を参照した時、どのタイミングで代入された値が参照されるかが決まるスコープのこと。
• Scalaの変数(valや引数)の有効範囲は、レキシカルスコーピングによって決定される。
• 変数の値を取り出す時、(Scalaの)レキシカルスコープでは、ネストした変数定義において最も内側で定義された変数を参照する。

以下の2つのコード。

scala> {val a = 1; ((a:Int) => ((a:Int) => a)(3))(2) }
res5: Int = 3

または、

scala> {val a = 1; {val a = 2; {val a = 3; a} } }
res11: Int = 3

この時、aは、最も内側にあるaは、ネストしている中で最も手前で定義された変数(引数)aの値を参照する。 次の例では、最も内側のスコープを抜けているので上記とは別の値を見に行く。

scala> {val a = 1; ((a:Int) => {((a:Int) => a)(3); a})(2) }
res10: Int = 2

または、

scala> {val a = 1; {val a = 2; {val a = 3;} a} }
res14: Int = 2

• レキシカルスコープ自体は、モダンな言語では一般的な仕組み。
  • Scalaだけでなく、JavaScriptやTypeScript(たぶん)、Ruby(たぶん)、Python、Groovy(たぶん)でも共通。
    • 但し、JavaScriptのvarはFunctionスコープと呼ばれるスコープ(レキシカルスコープとは若干違う)なので注意が必要。 (文法によってスコープのとり方が異なる)
  • 今とはなっては、(静的スコープではない)動的スコープを持つ言語の方が珍しい。動的スコープを採用している言語はほとんどない。
    • 現代で実用的な動的スコープがメインの言語はEmacs Lispくらい。。。
    • 但し、implicit parameterは動的スコープ的な役割に近い。 implicit parameterは、社内だとFutureのExecutionContextがよく使われる。

クロージャ(Closure)

• 自由変数を含む(使用した)関数によって生成された関数オブジェクトの事をクロージャ(Closure)という。
  • 自由変数: 関数定義中にその関数のブロック内で定義されていない変数のこと。
  • クロージャは、自由変数に束縛された値(の参照)をデータとして保持する。
  • ブロックから抜けだした関数オブジェクトは、レキシカルスコーピングによって保持した変数の参照を保持し続ける。
• プログラミング言語のClojureの事ではない。
• レキシカルスコープ同様、モダンな言語では一般的なしくみ。関数定義や無名関数からクロージャを生成できる。

以下では、関数オブジェクトがaseqという変数名が保持しているSeqの参照を持つ。

scala> val hSeq = {val aseq = Seq(1, 2, 3, 4, 5); ((i: Int) => aseq(i)) }
hSeq: Int => Int = $$Lambda$4005/1227571506@23364fcf

scala> hSeq(1)
res8: Int = 2

scala> hSeq(2)
res9: Int = 3

一番外側で定義された変数hSeqは、ブロック内部で生成された関数オブジェクト(クロージャ)を束縛している。 この関数オブジェクトに引数を与える事で、aseqに束縛されたSeqの値にアクセスできる。

• 上記のような書き方により、JavaやScalaで指定するprivateよりも更に細かいスコープ(変数の有効範囲)の制御が可能になる。

クロージャの使い方いろいろ

次のように2つの関数からのみ参照可能なHashmapを定義できる。

scala> val (f, g) = { val hmap = Map("ab"-> 1, "ac" -> 2);
     | (((s: String) => hmap(s)), ((s: String) => hmap("a"++s))) }
f: String => Int = $$Lambda$4011/179665104@2da7b9bf
g: String => Int = $$Lambda$4012/49123780@295afa48

scala> f("b")
java.util.NoSuchElementException: key not found: b
  at scala.collection.immutable.Map$Map2.apply(Map.scala:129)
  at .$anonfun$x$1$1(<console>:12)
  at .$anonfun$x$1$1$adapted(<console>:12)
  ... 36 elided

scala> g("b")
res17: Int = 1

scala> f("ac")
res18: Int = 2

• 勿論、ListやHashmapだけでなく、関数を保持する関数を作ったり、関数を保持する関数を保持する関数など色々作れる。
• ただし、関数オブジェクトを濫用し続けると、不用意に意図しないクロージャを生成してしまう事も考えられる。 このような場合、GCによって回収されない参照をいつまでも保持し続けることになってしまう。 (とは言え、普通に書いている限りだとこのようなバグは殆ど無いかも知れない)
• クロージャにより変数はそのスコープの外を出ても有効である場合がある。 つまり、ローカル変数は、変数を定義した関数本体が終了しても生き残る。
  • 変数が生存している(有効である)期間のことをエクステント(extent)という。
• クロージャとは逆に、関数内に自由変数を含まないような関数のことをコンビネータ(combinator)という。 ただし、Scalaだと、パーサコンビネータ以外ではコンビネータという言い方はあまりされない(みたい)。
• クロージャを使うことで計算を遅延(将来に実行)させられる。典型的な使用例がFutureによるコールバック。
  • 遅延させたい計算は常に無名関数のシンタックスで囲うことで遅延させる事が出来る。dao.findById(id)がFutureを返す時、mapに渡されたrow =>以降は、Futureの結果が返ってくるまで実行されない。

dao.findById(id).map { row => row.name }

クロージャでif関数っぽいものを作る

クロージャとは直接関係ないが、無名関数の性質を応用することでif関数のようなものも作ることが出来る。 つまり関数呼び出し時に引数が実行されない形の書き方ができる。

(※しかし、Scalaだとここまでしなくてもcall-by-nameで書ける)

scala> def ifFunction(b: Boolean, f: () => Unit, g: () => Unit) = if (b) f() else g()
ifFunction: (b: Boolean, f: () => Unit, g: () => Unit)Unit

scala> ifFunction(true, { () => println("a"); }, { () => println("b"); })
a

scala> ifFunction(false, { () => println("a"); }, { () => println("b"); })
b

無名関数で囲わない書き方の場合、次のようになる。

scala> def ifFunction(b: Boolean, f: Unit, g: Unit) = if (b) f else g
ifFunction: (b: Boolean, f: Unit, g: Unit)Unit

scala> ifFunction(false, { println("a"); }, { println("b"); })
a
b

関数呼び出しは、引数を評価した後、その結果が関数に渡されて関数自体が実行される。 そのため、通常の呼び出しだと、引数が評価されてしまうが、引数を関数化することで、 引数の評価を遅延させる(実質的には実行させない)事ができる。

クロージャで作るリスト

• クロージャのみでリスト構造(データ構造)を作ることが可能。
  • ルール: データ構造やクラスは使わない。
  • 関数型プログラミングにおける大道芸の一つ。

単方向連結リスト(いわゆるLinkedList)の実装。

scala> val cons = (x: Int, xs: Int => Any) => ((i: Int) => if (i == 0) x else xs(i - 1))
cons: (Int, Int => Any) => Int => Any = $$Lambda$3648/212142471@1c3cc65d

scala> val emptyF = (x: Int) => null
emptyF: Int => Int = $$Lambda$3649/558084802@db6ad80

scala> val ls = cons(4, cons(3, cons(2, emptyF)))
ls: Int => Any = $$Lambda$3650/2033873015@4f08ca31

scala> ls(1)
res57: Any = 3

scala> ls(3)
res58: Any = null

scala> ls(2)
res59: Any = 2

関数がAny型を返す、リストの上限を超えた時nullを返すのは、簡単のため。 consでリストを構築する。空リストはemptyFで表現する。

高階関数(High-order function)

• 関数オブジェクトは値として他の関数に渡したり、関数を受け取る、変数に束縛するなど、Javaオブジェクトのような扱いが可能。
• 関数を引数としたり、戻り値として使用する関数の事を高階関数という。
  • 関数に関数を渡す時は、無名関数として渡す(mapなど)こともできるし、定義された名前付きの関数を渡すこともできる。
    • 特に、無名関数を渡すパターンは、コレクション関数を使用する時によく使う。

無名関数を他の関数に渡す。

scala> Seq(1, 2, 3).map(i => i + 2)
res0: Seq[Int] = List(3, 4, 5)

定義済みの他の関数に渡す。

scala> def add2(i: Int): Int = i + 2
add2: (i: Int)Int

scala> Seq(1, 2, 3).map(add2)
res4: Seq[Int] = List(3, 4, 5)

• 高階関数を使用することで、ほぼ無制限にプログラム中の任意のロジック(具体的なコード)を抽象化できる。
  • ちなみに、データ型や関数の定義などは抽象化できない。。。
  • 抽象化したい部分を関数化し、差分のみをそれぞれ別関数にして、抽象化した関数に差分の関数を渡すという方法。
  • コード全体の至る所で使用できて、DRYに書けるというメリットはあるが。 やり過ぎると原型を留めなくなるので注意が必要。
• 部分適用/カリー化(Partial application / Curring)
  • 複数の引数を取る関数を一つの引数のみを取る関数に書き換えることをカリー化という。
  • 途中まで値を代入して、途中からの値を別の高階関数の中で代入させたい時などに使用する。

以下がカリー化の例。上はカリー化されていない関数。下が上の関数をカリー化した関数。

scala> def sum(a: Int, b: Int, c: Int): Int = a + b + c
sum: (a: Int, b: Int, c: Int)Int

scala> def sum(a: Int)(b: Int)(c: Int): Int = a + b + c
sum: (a: Int)(b: Int)(c: Int)Int

次のようにして、途中までの値を入れておく。

scala> sum(1)(2) _
res1: Int => Int = $$Lambda$3054/194743804@57e5ed15

そして、次のように使うことができる。

scala> Seq(1, 2, 3).map(sum(1)(2))
res3: Seq[Int] = List(4, 5, 6)

• 途中まで引数の値を適用し別の無名関数を生成する書き方を部分適用という。
  • 部分適用とカリー化は間違えやすいことで有名。
    • カリー化 != 部分適用

関数合成

• 2つの関数を合成する。数学の合成関数と考え方は同じ。: f(g(x)) = (f . g)(x)
• 合成関数用の関数として、compose/andThenが用意されている。
• ちなみに、Scalaだとcompose使いたいケースでは、メソッドチェーンで書く事が多いのであんまり使わない。

次の場合、

def withComma(ls: Seq[String]) = ls.mkString(",")
def trimString(ls: Seq[String]) = ls.map(_.trim.toInt)
def multiply20(ls: Seq[Int]) = ls.map (_ * 20).map(_.toString)

StingのSeqの要素を20倍してカンマ区切りの文字列にしたい。。。

val ls = Seq(" 20", " 30 ", "40 ", "50")

しかもなんか変な空白入ってる。。。

scala> withComma(multiply20(trimString(ls)))
res31: String = 400,600,800,1000

括弧が多い。。。

scala> (withComma compose multiply20 compose trimString)(ls)
res32: String = 400,600,800,1000

さらにこれを関数化したい。。。

scala> val multiply20c = withComma compose multiply20 compose trimString
multiply20c: Seq[String] => String = scala.Function1$$Lambda$605/1525241607@1f18de49

scala> multiply20c(ls)
res33: String = 400,600,800,1000

引数を定義して関数化すると、変数が増えて冗長になるので、関数を合成の場合は、composeのみで組み合わせを表現し関数を定義できる。 composeだとわかりにくい? そんな時の為にandThenという関数が用意されている。

• composeとandThenは順序が逆。

composeの場合

scala> (((s:String) => s.toInt) compose ((x:Int)=> x.toString))(20)
res24: Int = 20

andThenの場合

scala> (((x:Int)=> x.toString) andThen ((s:String) => s.toInt))(20)
res22: Int = 20

andThenを使って前述のコードを書き直す。

scala> val multiply20c = trimString andThen multiply20 andThen withComma
multiply20c: Seq[String] => String = scala.Function1$$Lambda$4021/295193997@7d9759a

scala> multiply20c(ls)
res34: String = 400,600,800,1000

処理の順番が明確になり、分かりやすくなった。

• ライブラリやフレームワークなどのコードで時々登場する。
  • 使いすぎると分かりづらくなる事も多いが、Scalazだと頻繁に使われていたりする。
  • Playframeworkのアクション合成(action composition)などでも類似の概念が登場する。
  • ただし、Scalaの場合、メソッドチェーンで書くほうが一般的なようなので、そこまで使わないかも知れない。
• 上記のような変数の登場しない合成による関数定義の仕方をポイントフリースタイル(point-free style)という。

部分関数(Partial function)

• ある特定の引数に対してのみ値を返す関数。
• ScalaのPartialFunctionが便利ですよ

まとめ

• Scalaでも他の関数型言語と同じように、関数を使ったプログラミングができることがわかる。 Javaよりは簡単かつ柔軟な書き方を実現するしくみが用意されている。
• Scalaだとメソッドチェーンによる書き方が多いので、ポイントフリースタイルや合成関数はあまり使わなさそう。