bussorenre Laboratory

bussorenre Laboratory

Scala における末尾再帰

背景

S-99: Ninety-Nine Scala Problems 等の例題を説いていると、よく再帰による実装を見かけます。

確かに、 Scala関数型デザイン&プログラミング―Scalazコントリビューターによる関数型徹底ガイド | Paul Chiusano, Rúnar Bjarnason, 株式会社クイープ | 工学 | Kindleストア 等の書籍にも、可能な限り再帰的な考え方で実装しろと書かれています。

しかし、「再帰でばかり実装すると、スタック領域を食いつぶしてしまうんじゃないのか?」という不安があります。 基本的に、関数呼び出しの際は、現在実行している関数の情報(レジスタ情報や引数・戻り先のポインタ)を、メモリ上のスタック領域と呼ばれるところに押し込んでいくので、再帰はスタック階層が深くなり、かの有名なスタックオーバーフローエラーが出ることになります。

普通の再帰

階乗(n!)を実装します。 階乗とは、例えば n = 5 の時、 5! = 5 x 4 x 3 x 2 x 1 = 120 となります。

scala で実装すると以下のようになります。

def fact(n: Int): BigInt =
  n match {
    case 0 => 1
    case _ => n * fact(n - 1)
  }

さて、n の値が小さいうちは普通に計算してくれますが、10000 とかぶっこむと StackOverflowError が出ます。

java.lang.StackOverflowError
  at scala.math.BigInt$.apply(BigInt.scala:38)
  at scala.math.BigInt$.int2bigInt(BigInt.scala:96)
  at .fact(<console>:14)
  at .fact(<console>:14)
  at .fact(<console>:14)
  at .fact(<console>:14)
  at .fact(<console>:14)
  at .fact(<console>:14)
  at .fact(<console>:14)
# 以下略

延々とfact関数を呼び出しており、エラーログ的にも優しくありません。

末尾再帰

Scala では、関数の最後の処理として自分自身を呼び出す再帰関数(これを末尾再帰と言う)を検知すると、パラメーターを新しい値に更新した後、再帰呼び出しを関数の冒頭にジャンプするコードに書き換える。らしい。 末尾再帰を検知すると、内部的にはwhile文に変換している。と捉えても大きな違いはなさそう。

実際にfact関数を末尾再帰にしてみる。

末尾再帰を妨げているのは、n * fact(n - 1) の部分で、この処理を別の関数として置き換え、その関数を再帰的に呼び出すように修正します。

def fact(n: Int): BigInt = {
  def innerFact(n: Int, f: BigInt): BigInt = 
    n match {
      case 0 => f
      case _ => innerFact(n - 1, n * f)
    }
  innerFact(n, 1)
}

fact の中に、内部関数としてinnerFact を定義しました。実装を見てもらえるとわかるように、関数の末尾は innerFact を呼び出すだけになっている。これにより、Scala の末尾再帰検出機構が働き、fact(10000) などもうまく実行してくれるようになります。

本当に書いた関数が末尾再帰になっているかを確認するには、 @tailrec アノテーションを利用します。

import scala.annotation.tailrec

@tailrec
def fact(n: Int): BigInt =
  n match {
    case 0 => 1
    case _ => n * fact(n - 1)
  }

<console>:19: error: could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position
           case _ => n * fact(n - 1)

def fact(n: Int): BigInt = {
  @tailrec
  def innerFact(n: Int, f: BigInt): BigInt = 
    n match {
      case 0 => f
      case _ => innerFact(n - 1, n * f)
    }
  innerFact(n, 1)
}

// 何もエラーが発生しない

普通に while で書けば良いんじゃないの?

関数型の流儀に反する以上の解をまだ得ていないので、誰か while じゃダメな理由を教えてください。

参考にしました

パターンマッチ

今日もScala。明日もScala。明後日もScala

Programming in Scala 第15章 ケースクラスとパターンマッチ。

// Java における比較対象
switch ( <セレクター式>) {
    case: 選択肢1
    case: 選択肢2
    default: その他
}
// Scala におけるパターンマッチ
<セレクター式> match {
    case 選択肢1
    case 選択肢2
    ......
 }

要するにSwitch 文の事……? 上から順番に与えられた選択肢を評価し、最初にマッチしたもののみを実行する。break 文などは特に不要。

