Scalaでリスト処理

Table of Contents

1 概要

Scalaにはリストを始め,コレクションと呼ばれるさまざまなデータ構造が用意されている. ここでは,それらの基本的な使い方について学ぶ.

1.1 注意

本Webページの作成には Emacs org-mode を用い, 数式等の表示は MathJax を用いています. IEでは正しく表示されないことがあるため, Firefox, Safari等のWebブラウザでJavaScriptを有効にしてお使いください. また org-info.js を利用しており, 「m」キーをタイプするとinfoモードでの表示になります. 利用できるショートカットは「?」で表示されます.

2 リスト (List)

Scalaのリスト (scala.collection.immutable.List) について説明する.

Scalaでは,リストは List(x1, x2, …, xn) のように表記する.

scala> List(3, 1, 4)
res: List[Int] = List(3, 1, 4)

実際には res ではなく res0 のように番号の付いた名前が表示される. この名前は,結果を利用する場合などに使用できる.

リストは x1 :: x2 :: … :: xn :: Nil のようにも表記できる.

scala> 3 :: 1 :: 4 :: Nil
res: List[Int] = List(3, 1, 4)

これらはScalaの型推論により List[Int] (整数のリスト)とデータ型が推論されていることがわかる.

scala> List("a", "b", "c")
res: List[String] = List(a, b, c)

こちらは,List[String] (文字列のリスト) と推論されている.

では,複数のデータ型が混在したリストはどのようになるだろうか.

scala> List(3, 1, 4, 3.14)
res: List[Double] = List(3.0, 1.0, 4.0, 3.14)

scala> List("scala", 2.8)
res: List[Any] = List(scala, 2.8)

IntとDoubleが混在したリストは,IntがDoubleに昇格されて, List[Double] (Doubleのリスト)になっている.

StringとIntが混在したリストは List[Any] になっている. Anyはすべてのクラスの親クラスである(ルートクラス).

2.1 Range

Range(m, n)は,m以上n未満の整数の列を作成する (m until n でも良い). リストに変換するにはtoListを用いる.

scala> Range(2, 8).toList
res: List[Int] = List(2, 3, 4, 5, 6, 7)
scala> (2 until 8).toList
res: List[Int] = List(2, 3, 4, 5, 6, 7)

m to nを用いれば,m以上n以下の整数の列を生成できる.

scala> (2 to 8).toList
res: List[Int] = List(2, 3, 4, 5, 6, 7, 8)

m to n by kを用いれば,m以上n以下でk毎の整数の列を生成できる.

scala> (2 to 8 by 3).toList
res: List[Int] = List(2, 5, 8)

実は,toListでリストに変換にしなくてもリストと同様に処理を行えるのだが, ここでは話を簡単にするためtoListでリストに変換している. なお,以下では必要がなければtoListを用いないことにする.

リストのコンパニオンオブジェクト (scala.collection.immutable.List$) を用いて, 以下のようにしても良い.

scala> List.range(2, 8)
res: List[Int] = List(2, 3, 4, 5, 6, 7)
scala> List.range(2, 8, 2)
res: List[Int] = List(2, 4, 6)

2.2 リストの基本的なメソッド

リストには様々なメソッドが用意されている (scala.collection.immutalbe.List を参照).

ここでは,基本的なメソッドを紹介する.

まず,リストを変数listに代入しておく. var は新しい変数の定義を表し,list が変数名である.

scala> var list = List(2, 7, 1, 8)
list: List[Int] = List(2, 7, 1, 8)

なお,再代入をしない変数の場合は val を用いる. ここでは,どちらを用いても良い.

scala> val list = List(2, 7, 1, 8)
list: List[Int] = List(2, 7, 1, 8)
  • headはリストの先頭要素を求める (Lispのcar).
    scala> list.head
    res: Int = 2
    
  • tailはリストの先頭要素を取り除いたリストを求める (Lispのcdr).
    scala> list.tail
    res: List[Int] = List(7, 1, 8)
    
    scala> list.tail.tail.tail.head
    res: Int = 8
    
    scala> list.tail.tail.tail.tail
    res: List[Int] = List()
    
  • :: はリストの先頭に要素を付け加えたリストを求める (Lispのcons).
    scala> 3 :: list
    res: List[Int] = List(3, 2, 7, 1, 8)
    

    +: でも良い.

    scala> 3 +: list
    res: List[Int] = List(3, 2, 7, 1, 8)
    

    特に後述のSeqについては +: のほうを用いる.

  • lengthはリストの長さを求める (Lispのlength).
    scala> list.length
    res: Int = 4
    

    sizeでも良い.

    scala> list.size
    res: Int = 4
    
  • isEmptyは空リストかどうかを調べる (Lispのnull).
    scala> list.isEmpty
    res: Boolean = false
    
  • == はリストを比較する (Lispのequal).
    scala> list == List(2, 7, 1, 8)
    res: Boolean = true
    
  • lastはリストの最後の要素を求める.
    scala> list.last
    res: Int = 8
    
  • initはリストの最後の要素を除いた残りのリストを求める.
    scala> list.init
    res: List[Int] = List(2, 7, 1)
    
  • :+ はリストの最後に要素を付け加えたリストを求める.
    scala> list :+ 3
    res: List[Int] = List(2, 7, 1, 8, 3)
    
  • apply(n)はn番目の要素を求める.
    scala> list.apply(3)
    res: Int = 8
    

    単にlist(i)でも良い.

    scala> list(3)
    res: Int = 8
    
  • take(n)は最初のn個の要素からなるリストを求める.
    scala> list.take(2)
    res: List[Int] = List(2, 7)
    
  • takeRight(n)は最後のn個の要素からなるリストを求める.
    scala> list.takeRight(3)
    res: List[Int] = List(7, 1, 8)
    
  • drop(n)は最初のn個の要素を除いたリストを求める.
    scala> list.drop(2)
    res: List[Int] = List(1, 8)
    
  • dropRight(n)は最後のn個の要素を除いたリストを求める.
    scala> list.dropRight(3)
    res: List[Int] = List(2)
    
  • contains(x)はxが要素に含まれているかどうかを調べる.
    scala> list.contains(1)
    res: Boolean = true
    
    scala> list.contains(3)
    res: Boolean = false
    
  • ::: はリストを連結する (Lispのappend).
    scala> list ::: list
    res: List[Int] = List(2, 7, 1, 8, 2, 7, 1, 8)
    

    ++ でも良い. 特に後述のSeqについては ++ のほうを用いる.

  • reverseは逆順のリストを求める (Lispのreverse).
    scala> list.reverse
    res: List[Int] = List(8, 1, 7, 2)
    
  • sortedは昇順にソートしたリストを求める.
    scala> list.sorted
    res: List[Int] = List(1, 2, 7, 8)
    

    降順にするには以下のようにする.

    scala> list.sorted(Ordering[Int].reverse)
    res: List[Int] = List(8, 7, 2, 1)
    
  • sumは全要素の和を求める.
    scala> list.sum
    res: Int = 18
    
  • productは全要素の積を求める.
    scala> list.product
    res: Int = 112
    
  • maxは全要素の最大値を求める.
    scala> list.max
    res: Int = 8
    
  • minは全要素の最小値を求める.
    scala> list.min
    res: Int = 1
    
  • リストのコンパニオンオブジェクト List に定義されている fill メソッドを用いると, 同一要素を連続したリストを作成できる.
    scala> List.fill(5)(1)
    res: List[Int] = List(1, 1, 1, 1, 1)
    

2.3 練習問題

  1. 1から7までの整数の総和,1から63までの整数の総和はいくつか.
    (解答例)
    scala> (1 to 7).sum
    res: Int = 28
    scala> (1 to 63).sum
    res: Int = 2016
    

    平成28年は西暦2016年である. どちらも1からある数までの整数の総和(三角数)になっているのは面白い. さらに,7も63も \(2^n-1\) の形の数になっている!

  2. リストlistの最後の要素はlist.lastで求めることができるが, list(list.size - 1)やlist.takeRight(1).headなどでも求めることができる. 他にはどのような方法があるか.
    (解答例)
    scala> list.takeRight(1)(0)
    res: Int = 8
    scala> list.reverse.head
    res: Int = 8
    scala> list.reverse(0)
    res: Int = 8
    scala> list.drop(list.size - 1).head
    res: Int = 8
    scala> list.drop(list.size - 1)(0)
    res: Int = 8
    
  3. 整数のリストlistの全要素の平均値を求めるにはどうすれば良いか (ヒント: toDouble メソッドで整数を実数に変換する必要がある).
    (解答例)
    scala> list.sum.toDouble / list.size
    res: Double = 4.5
    
  4. 1から19までの奇数の総和を求めるにはどうすれば良いか.
    (解答例)
    scala> (1 to 19 by 2).sum
    res: Int = 100
    

    1 から \(2n-1\) までの奇数の総和は \(n^2\) になる.

  5. リストlistのi番目からj番目の前までの要素を取り出したリストを求めるにはどうすれば良いか. なお先頭は0番目とする.i=1, j=3 の場合を考えよ.listがList(2,7,1,8)の場合はList(7,1)となる.
    (解答例)
    scala> list.drop(1).take(3-1)
    res: List[Int] = List(7, 1)
    

    上では説明していないが slice を用いれば同様のことができる.

    scala> list.slice(1, 3)
    res: List[Int] = List(7, 1)
    

2.4 階乗の計算

これまで説明したメソッドを用いると,nの階乗の値を求めることができる. nの階乗は1からnの値の積だから,10の階乗は以下のようにして計算できる.

scala> (1 to 10).product
res: Int = 3628800

では20の階乗はどうなるだろうか.

scala> (1 to 20).product
res: Int = -2102132736

これは,20の階乗の値が 231 以上で,Intの範囲を超えたためである. そこで 1L のように記述してLongで計算する.

scala> (1L to 20).product
res: Long = 2432902008176640000

しかし30の階乗にすると,Longの範囲も超えてしまう.

scala> (1L to 30).product
res: Long = -8764578968847253504

BigIntを用いれば,大丈夫!

scala> (BigInt(1) to 30).product
res: BigInt = 265252859812191058636308480000000

100の階乗や1000の階乗でもへっちゃらだ.

2.5 練習問題

  1. 0の階乗にあたる (1 to 0).product の値は何になるだろうか. また,なぜそのような値になるか考えてみよ.
    (解答例)
    scala> (1 to 0).product
    res: Int = 1
    

    0個の要素の積は乗算の単位元である 1 になるのが自然である.

  2. \(n\) 個から \(r\) 個取り出す順列の個数 \({}_n\mbox{P}_r\) を求めるにはどうすれば良いか.
    (解答例)

    以下は \({}_{100}\mbox{P}_{20}\) を求めている.

    scala> val n = 100
    scala> val r = 20
    scala> (BigInt(n-r+1) to n).product
    res: BigInt = 1303995018204712451095685346159820800000
    
  3. \(n\) 個から \(r\) 個取り出す組合せの個数 \({}_n\mbox{C}_r\) を求めるにはどうすれば良いか.
    (解答例)

    以下は \({}_{100}\mbox{C}_{20}\) を求めている.

    scala> val n = 100
    scala> val r = 20
    scala> (BigInt(n-r+1) to n).product / (BigInt(1) to r).product
    res: BigInt = 535983370403809682970
    

3 関数定義

Scalaで関数 (function)を定義する.

scala> def inc(x: Int): Int = x + 1
inc: (x: Int)Int

「inc」が関数名,「x: Int」が引数名とそのデータ型, その右の「Int」が返り値のデータ型, 「=」の右の「x + 1」が関数定義本体である.

C言語での以下のような定義に対応する.

int inc(int x) {
  return x + 1;
}

以下のように入力すれば,REPL中で実行できる.

scala> inc(123)
res: Int = 124

関数の返り値のデータ型Intは,型推論で決定できるので記述を省略できる.

scala> def inc(x: Int) = x + 1
inc: (x: Int)Int

if式を用いると,2つの整数の大きいほうを求める関数を定義できる.

scala> def larger(x: Int, y: Int) = if (x > y) x else y
inc: larger: (x: Int,y: Int)Int

次に,整数のリストの全要素の平均値を求める関数averageを定義してみる.

scala> def average(list: List[Int]) = list.sum / list.size
average: (list: List[Int])Int

実行すると以下のような結果になってしまい,Doubleの平均値が得られない.

scala> average(List(1,2))
res: Int = 1

toDouble メソッドでDoubleに変換すれば良い. 返り値の型もDoubleと推論されている.

scala> def average(list: List[Int]) = list.sum.toDouble / list.size
average: (list: List[Int])Double

average(List(1,2))
res: Double = 1.5

3.1 練習問題

  1. \(n\) 個から \(r\) 個取り出す順列の個数 \({}_n\mbox{P}_r\) を求める関数 permutation(n, r) を定義せよ.
    (解答例)
    scala> def permutation(n: Int, r:Int) = (BigInt(n-r+1) to n).product
    scala> permutation(100, 20)
    res: BigInt = 1303995018204712451095685346159820800000
    
  2. 空でない整数リストをひとつ左に回転させたリストを求める関数rotateLeftを定義せよ. rotateLeft(List(1,2,3))の結果はList(2,3,1)である.
    (解答例)
    scala> def rotateLeft(list: List[Int]) = list.tail :+ list.head
    scala> rotateLeft(List(1,2,3))
    res: List[Int] = List(2, 3, 1)
    
  3. 空でない整数リストをひとつ右に回転させたリストを求める関数rotateRightを定義せよ. rotateRight(List(1,2,3))の結果はList(3,1,2)である.
    (解答例)
    scala> def rotateRight(list: List[Int]) = list.last +: list.init
    scala> rotateRight(List(1,2,3))
    res: List[Int] = List(3, 1, 2)
    
  4. 整数リストが回文かどうか調べる関数palindromeを定義せよ. palindrome(List(1,2,1))やpalindrome(List(1,2,2,1))は真である.
    (解答例)
    scala> def palindrome(list: List[Int]) = list == list.reverse
    scala> palindrome(List(1,2,1))
    res: Boolean = true
    
  5. 与えられた整数リストのi番目からj番目の前までの要素を取り出したリストを求める関数sliceを定義せよ. 先頭を0番目とする.
    (解答例)
    scala> def slice(list: List[Int], i: Int, j: Int) = list.take(j).drop(i)
    scala> slice(list, 1, 3)
    res: List[Int] = List(7, 1)
    

3.2 総称メソッド

上の練習問題中の rotateLeft, rotateRight, palindrome などを, 整数リストだけでなく任意のデータ型のリストに対して動作するように定義したい.

このような場合,Scalaではメソッド (関数)を 総称メソッド (generic method)として定義する. 総称メソッドの定義では,以下のようにメソッド名の後ろに型パラメータを指定する.

scala> def rotateLeft[A](list: List[A]) = list.tail :+ list.head

ここで A が型パラメータでありリストの要素のデータ型を表している. 型パラメータ A を用いると,引数 list のデータ型は List[A] となる.

このように定義すれば,整数のリストだけでなく任意のデータ型のリストに対して動作するようになる.

scala> rotateLeft[Int](List(1, 2, 3))
res: List[Int] = List(2, 3, 1)

scala> rotateLeft[String](List("a", "b", "c"))
res: List[String] = List(b, c, a)

型パラメータを指定している部分は Scala 処理系が型推論してくれるので,省略できる.

scala> rotateLeft(List(1, 2, 3))
res: List[Int] = List(2, 3, 1)

scala> rotateLeft(List("a", "b", "c"))
res: List[String] = List(b, c, a)

3.3 練習問題

  1. rotateRightを総称メソッドとして定義し,実行せよ.
  2. 関数palindromeを総称メソッドとして定義し,実行せよ.

4 リストと関数

4.1 mapとfilterなど

Scalaでは, リストの要素に関数 (function)を適用した新しいリストを求めることなどが簡単に行える.

リストの各要素に関数を適用するにはmapを用いる.

scala> list.map(inc)
res: List[Int] = List(3, 8, 2, 9)

Scalaでは,いちいち定義しなくても,関数を利用することができる ( 匿名関数, anonymous function).