expr match {
    case Hoge(e, 1) => e
    case Piyo(e,2) => e
    case Fuga(_, 3) => Nil

この時、e は変数パターンと呼ばれ、ワイルドカードのように機能し、右側の式で値を参照することが出来る。 _ は変数名束縛の無いワイルドカードで、全てのパターンにマッチするものの右側の式で参照できない。 それ以外は定数パターンで、特定の値のみを受け取る。

Java におけるswitch 文との違いは、

  • Java は 定数パターンしか扱えない
  • Java とか Cみたいにbreakを挟まないと行けないとかがない。先述の通り、最初にマッチしたものだけを実行する
  • マッチするパターンがなければ MatchError が返される。

じゃぁdefault の代わりにどうするのかと言われると、こうする

expr match  {
  case Hoge(1, e) => e
  case _ =>
}

この時、Hoge(1,e) にマッチしなかった場合は全て 次のcase _ にマッチする。何も結果を返さないので、このmatch 式全体の戻り値は(): Unit になる。

if とかと同様に、match も なので、必ず値を返す。

Scala におけるList の操作

Programming in Scala 第三版16章 リストの操作

言語によっても仕様が異なり混乱しやすいリスト。 Scala における 配列とリストの違いは

  1. リストはイミュータブルオブジェクトで、リストの要素は代入によって置き換えられない
  2. 内部的にはLinked List

配列と同じ部分でいうと、Scala におけるArray, List は[T]で示される型のみを格納できる。

// String 型しか格納できない
val fruits: List[String] = List("apple", "banana", "cherry")

// nums 型しか格納できない。型を省略した場合、型推論でなんとかしてくれる
val nums = List(1,2,3,4,5)

中間演算子によるこういう書き方も可能。 この場合 :: は右結合の演算子なので、() を省略しない場合こういう順番になる

val nums = 1 :: 2 :: 3 :: 4 :: Nil

val nums = 1 :: ( 2 :: (3 :: (4 :: Nil)))

リスト同士の連結は

val nums = List(1,2,3,4) ::: List(5,6,7)

この時、もちろん 両項の List[T] 型は一致していなければならない。 この演算子も右結合

パターンマッチによるリストの要素の分解が出来る。

scala > val List(a, b, c) = fruit

a: String = apple
b: String = banana
c:String = cherry

上記構文では、List の要素数が3の型に限られてしまうので、要素数が可変の場合は、 (リストの要素数がわからない場合は)先程の中間演算子を用いるともっとあっさり解決する

scala> val a :: b :: remining = fruit

a: String = apple
b: String = banana
remining:List[String] = List(cherry)

Scala を書く時に他言語と混乱しないための文法備忘

Scala 初めてまだ数日勢。毎日ずっと書いていないと、元々書いていた他の言語に邪魔されて思考が途切れてしまう。 特にSwift と混合しやすい。次点で Go, javascript と混合してしまいやすい。

苦しんで自分にscala を叩き込む

宣言

val, var を使う。

val hoge = new Object()
var i = 100

特にval。よく間違えてlet とか const とか書いて怒られている。さすがにauto と書くことはない。

メソッド宣言と呼び出し

まずは宣言

def hogepiyo(arg1: type1, arg2: type2): ReturnType = {
  // write something
}

def foobar(arg1: Type1, arg2: Type2): ReturnType = foo * bar

呼び出しが少しややこしい。

qiita.com

からの抜粋になるが、

class Hoge {
  //引数リストがないメソッド
  def f1 = 1
  //引数がないメソッド
  def f2() = 1
  //引数が1つのメソッド
  def f3(x: Int) = x * 2
  //引数が複数のメソッド
  def f4(x: Int, y: Int) = x * y
}

//引数リストがないメソッド
////hoge.f1()
////hoge f1()
hoge.f1                                           //> res0: Int = 1
hoge f1                                           //> res1: Int = 1
//空行は伊達じゃないよ

//引数がないメソッド
hoge.f2()                                         //> res2: Int = 1
hoge.f2                                           //> res3: Int = 1
hoge f2()                                         //> res4: Int = 1
hoge f2                                           //> res5: Int = 1
//空行は伊達じゃないよ

//引数が1つのメソッド
hoge.f3(1)                                        //> res6: Int = 2
hoge f3(1)                                        //> res7: Int = 2
hoge f3 1                                         //> res8: Int = 2
hoge.f3 { 1 }                                     //> res9: Int = 2
hoge f3 { 1 }                                     //> res10: Int = 2
////hoge.f3 1

//引数が複数のメソッド
hoge.f4(1, 2)                                     //> res11: Int = 2
hoge f4(1, 2)                                     //> res12: Int = 2
////hoge.f4 1, 2
////hoge f4 1, 2

基本的にはjava と同じ書き方をすれば動くっちゃ動く。が、関数型っぽくないらしい。引数がない時に()を省略できるのはまぁruby とかでもやってきたから慣れれば出来る。

後置記法というらしいが、

hoge piyo

みたいな感じで、.()も省略されている場合はその次の行は空行である必要があるみたい。

hoge piyo foo

みたいな感じで、引数が一つの場合は後ろを空行にしなくてもいいらしい。この差異の意図がよくわかってない。 例文として、0 to 3 のような演算子のように使うメソッドは省略することが多い的なことが書いてあった。なんとなくわからんでもない。

あとは、副作用があるかないかでも変わる。副作用がある場合は必ずhoge.piyo(foo) みたいに書く。

コンストラクタ宣言

class Hoge(a: Type1, b:Type2) {
  require(a != b)
  // do something
  
  // auxiliary constructor
  def this(c: Type3) = this(c, c*c)
}

ruby / javascriptに近いかも。インスタンスが生成される時、上から順に実行されている。

requireでバリデーションが出来る。くっそ便利。バリデーションに失敗したら例外が帰る。

Scala ではコンストラクタはただ一つのプライマリコンストラクタを持つことが出来る。それ以外のコンストラクタは補助コンストラクタ(Auxiliary Constructor) と呼ばれ、必ずプライマリコンストラクタ(Primary Constructor)を呼ぶ必要がある。

ここはSwift で苦しんだのでわりとあっさり理解した。

制御構文

厳密にはscala には制御構文はない(本当に?) if 等は全部 if 文ではなく if 式である。 式 = statement なので、必ず結果を返す。

if式

要するに三項演算子だと思えば理解が早い。

val a = if (a or b) functionA else functionB

さて、else が必要ないときはelse を省略することが出来るが、() というUnit 型が返される(何もしないという副作用だけを返す)

if (a > 0) {
    println("hoge")
} else {
    println("piyo")
}

このようなif文のような事も普通に出来る。この時、計算結果を返さないので副作用のみを扱う関数2つを定義し、条件式でどっちを実行するか決定している。みたいなイメージになる。

if 式 というかif 関数と思えば扱いやすいのかな。3値(条件式, 関数1, 関数2)を元に演算結果を返す。みたいな。

for 式

あとで別記事で書く

まだWIP

Intelli J Idea でScalaを書く環境を整えてく(自分用)

業務用ということで、会社から Inteli J Idea を支給してもらった。この機会にぜひとも乗りこなしたい。

Emacs バインドをある程度使えるようにする

Emacs使いのための IntelliJ IDEAキーマップ チートシート を参考にする。

Emacs+ Patched というプラグインを入れ、 Preferences -> Keymap で Emacs+ を選択し、Duplicate... でコピーを作成

Preferences -> Appearance & Behavior -> Presentation Assistant で、Main keymap に作成したコピーを指定

変更 キーバインド アクション 追加 Ctrl+X, Ctrl+B Switcher

PlantUML

IntelliJ IDEAでPlantUMLを書く

PlantUML でドキュメントを書いているので、同じくプラグインをぶっこむ。

初めて入れてみたけどくっそ便利すぎて今までの人生は何だったのか感

Scala における Unit型と副作用

C系とか Java 系みたいな、手続き型には無い(無くはないけどそんなに重要視されていない)概念に 作用と副作用がある。

関数型言語では、プログラムは値を返す存在とみなされる。

Programming in Scala においては 3.5 あたりに

まずは、val、イミュータブルオブジェクト、副作用のないメソッドを優先させ、それらで出来る限りやってみる。 明確なニーズと正当化できる理由がある時に限り、var、ミュータブルオブジェクト、副作用のあるメソッドを使う

と書いてある。

副作用とはどういうことか。

例えば「標準出力にHello world を出力する」という仕様に対しては、前回書いたHelloworld だと

object HelloWorld {
  def main(args: Array[String]): Unit = {
    println("Hello, Scala world!")
  }
}

こうなっており、引数を受け取って結果(作用)を返していない(=副作用しか無い)メソッドになっている。 こういうメソッドにはUnit型が使われる。