scala> list.map(x => x + 1)
res: List[Int] = List(3, 8, 2, 9)

ここで「x => x + 1」が匿名関数の定義で,最初の「x」が引数名,「x + 1」の部分が関数本体である.

さらに,下線 _ を用いると引数名を省略して記述できる.

scala> list.map(_ + 1)
res: List[Int] = List(3, 8, 2, 9)

Scalaのリストには,このように関数を引数とする様々なメソッドが用意されている.

  • map(f)は,リスト x1, x2, …, xn に対して リスト f(x1), f(x2), …, f(xn) を求める.
    scala> list.map(_ > 2)
    res: List[Boolean] = List(false, true, false, true)
    
  • filter(f)は,リスト x1, x2, …, xn に対して f(xi) が真になる要素からなるリストを求める.
    scala> list.filter(_ > 2)
    res: List[Int] = List(7, 8)
    
    scala> (2 until 8).filter(_ % 2 != 0)
    res: IndexedSeq[Int] = Vector(3, 5, 7)
    
  • count(f)は,リスト x1, x2, …, xn に対して f(xi) が真になる要素の個数を求める.
    scala> list.count(_ > 2)
    res: Int = 2
    

    7と8の二つの要素があるので,2が返る.

  • forall(f)は,リスト x1, x2, …, xn に対して すべての f(xi) が真になる時だけ真を返す.
    scala> list.forall(_ > 2)
    res: Boolean = false
    
    scala> list.forall(_ > 0)
    res: Boolean = true
    
  • exists(f)は,リスト x1, x2, …, xn に対して ある f(xi) が真になる時だけ真を返す.
    scala> list.exists(_ > 2)
    res: Boolean = true
    
    scala> list.exists(_ > 8)
    res: Boolean = false
    
  • indexWhere(f)は,リスト x1, x2, …, xn に対して f(xi) が真になる最初の i を返す(存在しない時は -1 を返す).
    scala> list.indexWhere(_ > 2)
    res: Int = 1
    
    scala> list.indexWhere(_ > 8)
    res: Int = -1
    
  • sortWith(f)は,比較関数 f を用いてソートしたリストを求める.
    scala> list.sortWith((a,b) => a > b)
    res: List[Int] = List(8, 7, 2, 1)
    
    scala> list.sortWith(_ > _)
    res: List[Int] = List(8, 7, 2, 1)
    
  • sortBy(f)は,関数 f で変換した結果の昇順でソートしたリストを求める.
    scala> list.sortBy(a => -a)
    res: List[Int] = List(8, 7, 2, 1)
    
    scala> list.sortWith(-_)
    res: List[Int] = List(8, 7, 2, 1)
    

4.2 練習問題

以下を行う方法を答えよ.

  1. 整数のリストの各要素を二乗したリストを求める.
    (解答例)
    scala> list.map(x => x*x)
    res: List[Int] = List(4, 49, 1, 64)
    

    list.map(_*_) とは記述できない. _*_ と記述した場合,2引数の関数と解釈される.

  2. 整数のリストの各要素の二乗の合計を求める.
    (解答例)
    scala> list.map(x => x*x).sum
    
  3. 整数のリストの各要素の二乗の平均値を求める.
    (解答例)
    scala> list.map(x => x*x).sum.toDouble / list.size
    res: Double = 29.5
    
  4. 文字列のリスト中の各要素の文字列長の最大値を求める.
    (解答例)
    scala> List("ab", "ra", "ca", "dab", "ra").map(_.size).max
    res: Int = 3
    
  5. 整数のリスト中の偶数だけを取り出したリストを求める.
    (解答例)
    scala> list.filter(_ % 2 == 0)
    res: List[Int] = List(2, 8)
    
  6. 整数のリスト中の偶数の最大値を求める.
    (解答例)
    scala> list.filter(_ % 2 == 0).max
    res: Int = 8
    
  7. 整数のリスト中に偶数が含まれているかどうか調べる.
    (解答例)
    scala> list.exists(_ % 2 == 0)
    res: Boolean = true
    
  8. 整数のリストの全要素が奇数になっているかどうか調べる.
    (解答例)
    scala> list.forall(_ % 2 != 0)
    res: Boolean = false
    

4.3 練習問題

  1. 142857 を 1 倍から 7 倍までした結果のリストを求めよ.
    (解答例)
    scala> (1 to 7).map(142857 * _)
    res: IndexedSeq[Int] = Vector(142857, 285714, 428571, 571428, 714285, 857142, 999999)
    
  2. 1から100までの整数のうち,3の倍数でなく,また5の倍数でもない数のリストを求めよ.
    (解答例)
    scala> (1 to 100).filter(n => n % 3 != 0 && n % 5 != 0)
    res: IndexedSeq[Int] = Vector(1, 2, 4, 7, 8, 11, ..., 97, 98)
    scala> (1 to 100).filter(_ % 3 != 0).filter(_ % 5 != 0)
    res: IndexedSeq[Int] = Vector(1, 2, 4, 7, 8, 11, ..., 97, 98)
    
  3. 0, 101, 11011, 1110111, 111101111, 11111011111 のように,中央に0があり, 左右に同じ個数の1が並んでいる数を2進単眼数(http://oeis.org/A138148)という. 最初の10個の2進単眼数の文字列から成るリストを求めよ. ヒント: "1"*n で,1をn回繰り返した文字列が得られる. また + は文字列の連結を求める. たとえば "1"*2+"0"+"1"*2 の結果は "11011" である.
    (解答例)
    scala> (0 until 10).map(n => "1"*n + "0" + "1"*n)
    res: IndexedSeq[String] = Vector(0, 101, 11011, 1110111, 111101111, ..., 1111111110111111111)
    
  4. Integer.parseInt(s, 2) を用いると,2進数表現である文字列sから,整数値に変換できる. 最初の10個の2進単眼数の整数値から成るリストを求めよ.
    (解答例)
    scala> (0 until 10).map(n => "1"*n + "0" + "1"*n).map(Integer.parseInt(_, 2))
    res: IndexedSeq[Int] = Vector(0, 5, 27, 119, 495, 2015, 8127, 32639, 130815, 523775)
    

    平成27年は西暦2015年で,どちらも2進単眼数である.

  5. x.toBinaryString を用いると,整数xの2進数表現の文字列を求めることができる. 1800以上2100以下の自然数のうち,2進数表現が回文になっている値のリストを求めよ.
    (解答例)
    scala> def palindrome(s: String) = s == s.reverse
    scala> (1800 to 2100).filter(x => palindrome(x.toBinaryString))
    res: IndexedSeq[Int] = Vector(1831, 1879, 1911, 1935, 1967, 2015, 2047, 2049)
    
  6. 与えられた2以上の整数 \(n\) が素数の時に真を返す関数isPrimeを定義せよ.
    (解答例)

    \(n\) が 2以上 \(n\) 未満のどの数でも割り切れなければ \(n\) は素数なので, 以下のように定義できる.

    scala> def isPrime(n: Int) = (2 until n).forall(n % _ != 0)
    

    また,割る数は \(\sqrt{n}\) までで良いことに注意すれば以下のようになり,より効率的になる.

    scala> def isPrime(n: Int) = (2 to math.sqrt(n).toInt).forall(n % _ != 0)
    
  7. 10000以下の素数の個数を求めよ.
    (解答例)
    scala> (2 to 10000).count(isPrime)
    res: Int = 1229
    
  8. \(k\) が 1 から 10 の各整数値について \(10000k\) 以下の素数の個数を求めよ.
    (解答例)
    scala> (1 to 10).map(k => (2 to 10000*k).count(isPrime))
    res: IndexedSeq[Int] = Vector(1229, 2262, 3245, 4203, 5133, 6057, 6935, 7837, 8713, 9592)
    

    \(n\) 以下の素数の個数を求める関数 pi を定義しても良い.

    scala> def pi(n: Int) = (2 to n).count(isPrime)
    scala> (1 to 10).map(k => pi(10000*k))
    

    素数定理によれば pi(n) は \(n/\ln n\) で近似できる.

  9. 2以上10000以下の自然数のうち,2進数表現が回文になっている素数のリストを求めよ. また10進数表現が回文になっている素数のリストを求めよ. 2進数表現も10進数表現も回文になっている素数はあるか.
    (解答例)
    scala> (2 to 10000).filter(x => palindrome(x.toBinaryString)).filter(isPrime)
    res: IndexedSeq[Int] = Vector(3, 5, 7, 17, ..., 1831, 1879, 4889, ..., 8191)
    scala> (2 to 10000).filter(x => palindrome(x.toBinaryString) && isPrime(x))
    res: IndexedSeq[Int] = Vector(3, 5, 7, 17, ..., 1831, 1879, 4889, ..., 8191)
    scala> (2 to 10000).filter(x => palindrome(x.toString) && isPrime(x))
    res: IndexedSeq[Int] = Vector(2, 3, 5, 7, 11, 101, ..., 797, 919, 929)
    scala> (2 to 10000).filter(x => palindrome(x.toString) && palindrome(x.toBinaryString) && isPrime(x))
    IndexedSeq[Int] = Vector(3, 5, 7, 313)
    
  10. \(n=100\) の時, \(\sum_{i=1}^n 1/i\) を計算せよ.
    (解答例)
    scala> (1 to 100).map(1.0 / _).sum
    res: Double = 5.187377517639621
    

    \(\sum_{i=1}^n 1/i\) から \(\ln n\) を引いた値は, \(n \rightarrow \infty\) でおよそおよそ 0.57721 の値に収束する (オイラー定数).

    scala> (1 to 100).map(1.0 / _).sum - math.log(100)
    res: Double = 0.5822073316515288
    scala> (1 to 1000).map(1.0 / _).sum - math.log(1000)
    res: Double = 0.5777155815682065
    scala> (1 to 10000).map(1.0 / _).sum - math.log(10000)
    res: Double = 0.5772656640681646
    

    ただし,より精度の高い計算をするためには,計算誤差を小さくするため, 小さい値の項から先に和を求めるなどの工夫が必要になる.

  11. if (i % 2 == 0) x else y と記述すると, i が偶数の時 x の値を取り,奇数の時 y の値を取る. これを用いて \(a_i = \frac{(-1)^i}{2i+1}\) を一般項とする数列 \(a_0\), \(a_1\), … の最初の100項からなるリストを求めよ.
    (解答例)
    scala> (0 to 99).map(i => if (i % 2 == 0) 1.0/(2*i+1) else -1.0/(2*i+1))
    res: IndexedSeq[Double] = Vector(1.0, -0.3333333333333333, 0.2, ...)
    

    この数列は 1, -1/3, 1/5, -1/7, 1/9, … である.

  12. 上のリストの総和の4倍を求めよ. 項数を増やすとどのような値に近づくと思うか.
    (解答例)
    scala> (0 to 99).map(i => if (i % 2 == 0) 1.0/(2*i+1) else -1.0/(2*i+1)).sum * 4
    res: Double = 3.1315929035585537
    

    項数を増やすと非常に遅いが \(\pi\) に収束する.

    scala> (0 to 999).map(i => if (i % 2 == 0) 1.0/(2*i+1) else -1.0/(2*i+1)).sum * 4
    res: Double = 3.140592653839794
    scala> (0 to 9999).map(i => if (i % 2 == 0) 1.0/(2*i+1) else -1.0/(2*i+1)).sum * 4
    res: Double = 3.1414926535900345
    scala> (0 to 99999).map(i => if (i % 2 == 0) 1.0/(2*i+1) else -1.0/(2*i+1)).sum * 4
    res: Double = 3.1415826535897198
    

    ただし,より精度の高い計算をするためには,計算誤差を小さくするため, 小さい値の項から先に和を求めるなどの工夫が必要になる. たとえば,以下のようにすればより誤差が小さい.

    scala> (99999 to 0 by -1).map(i => if (i % 2 == 0) 1.0/(2*i+1) else -1.0/(2*i+1)).sum * 4
    res: Double = 3.1415826535897935
    
  13. \(\sum_{i=0}^n 1/i!\) は \(n \rightarrow \infty\) で \(e\) に収束する. \(n=20\) の場合の値を求めよ.
    (解答例)
    scala> (20 to 0 by -1).map(n => (1 to n).map(1.0 / _).product).sum
    res: Double = 2.718281828459045
    scala> (20 to 0 by -1).map(n => (1 to n).map(1.0 / _).product).sum - math.E
    res: Double = 0.0
    

4.4 reduceとfold

整数のリストlistについて,list.sum は要素の合計を求める. すなわちlistが x1, x2, …, xn の時, x1+x2+…+xn を求めている.

Scalaには,これを一般化したメソッドとしてreduceLeft, reduceRight, reduceが 用意されている.

  • reduceLeft(f)は,リスト x1, x2, …, xn に対して f(f(…f(f(x1, x2), x3), …), xn) を求める. たとえば n=4 の場合は,f(f(f(x1, x2), x3), x4) である.
    scala> list.reduceLeft((a,b) => a + b)
    res: Int = 18
    
    scala> list.reduceLeft(_ + _)
    res: Int = 18
    
    scala> list.reduceLeft((a,b) => 10*a + b)
    res: Int = 2718
    
    scala> list.reduceLeft(10*_ + _)
    res: Int = 2718
    

    リストの長さ n=1 の場合は, x1 がそのまま返り値となる.

    scala> List(12).reduceLeft((a,b) => a + b)
    res: Int = 12
    
  • reduceRight(f)は,リスト x1, x2, …, xn に対して f(x1, f(x2, … f(xn-1, xn)…)) を求める. たとえば n=4 の場合は,f(x1, f(x2, f(x3, x4))) である.
    scala> list.reduceRight((a,b) => a + b)
    res: Int = 18
    
    scala> list.reduceRight(_ + _)
    res: Int = 18
    
    scala> list.reduceRight((a,b) => a + 10*b)
    res: Int = 8172
    
    scala> list.reduceRight(_ + 10*_)
    res: Int = 8172
    

reduceLeft, reduceRight, reduceとよく似た関数として foldLeft, foldRight, foldがある.

  • foldLeft(e)(f)は,リスト x1, x2, …, xn に対して f(f(…f(f(f(e, x1), x2), x3), …), xn) を求める. たとえば n=4 の場合は,f(f(f(f(e, x1), x2), x3), x4) である.
    scala> list.foldLeft(0)(_ + _)
    res: Int = 18
    
    list.foldLeft(0)(10*_ + _)
    res: Int = 2718
    
  • foldRight(e)(f)は,リスト x1, x2, …, xn に対して f(x1, f(x2, … f(xn-1, f(xn, e))…)) を求める. たとえば n=4 の場合は,f(x1, f(x2, f(x3, f(x4, e)))) である.
    scala> list.foldRight(0)(_ + _)
    res: Int = 18
    
    scala> list.foldRight(0)(_ + 10*_)
    res: Int = 8172
    

reduceLeft(f) と reduceRight(f) は,関数 f が結合的な場合は同一結果になる. すなわち f(x,f(y,z)) = f(f(x,y),z) が成り立つ場合である. foldLeft(e)(f) と foldRight(e)(f) も, 関数 f が結合的で e が演算 f の単位元の場合,同一結果になる.

このような時には,reduce(f) あるいは fold(e)(f) を用いておくのが良い. 並列コレクションに対しては,並列に計算が行われ,効率が良くなる可能性がある.

4.5 練習問題

  1. リスト x1, x2, …, xn に対して x1 - x2 - … - xn を求めるにはどうすれば良いか. たとえば List(3,1,4) に対しては 3-1-4 すなわち -2 を求めたい.
    (解答例)
    scala> List(3,1,4).reduceLeft(_ - _)
    res: Int = -2
    

    reduceRightだと 3-(1-4) すなわち 6 になってしまう.

    scala> List(3,1,4).reduceRight(_ - _)
    res: Int = 6
    
  2. 0と1を要素とするリストで2進数を表しているとする. 整数値を求めるにはどうすれば良いか. たとえば List(1,1,0,1) から,13を求めるにはどうすれば良いか.
    (解答例)
    scala> List(1,1,0,1).reduceLeft(2*_ + _)
    res: Int = 13
    

    List(1,1,0,1).reduceRight(_ + 2*_) とすると,逆順になっている2進表現から値を求めることができる.

    scala> List(1,1,0,1).reduceRight(_ + 2*_)
    res: Int = 11
    
  3. x ^ y は x と y のビット毎のXOR (exclusive or; 排他的論理和; \(x\oplus y\))を返す. 0から7までのXOR,すなわち 0 ^ 1 ^ 2 ^ ... ^ 7 はいくつになるか. また,0から15までのXOR,0から31までのXORはそれぞれどうなるか.
    (解答例)
    scala> (0 to 7).reduce(_ ^ _)
    res: Int = 0
    scala> (0 to 15).reduce(_ ^ _)
    res: Int = 0
    scala> (0 to 31).reduce(_ ^ _)
    res: Int = 0
    

    XORは結合的(すなわち \((x \oplus (y \oplus z)) = ((x \oplus y) \oplus z)\))なので, reduceLeftでもreduceRightのどちらでも良い. 0 から 2n-1 までのXORは,すべての桁で1が偶数回現れるから,結果は0になる.

  4. List(2,7,1,8).reduceLeft((a,b) => 100*a + b) の結果はどうなるか.
    (解答例)
    scala> List(2,7,1,8).reduceLeft((a,b) => 100*a + b)
    res: Int = 2070108
    
  5. List(2,7,1,8).reduceRight((a,b) => a + 100*b) の結果はどうなるか.
    (解答例)
    scala> List(2,7,1,8).reduceRight((a,b) => a + 100*b)
    res: Int = 8010702
    
  6. List("a","b","c").reduceLeft(_ + "," + _) の結果はどうなるか. また List("a","b","c").reduceRight(_ + "," + _) の結果はどうなるか. なお + は文字列の連結を求める.
    (解答例)
    scala> List("a","b","c").reduceLeft(_ + "," + _)
    res: String = a,b,c
    scala> List("a","b","c").reduceRight(_ + "," + _)
    res: String = a,b,c
    
  7. List("a","b","c").foldLeft("e")("(" + _ + "," + _ + ")") の結果はどうなるか.
    (解答例)
    scala> List("a","b","c").foldLeft("e")("(" + _ + "," + _ + ")")
    res: String = (((e,a),b),c)
    
  8. List("a","b","c").foldRight("e")("(" + _ + "," + _ + ")") の結果はどうなるか.
    (解答例)
    scala> List("a","b","c").foldRight("e")("(" + _ + "," + _ + ")")
    res: String = (a,(b,(c,e)))
    
  9. List("a","b","c","d").reduceRight("(" + _ + "+1/" + _ + ")") の結果はどうなるか.
    (解答例)
    scala> List("a","b","c","d").reduceRight("(" + _ + "+1/" + _ + ")")
    res: String = (a+1/(b+1/(c+1/d)))
    
  10. 以下のように,分母のさらに分数が含まれている分数を連分数 (https://ja.wikipedia.org/wiki/連分数) といい,分子が常に1の連分数を正則連分数という. $$ a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3}}} $$ 整数のリスト a0, a1, a2, …, an で,正則連分数を表すことにする. 正則連分数を表すリストから,その実数値を求める関数cfracを定義せよ. ヒント: 与えられた整数リストに対し,まず map(_.toDouble) で実数のリストに変換しておく.
    (解答例)
    scala> def cfrac(a: List[Int]) = a.map(_.toDouble).reduceRight(_ + 1.0/_)
    

    正則連分数 1,1,1,… は黄金数 φ = 1.618… に収束する.

    scala> cfrac(List(1,1,1,1,1))
    res: Double = 1.6
    scala> cfrac((1 to 20).map(_ => 1).toList)
    res: Double = 1.6180339985218035
    

    正則連分数 2,2,2,… は \(1+\sqrt{2}\) = 2.414… に収束する.

    scala> cfrac((1 to 20).map(_ => 2).toList)
    res: Double = 2.4142135623730963
    

4.6 foreachとfor

foreachで,リストの要素への繰り返し処理を行える.

scala> list.foreach { println }
2
7
1
8

scala> (1 to 4).foreach { println }
1
2
3
4

forを用いても同様の処理を行える.

scala> for (x <- list) { println(x) }
2
7
1
8

scala> for (x <- 1 to 4) { println(x) }
1
2
3
4

forでは,yieldを用いてmapと同様の処理が可能である.

scala> for (x <- list) yield x+1
res: List[Int] = List(3, 8, 2, 9)

複数の変数でループを回すこともできる.

scala> for (i <- list; j <- list) yield 10*i+j
res: List[Int] = List(22, 27, 21, 28, 72, 77, 71, 78, 12, 17, 11, 18, 82, 87, 81, 88)
scala> for (i <- 1 to 3; j <- 1 to 3) yield 10*i+j
res: IndexedSeq[Int] = Vector(11, 12, 13, 21, 22, 23, 31, 32, 33)

条件を if で記述することもできる.

scala> for (i <- 1 to 3; j <- 1 to 3 if i != j) yield 10*i+j
res: IndexedSeq[Int] = Vector(12, 13, 21, 23, 31, 32)

4.7 練習問題

  1. forを用いて 1! から 10! までを要素とするリスト(あるいはVector)を求めよ.
    (解答例)
    scala> for (n <- 1 to 10) yield (1 to n).product
    res: IndexedSeq[Int] = Vector(1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800)
    
  2. 文字 a,b,c のそれぞれを1文字から3文字まで繰り返した文字列から成るリストを求めよ. すなわち "a", "aa", "aaa", "b", "bb", "bbb", "c", "cc", "ccc" を求める.
    (解答例)
    scala> for (s <- List("a","b","c"); n <- 1 to 3) yield s * n
    res: List[String] = List(a, aa, aaa, b, bb, bbb, c, cc, ccc)
    
  3. 3桁の整数で,各桁の数の和が10に等しいものを求めよ.
    (解答例)
    scala> for (i <- 1 to 9; j <- 0 to 9; k <- 0 to 9; if i+j+k==10) yield 100*i+10*j+k
    res: IndexedSeq[Int] = Vector(109, 118, 127, 136, 145, ..., 811, 820, 901, 910)
    
  4. 1から10の整数nについて10nと10n+1を要素とするリスト 10, 11, 20, 21, …, 100, 101 を求めたい.どうすれば良いか.
    (解答例)
    scala> for (n <- 1 to 10; x <- List(10*n, 10*n+1)) yield x
    res: IndexedSeq[Int] = Vector(10, 11, 20, 21, 30, 31, ..., 100, 101)
    

5 列 (Seq)

列 (scala.collection.immutable.Seq) はリストの上位クラスであり, Seq 用に定義したメソッドは List にも利用できる.

scala> val seq = Seq(2, 7, 1, 8)
seq: Seq[Int] = List(2, 7, 1, 8)

scala> def s(seq: Seq[Int]) = seq.size
s: (seq: Seq[Int])Int
scala> s(seq)
res: Int = 4
scala> s(list)
res: Int = 4

したがって,特別な必要がない限り List ではなく Seq を用いるほうが良いだろう. ただ ::, ::: などのメソッドは利用できない. 代わりに +:, ++ を用いる.

6 集合 (Set)

Scalaでは,集合 (scala.collection.immutable.Set) もリストと同様に利用できる.

scala> val set = Set(2, 7, 1, 8, 2, 8)
set: scala.collection.immutable.Set[Int] = Set(2, 7, 1, 8)

なお,以下では出力中の「scala.collection.immutable.」の部分は省略する.

集合もリストと同様に様々なメソッドが用意されているが, 集合特有のものとしては以下がある.

  • intersect(s)は共通集合を求める(& を用いても良い).
    set.intersect(Set(3,1,4))
    res: Set[Int] = Set(1)
    
  • union(s)は和集合を求める(| を用いても良い).
    set.union(Set(3,1,4))
    res: Set[Int] = Set(8, 4, 1, 2, 7, 3)
    
  • diff(s)は差集合を求める(&~ を用いても良い).
    set.diff(Set(3,1,4))
    res: Set[Int] = Set(2, 7, 8)
    
  • subsetOf(s)は部分集合かどうかを調べる.
    scala> set.subsetOf(Set(3,1,4))
    res: Boolean = false
    
    scala> set.subsetOf(set)
    res: Boolean = true
    

リストへの変換はtoListを用いる.列ならばtoSeqを用いる.

scala> set.toList
res: List[Int] = List(2, 7, 1, 8)
scala> set.toSeq
res: Seq[Int] = ArrayBuffer(2, 7, 1, 8)

逆にリストからの変換はtoSetを用いる.

scala> list.toSet
res: Set[Int] = Set(2, 7, 1, 8)
scala> seq.toSet
res: Set[Int] = Set(2, 7, 1, 8)

6.1 練習問題

  1. 1 から 100 の整数から成る集合を変数 set1 に代入せよ.
    (解答例)
    scala> val set1 = (1 to 100).toSet
    set1: Set[Int] = Set(69, ...)
    
  2. set1 の各要素の二乗を4で割った余りから成る集合を求めよ.
    (解答例)
    scala> set1.map(x => x*x % 4)
    res: Set[Int] = Set(1, 0)
    scala> for (x <- set1) yield x*x % 4
    res: Set[Int] = Set(1, 0)
    
  3. 変数 evens に100以下の偶数の集合を代入せよ.
    (解答例)
    scala> val evens = (2 to 100 by 2).toSet
    evens: Set[Int] = Set(88, 10, 56, ..., 100)
    
  4. 変数 primes に100以下の素数の集合を代入せよ.
    (解答例)
    scala> def isPrime(n: Int) = (2 to math.sqrt(n).toInt).forall(n % _ != 0)
    scala> val primes = (2 to 100).filter(isPrime).toSet
    primes: Set[Int] = Set(5, 37, 29, ..., 83)
    
  5. 100以下の2つの素数の和で表せる数の集合を変数 primes2 に代入せよ.
    (解答例)
    scala> val primes2 = for (p1 <- primes; p2 <- primes) yield p1+p2
    primes2: Set[Int] = Set(69, 138, 88, ..., 100)
    
  6. 100以下の偶数で,2つの素数の和で表せない数の集合を求めよ.
    (解答例)
    scala> evens diff primes
    res: Set[Int] = Set(2)
    

    4以上の任意の偶数は,2つの素数の和で表せると予想されている (https://ja.wikipedia.org/wiki/ゴールドバッハの予想).

7 マップ (Map)

マップ (scala.collection.immutable.Map) は以下のように記述する.

scala> var map = Map("hamlet"->118, "ophelia"->31)
res: Map[String,Int] = Map(hamlet -> 118, ophelia -> 31)

-> 」の左辺がキー (key)で,右辺が値 (value)である. カッコでくくって対 (後述のPair)を用いても良い.

scala> Map(("hamlet", 118), ("ophelia", 31))
res: Map[String,Int] = Map(hamlet -> 118, ophelia -> 31)

+ 」により値を登録した新しいマップを求められる.

scala> map + ("horatio"->48)
res: Map[String,Int] = Map(hamlet -> 118, ophelia -> 31, horatio -> 48)

しかし,元のマップは変化していない(immutable)ので, 登録したマップを利用するには,変数に代入する必要がある.

scala> map = map + ("horatio"->48)
map: Map[String,Int] = Map(hamlet -> 118, ophelia -> 31, horatio -> 48)

+= 」を用いても良い.

scala> map += ("horatio"->48)

以下にマップの主なメソッドを示す.

  • 値が含まれているかどうかは,containsで調べる.
    scala> map.contains("hamlet")
    res: Boolean = true
    
    scala> map.contains("king")
    res: Boolean = false
    
  • 値を取り出すにはapplyあるいは Map名そのものを用いる.
    scala> map.apply("hamlet")
    res: Int = 118
    
    scala> map("hamlet")
    res: Int = 118
    

    キーが登録されていない場合には,エラーとなる.

    scala> map("king")
    java.util.NoSuchElementException: key not found: king
    
  • getOrElseを用いると登録されていない場合の値を指定できる.
    scala> map.getOrElse("hamlet", 0)
    res: Int = 118
    
    scala> map.getOrElse("king", 0)
    res: Int = 0
    
  • keysでキーの集合を求めることができる.
    scala> map.keys
    res: Iterable[String] = Set(hamlet, ophelia, horatio)
    
  • キーの個数は,sizeで求めることができる.
    scala> map.size
    res: Int = 3
    

    もちちん keys.size でも良い.

    scala> map.keys.size
    res: Int = 3
    
  • キーに対するフィルターはfilterKeysを用いる. 以下は,キー7文字以上のものだけを求めている.
    scala> map.filterKeys(_.length >= 7)
    res: Map[String,Int] = Map(ophelia -> 31, horatio -> 48)
    
  • マップに直接filterを適用する場合は, キーと値の対(後述のPair)を引数とする関数を与える. 以下は,値が40以上のものだけを求めている. なお,「 kv._2 」は対kvの2番目の要素(すなわち値)を取り出している.
    scala> map.filter(kv => kv._2 >= 40)
    res: Map[String,Int] = Map(hamlet -> 118, horatio -> 48)
    

    あるいは case のパターンマッチを用いた無名関数を利用しても良い. ここで case のまわりは ( ) ではなく { } でくくられていることに注意.

    scala> map.filter{ case (w,c) => c >= 40 }
    res: Map[String,Int] = Map(hamlet -> 118, horatio -> 48)
    
  • for でも同様の処理ができる.
    scala> for (kv <- map; if kv._2 >= 40) yield kv
    res: Map[String,Int] = Map(hamlet -> 118, horatio -> 48)
    scala> for ((w,c) <- map; if c >= 40) yield (w,c)
    res: Map[String,Int] = Map(hamlet -> 118, horatio -> 48)
    

8 リストのリスト

以下のようにリストのリストが与えられているとする.

scala> val lists = List(List(3,1,4), List(2,7,1,8,2,8), List(0,5,7,7))

要素である各リストの長さは,以下のようにして求められる.

scala> lists.map(_.size)
res: List[Int] = List(3, 6, 4)

scala> for (list <- lists) yield list.size
res: List[Int] = List(3, 6, 4)

8.1 練習問題

  1. 要素リストの長さの最大値を求めるにはどうすれば良いか.
    (解答例)
    scala> lists.map(_.size).max
    res: Int = 6
    scala> (for (list <- lists) yield list.size).max
    res: Int = 6
    
  2. 要素である全整数の合計(55になる)を求めるにはどうすれば良いか.
    (解答例)
    scala> lists.map(_.sum).sum
    res: Int = 55
    scala> (for (list <- lists) yield list.sum).sum
    res: Int = 55
    
  3. reduceLeftを用いて,要素リストを連結したリストを求めるにはどうすれば良いか.
    (解答例)
    scala> lists.reduceLeft(_ ++ _)
    res: List[Int] = List(3, 1, 4, 2, 7, 1, 8, 2, 8, 0, 5, 7, 7)
    

    for を用いることもできる.

    scala> for (list <- lists; x <- list) yield x
    res: List[Int] = List(3, 1, 4, 2, 7, 1, 8, 2, 8, 0, 5, 7, 7)
    
  4. foldLeftを用いて,要素リストを逆順にして連結したリストを求めるにはどうすれば良いか. ヒント: 空リストは List[Int]() で表す.
    (解答例)
    scala> lists.foldLeft(List[Int]())(_ ++ _.reverse)
    res: List[Int] = List(4, 1, 3, 8, 2, 8, 1, 7, 2, 7, 7, 5, 0)
    

    for を用いることもできる.

    scala> for (list <- lists; x <- list.reverse) yield x
    res: List[Int] = List(4, 1, 3, 8, 2, 8, 1, 7, 2, 7, 7, 5, 0)
    
  5. 各要素リストを集合に変換したリストを求めるにはどうすれば良いか.
    (解答例)
    scala> lists.map(_.toSet)
    res: List[Set[Int]] = List(Set(3, 1, 4), Set(2, 7, 1, 8), Set(0, 5, 7))
    scala> for (list <- lists) yield list.toSet
    res: List[Set[Int]] = List(Set(3, 1, 4), Set(2, 7, 1, 8), Set(0, 5, 7))
    
  6. 要素として現れる整数の集合を求めるにはどうすれば良いか.
    (解答例)
    scala> lists.map(_.toSet).reduceLeft(_ ++ _)
    res: Set[Int] = Set(0, 5, 1, 2, 7, 3, 8, 4)
    
  7. 行列をリストのリストで表す. 変数 matrix が List(List(3,1,4,1), List(2,7,1,8), List(0,5,7,7)) である時, 転置行列を求めるにはどうすれば良いか.
    (解答例)
    scala> val matrix = List(List(3,1,4,1), List(2,7,1,8), List(0,5,7,7))
    scala> (0 until matrix(0).size).map(j => (0 until matrix.size).map(i => matrix(i)(j)))
    res: IndexedSeq[List[Int]] = Vector(List(3, 2, 0), List(1, 7, 5), List(4, 1, 7), List(1, 8, 7))
    scala> for (j <- 0 until matrix(0).size) yield for (i <- 0 until matrix.size) yield matrix(i)(j)
    res: IndexedSeq[IndexedSeq[Int]] = Vector(Vector(3, 2, 0), Vector(1, 7, 5), Vector(4, 1, 7), Vector(1, 8, 7))
    scala> (0 until matrix(0).size).map(j => matrix.map(r => r(j)))
    res: IndexedSeq[List[Int]] = Vector(List(3, 2, 0), List(1, 7, 5), List(4, 1, 7), List(1, 8, 7))
    scala> for (j <- 0 until matrix(0).size) yield for (r <- matrix) yield r(j)
    res: IndexedSeq[IndexedSeq[Int]] = Vector(Vector(3, 2, 0), Vector(1, 7, 5), Vector(4, 1, 7), Vector(1, 8, 7))
    

    transpose メソッドでも同様の結果になる.

    scala> matrix.transpose
    res: List[List[Int]] = List(List(3, 2, 0), List(1, 7, 5), List(4, 1, 7), List(1, 8, 7))
    
  8. 行列をリストのリストで表す. i行j列からm行n列を取り出した部分行列を求めるにはどうすれば良いか. 変数 matrix が List(List(3,1,4,1), List(2,7,1,8), List(0,5,7,7)) である時, 1行2列から2行2列を取り出した部分行列はList(List(1, 8), List(7, 7))である.
    (解答例)
    scala> matrix.slice(1, 3).map(col => col.slice(2, 4))
    res: List[List[Int]] = List(List(1, 8), List(7, 7))
    scala> for (i <- 1 until 1+2) yield for (j <- 2 until 2+2) yield matrix(i)(j)
    res: List[List[Int]] = List(List(1, 8), List(7, 7))
    

8.2 flatMap

整数リストのリスト中から奇数だけを取り出して並べたリストを作成しよう. つまり上のlistsの場合, List(3,1,7,1,5,7,7) が求めたいリストである.

各要素リストについて下のようにfilterを実行すれば, 奇数リストのリストが得られる.

scala> lists.map(_.filter(_ % 2 != 0))
res: List[List[Int]] = List(List(3, 1), List(7, 1), List(5, 7, 7))

reduceLeft を用いて,要素リストを連結すれば答えが求まる.

scala> lists.map(_.filter(_ % 2 != 0)).reduceLeft(_ ++ _)
res: List[Int] = List(3, 1, 7, 1, 5, 7, 7)

flatMapメソッドを用いれば,mapと連結を一括して行うことができる. すなわち flatMap(f)は,リスト x1, x2, …, xn に対して f(x1), f(x2), …, f(xn) を連結したリスト,すなわち f(x1) ++ f(x2) ++ … ++ f(xn) を求める. mapしたリストを中間的に作成する必要がないため, flatMapを用いるほうがmapと連結を用いるよりも効率が良くなる.

scala> lists.flatMap(_.filter(_ % 2 != 0))
res: List[Int] = List(3, 1, 7, 1, 5, 7, 7)

関数 f として恒等関数 x => x を用いれば,単純なリストの連結になる. flatten メソッドも同じことを行う.

scala> lists.flatMap(x => x)
res: List[Int] = List(3, 1, 4, 2, 7, 1, 8, 2, 8, 0, 5, 7, 7)

scala> lists.flatten
res: List[Int] = List(3, 1, 4, 2, 7, 1, 8, 2, 8, 0, 5, 7, 7)

整数 i と j がそれぞれ 1 から 3 まで変化する時, 10*i+j を要素とするリストも flatMap を用いれば,以下のように求めることができる (Vectorが求まっているが toList でリストに変換できる).

scala> (1 to 3).flatMap(i => (1 to 3).map(j => 10*i+j))
res: IndexedSeq[Int] = Vector(11, 12, 13, 21, 22, 23, 31, 32, 33)

これは for を用いて以下のようにも記述できる. 実は,これは内部的に flatMap に変換されて実行されている.

scala> for (i <- 1 to 3; j <- 1 to 3) yield 10*i+j
res: IndexedSeq[Int] = Vector(11, 12, 13, 21, 22, 23, 31, 32, 33)

8.3 練習問題

  1. listsの各要素リストの先頭2要素を取り出したリストを求めるにはどうすれば良いか. 上の例の場合 List(3,1,2,7,0,5) が求める答えである.
    (解答例)
    scala> lists.flatMap(_.take(2))
    res: List[Int] = List(3, 1, 2, 7, 0, 5)
    scala> for (list <- lists; x <- list.take(2)) yield x
    res: List[Int] = List(3, 1, 2, 7, 0, 5)
    
  2. 整数 i, j, k がそれぞれ 1 から 3 まで変化する時, 100*i+10*j+k を要素とするリスト(あるいはVector)を求めるにはどうすれば良いか.
    (解答例)
    scala> (1 to 3).flatMap(i => (1 to 3).flatMap(j => (1 to 3).map(k => 100*i+10*j+k)))
    res: IndexedSeq[Int] = Vector(111, 112, 113, 121, ..., 333)
    scala> for (i <- 1 to 3; j <- 1 to 3; k <- 1 to 3) yield 100*i+10*j+k
    res: IndexedSeq[Int] = Vector(111, 112, 113, 121, ..., 333)
    

9 対と組 (Pair and Tuple)

List や Seq は長さが任意のデータ列である. 組 (Tuple)は長さが固定のデータ列である. 各要素のデータ型は異なっても良い. 長さ n のTupleは (a1,a2,…,an) のように記述する.

長さが2の組は,対 (Tuple2, Pair)と呼ばれる.

scala> val pair = ("scala", 2.9)
pair: (String, Double) = (scala,2.9)

対は,以下のように記述しても良い.

scala> "scala" -> 2.9
scala> Tuple2("scala", 2.9)
scala> Pair("scala", 2.9)

組の i 番目の要素は, _1, _2, _3 のようにその番号を用いたメソッドで取り出す.

scala> pair._1
res: String = scala
scala> pair._2
res: Double = 2.9

また,代入において,その要素を取り出すことができる.

scala> val (s,v) = pair
s: String = scala
v: Double = 2.9

9.1 練習問題

変数 pairs が以下のように定義されているとする.

scala> val pairs = for (x <- 1 to 3; y <- 1 to 3) yield (x,y)
pairs: IndexedSeq[(Int, Int)] = Vector((1,1), (1,2), (1,3), (2,1), ..., (3,3))
  1. pairs について,各対の第1要素と第2要素を交換したリストを求めるにはどうすれば良いか.
    (解答例)
    scala> pairs.map(p => (p._2,p._1))
    res: IndexedSeq[(Int, Int)] = Vector((1,1), (2,1), (3,1), (1,2), ..., (3,3))
    scala> for ((x,y) <- pairs) yield (y,x)
    res: IndexedSeq[(Int, Int)] = Vector((1,1), (2,1), (3,1), (1,2), ..., (3,3))
    
  2. pairs について,各対の第1要素から成る集合を求めるにはどうすれば良いか.
    (解答例)
    scala> pairs.map(_._1).toSet
    res: Set[Int] = Set(1, 2, 3)
    
  3. pairs について,第1要素と第2要素の和の昇順にソートしたリストを求めるにはどうすれば良いか (ヒント: sortBy を用いる)
    (解答例)
    scala> pairs.sortBy(p => p._1 + p._2)
    res: IndexedSeq[(Int, Int)] = Vector((1,1), (1,2), (2,1), ..., (2,3), (3,2), (3,3))
    

10 オプション型 (Option)

Scala では値が存在しない可能性がある場合などに Option 型を用いる. たとえば,以下のマップを考える.

scala> val ageMap = Map("Taro" -> 21, "Jiro" -> 19)
ageMap: Map[String,Int] = Map(Taro -> 21, Jiro -> 19)

ageMap.get(p) は,p の値が a の場合 Some(a) を返し, 値が存在しない場合 None を返す.

scala> ageMap.get("Taro")
res: Option[Int] = Some(21)
scala> ageMap.get("Saburo")
res: Option[Int] = None

Some(a) から値 a を取り出すには get メソッドを用いる. None に対して get を使用した場合は例外が発生する.

scala> ageMap.get("Taro").get
res Int = 21
scala> ageMap.get("Saburo").get
java.util.NoSuchElementException: None.get

Some(a) か None かは isEmpty メソッドで区別できる.

scala> ageMap.get("Taro").isEmpty
res: Boolean = false
scala> ageMap.get("Saburo").isEmpty
res: Boolean = true

Some(a) は長さ 1 のリスト,None は空リストと同様である. 例えば filter を用いることができる.

scala> ageMap.get("Taro").filter(_ >= 20)
res: Option[Int] = Some(21)
scala> ageMap.get("Jiro").filter(_ >= 20)
res: Option[Int] = None
scala> ageMap.get("Saburo").filter(_ >= 20)
res: Boolean = None

for でも同様のことができる.

scala> for (a <- ageMap.get("Taro"); if a >= 20) yield a
res: Option[Int] = Some(21)
scala> for (a <- ageMap.get("Jiro"); if a >= 20) yield a
res: Option[Int] = None
scala> for (a <- ageMap.get("Saburo"); if a >= 20) yield a
res: Option[Int] = None

文字列のリストに対して適用した例を見てみよう.

scala> val names = Seq("Taro", "Jiro", "Saburo")
res: Seq[String] = List(Taro, Jiro, Saburo)
scala> names.map(p => ageMap.get(p).filter(_ >= 20))
res: Seq[Option[Int]] = List(Some(21), None, None)
scala> names.map(p => ageMap.get(p).map(_ + 1))
res: Seq[Option[Int]] = List(Some(22), Some(20), None)

Option 型のデータはリストと同様なので,それらを連結することができる.

scala> Some(21) ++ Some(19)
res: Iterable[Int] = List(21, 19)
scala> Some(21) ++ None
res: Iterable[Int] = List(21)
scala> names.map(p => ageMap.get(p))
res: Seq[Option[Int]] = List(Some(21), Some(19), None)
scala> names.map(p => ageMap.get(p)).flatten
res: Seq[Int] = List(21, 19)

flatMap や for を用いるとその利点が明らかになる. 値が定義されてるものだけを簡潔に取り出すことが可能である.

scala> names.flatMap(p => ageMap.get(p))
res: Seq[Int] = List(21, 19)
scala> for (p <- names; a <- ageMap.get(p)) yield a
res: Seq[Int] = List(21, 19)

値が存在する場合と存在しない場合についての場合分けをせずに,統一的な処理が可能になっている.

10.1 練習問題

  1. names.map(p => ageMap.get(p).filter(_ >= 20).map(_ + 1)) の結果はどうなるか.
    (解答例)
    scala> names.map(p => ageMap.get(p).filter(_ >= 20).map(_ + 1))
    res: Seq[Option[Int]] = List(Some(22), None, None)
    
  2. names.flatMap(p => ageMap.get(p).filter(_ >= 20).map(_ + 1)) の結果はどうなるか.
    (解答例)
    scala> names.flatMap(p => ageMap.get(p).filter(_ >= 20).map(_ + 1))
    res: Seq[Int] = List(22)
    
  3. for (p <- names; a <- ageMap.get(p); if a >= 20) yield a + 1 の結果はどうなるか.
    (解答例)
    scala> for (p <- names; a <- ageMap.get(p); if a >= 20) yield a + 1
    res: Seq[Int] = List(22)
    

11 イテレータ (Iterator)

Iterator は List や Seq と良く似ているが, 要素を1度しか参照できない点が異なっている.

scala> val iter = Iterator(3, 1, 4)
iter: Iterator[Int] = non-empty iterator

1度要素を参照すると,その要素は削除される.

scala> iter.size
res: Int = 3

scala> iter.size
res: Int = 0

何度も参照したい場合には toList で List に変換すれば良い (toSeq で Seq に変換するのでも良い.この場合は,遅延評価される Stream データになる).

scala> val iter = Iterator(2, 7, 1, 8)
iter: Iterator[Int] = non-empty iterator
scala> val list = iter.toList
list: List[Int] = List(2, 7, 1, 8)

Iterator は 2度と参照できないという欠点はあるが, 巨大なサイズのデータでも List や Seq と同様に処理が可能になるという利点がある.

Iterator を利用しているメソッドとしては, リストのすべての順列を返す permutations や,すべての組合せを返す combination(n) がある.

scala> List(1,2,3).permutations.foreach(println)
List(1, 2, 3)
List(1, 3, 2)
List(2, 1, 3)
List(2, 3, 1)
List(3, 1, 2)
List(3, 2, 1)

scala> List(1,2,3).combinations(2).foreach(println)
List(1, 2)
List(1, 3)
List(2, 3)

他には,リストを n 個ずつのリストに分割する grouped(n), リストから連続する n 個の要素を取り出したリストを返す sliding(n) がある.

scala> (1 to 10).grouped(3).foreach(println)
Vector(1, 2, 3)
Vector(4, 5, 6)
Vector(7, 8, 9)
Vector(10)

scala> (1 to 10).sliding(3).foreach(println)
Vector(1, 2, 3)
Vector(2, 3, 4)
Vector(3, 4, 5)
Vector(4, 5, 6)
Vector(5, 6, 7)
Vector(6, 7, 8)
Vector(7, 8, 9)
Vector(8, 9, 10)

11.1 練習問題

  1. 整数列 seq の要素が,すべて異なっていることを調べる関数 alldiff(seq) を定義せよ.
    (解答例)
    scala> def alldiff(seq: Seq[Int]) = seq.combinations(2).forall(s => s(0) != s(1))
    scala> alldiff(Seq(1,2,3,4))
    res: Boolean = true
    scala> alldiff(Seq(1,2,3,4,1))
    res: Boolean = false
    
  2. 整数列 seq の要素が,昇順になっていることを調べる関数 ascending(seq) を定義せよ.
    (解答例)
    scala> def ascending(seq: Seq[Int]) = seq.sliding(2).forall(s => s(0) <= s(1))
    scala> ascending(Seq(1,3,5))
    res: Boolean = true
    scala> ascending(Seq(1,3,5,2))
    res: Boolean = false
    
  3. 整数列 seq 中で,連続する n 要素の和の最大値を求める関数 maxSum(n, seq) を定義せよ.
    (解答例)
    scala> def maxSum(n: Int, seq: Seq[Int]) = seq.sliding(n).map(_.sum).max
    scala> maxSum(3, Seq(3,1,4,1,5,9,2,6,5,3,5))
    res: Int = 17
    
  4. 与えられた整数列 seq の階差数列を求める関数diffSeq(seq)を定義せよ. 階差数列は,次の要素との差から成る数列である. たとえば Seq(2,7,1,8) の階差数列は Seq(5,-6,7) である.
    (解答例)
    scala> def diffSeq(seq: Seq[Int]) = seq.sliding(2).map(p => p(1)-p(0)).toSeq
    scala> diffSeq(Seq(2,7,1,8))
    res: Seq[Int] = Stream(5, ?)
    

    すべての要素を求めるには toList する.

    scala> diffSeq(Seq(2,7,1,8)).toList
    res: List[Int] = List(5, -6, 7)
    

Date: 2016-08-01 15:49:53 JST

Author: 田村直之

Validate XHTML 1.0