Scala Programming

WHAT'S NEW

• 2014/11/01 Scala 入門 : 自分型アノテーションと構造的部分型, ヒープ を追加
• 2014/10/26 Yet Another Scala Problems (7) を追加

CONTENTS

• お気楽 Scala プログラミング入門
• Yet Another Scala Problems
• 参考 URL
• 権利・免責事項など

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

CONTENTS

• 2014/07/20 はじめに
• 2014/07/20 Scala の基礎知識
  使ってみよう、整数と浮動小数点数、算術演算子、比較演算子、論理演算子、文字と文字列、変数、条件分岐、while による繰り返し、for による繰り返し、FizzBuzz 問題、オブジェクト指向の簡単な説明、実行結果、素因数分解、数値積分 (πの計算)
• 2014/07/21 Scala の基礎知識 (2)
  関数の基礎知識、関数の定義方法、局所変数と大域変数、局所変数の定義と有効範囲、整数の和、局所関数の定義、累乗の計算、配列、統計量の計算、素数を求める、エラトステネスの篩、値呼びと参照呼び、可変長引数、デフォルト引数、名前付き引数
• 2014/07/26 再帰定義
  再帰定義の基本、再帰定義のポイント、ユークリッドの互除法、フィボナッチ関数、末尾再帰、二重再帰を末尾再帰に変換する、末尾再帰を繰り返しに変換する、相互再帰
• 2014/07/26 高階関数
  関数を引数にとる関数、多相性、データの探索、無名関数、カリー化、部分適用、関数の合成
• 2014/07/27 リスト
  リストの構造、リストの生成と参照、リストの合成と分解、再帰定義によるリスト操作、リストの連結、リストの反転、リストの探索、Option、タプル (Tuple)
• 2014/07/27 パターンマッチング
  val や var でのパターンマッチング、match 式、リストのパターンマッチング、Option のパターンマッチング、連想リスト、挿入ソート
• 2014/08/02 高階関数 (2)
  マッピング、プレースホルダー、フィルター、畳み込み、畳み込みの使用例、foreach、for 内包表記、クイックソート、クイックソートの弱点、リストの平坦化
• 2014/08/02 レキシカルスコープとクロージャ
  レキシカルスコープ、レキシカルスコープと局所関数、クロージャ、環境の仕組み、ジェネレータ、イテレータ
• 2014/08/03 順列と組み合わせ
  順列の生成、バックトラック法の実装、プログラムの作成、高階関数版の作成、リストの中から n 個の要素を選ぶ順列、順列をリストに格納する、要素の選択、順列をリストに格納する (2)、Scala の permuations、組み合わせの数、パスカルの三角形、組み合わせの生成、組み合わせをリストに格納する、組み合わせをリストに格納する (2)、Scala の combinations
• 2014/08/09 パズルの解法
  問題１：小町算、問題２：覆面算、問題３：魔方陣、問題４：マスターマインド、解答１、別解、解答２、解答３、対称解の排除、解答４、プログラムの作成、何回で当たるか
• 2014/08/10 オブジェクト指向の基礎知識
  オブジェクトとは？、クラスとインスタンス、メソッド、継承、Scala のクラス、Scala のインスタンス、Scala のメソッド、コンストラクタ、補助コンストラクタ、メソッドの多重定義、Point クラス、toString メソッド、equals メソッド、シングルトンオブジェクト、コンパニオンオブジェクト、apply, unapply メソッド、case クラス
• 2014/08/16 継承
  単一継承、多重継承、継承の仕組み、単一継承の使い方、オーバーライド、型の継承、継承とオーバーライドの制限、抽象クラス、図形のクラス、キャストとポリモーフィズム
• 2014/08/16 トレイト
  トレイトとは？、多重継承とその問題点、Mix-in、トレイトの使い方、図形のクラス、Ord トレイト、クラスからトレイトへのキャスト
• 2014/08/17 連結リスト
  可変 (mutable) な連結リスト、連結リストの定義、作業用メソッド _nth、データの参照、データの更新、データの挿入、データの削除、連結リストの表示、実行例 (1)、マッピング、データの探索、フィルター、畳み込み、実行例 (2)、不変 (immutable) な連結リスト、メソッドの定義、実行例 (3)、高階関数の定義、実行例 (4)
• 2014/08/23 二分探索木
  木構造、二分木、節の定義、データの探索、データの挿入、データの削除、最小値と最大値、データ削除のプログラム、巡回 (traverse)、二分木の畳み込み、public メソッドの作成、実行例 (1)、不変 (immutable) な二分木、メソッドの定義、実行例 (2)
• 2014/08/24 例外処理
  例外の捕捉、try 式の使い方、例外の送出、例外の定義、大域脱出、finally 節
• 2014/08/24 有理数
  有理数の定義、有理数の生成、算術演算子の定義、暗黙の型変換、変換関数の定義、比較演算子の定義、その他のメソッド、小町分数、Four Four's、数式のパターン、クラスの定義、数式の生成、実行結果
• 2014/08/30 多相クラス
  クラスの型パラメータ、双方向リスト、双方向リストの仕様、クラスの定義、データの参照、データの更新、データの挿入、データの削除、実行例、制限付きリスト、スタック、継承は is-a 関係を表す、mutable なスタックの実装、キュー、mutable なキューの実装
• 2014/08/31 多相クラス (2)
  抽象型とは？、スタックの仕様、リストを使ったスタックの実装、配列を使ったスタックの実装、リングバッファ、キューの仕様、配列を使ったキューの実装、簡単な実行例、immutable なスタックの実装、immutable なキュー、immutable なキューの実装、型パラメータの制限 (上限境界と下限境界)、Ordered トレイト、変位の指定 (非変、共変、反変)、mutable な多相型データ構造は非変
• 2014/09/06 多相クラス (3)
  Option の定義、不変 (immutable) で多相的な連結リスト、メソッドの作成、実行例、可視境界、不変 (immutable) で多相的な二分木、メソッドの作成、実行例
• 2014/09/06 入れ子クラスとイテレータ
  入れ子クラスとは？、内部クラス、無名クラス、抽象クラスとトレイトからインスタンスを生成する、イテレータ、双方向リストの改良、実行例
• 2014/09/07 経路の探索
  グラフ、隣接行列と隣接リスト、バックトラックによる探索、スタックによる深さ優先探索の実装、immutable なスタックを使う場合、幅優先探索、経路の管理、幅優先探索のプログラム、immutable なキューを使う場合、反復深化、反復深化のプログラム
• 2014/09/13 積木の移動
  問題の説明、データ構造の定義、積木を動かす、深さ優先探索、幅優先探索、反復深化
• 2014/09/13 パズルの解法 (2)
  問題１「騎士の周遊」、問題２「水差し問題」、問題３「Hoppers」、解答１、実行結果、解答２、実行結果、解答３、実行結果
• 2014/09/20 パッケージ
  パッケージの宣言、パッケージの入れ子、一つのファイルに複数のパッケージを定義する、import 文、import 文の便利な機能、オブジェクトのインポート、パッケージオブジェクト、スコープ限定子、シールドクラス
• 2014/09/20 列 (Seq)
  リストと列の違い、不変 (immutable) な列、列の生成、可変 (mutable) な列、WrappedArray、列のパターンマッチング、列の操作メソッド、列のソート、Ordering、暗黙の引数
• 2014/09/28 マップ (Map) とセット (Set)
  マップとは？、不変 (immutable) なマップ、データの追加、データの削除、キーと値の取得、マップと列の変換、可変 (mutable) なマップ、マップの更新、セットとは？、不変 (immutable) なセット、データの追加、データの削除、集合演算、要素の取得、セットと列の変換、可変 (mutable) なセット、セットの更新、TreeMap と TreeSet、たらいまわし関数、メモ化による高速化、実行結果
• 2014/10/05 遅延評価
  遅延評価とは？、たらいまわし関数の高速化、遅延ストリーム、遅延ストリームの構造、整数列の生成、フィボナッチ数列の生成、遅延ストリームの操作メソッド (1)、高階関数、遅延ストリームの操作メソッド (2)、高階関数 (2)、組 (tuple) を生成するストリーム、無限ストリームで組 (tuple) を生成する場合、素数列の生成、エラトステネスの篩、Stream の使い方
• 2014/10/12 パズルの解法 (3)
  8 パズルの説明、幅優先探索による解法、実行結果、双方向探索、最長手数の求め方、プログラムの作成、反復深化による解法、手数の遇奇性、プログラムの作成、下限値枝刈り法、下限値枝刈り法のプログラム
• 2014/10/18 整数の論理演算とビット操作
  ビット演算子、組み合わせの生成、組み合わせに番号を付ける方法、組み合わせを番号に変換、番号を組み合わせに変換、ちょっと便利なビット操作、ビットが 1 の個数を求める、BitSet
• 2014/10/18 N Queens Problem
  8 クイーンの解法、単純な生成検定法、実行結果、無駄を省く、実行結果 (2)、プログラムの改良、実行結果 (3)、ビット演算による高速化、実行結果 (4)
• 2014/10/25 継続渡しスタイル
  継続とは？、継続渡しスタイル (CPS) とは？、再帰呼び出しと継続渡しスタイル、二重再帰と継続渡しスタイル、CPS の便利な使い方、二分木の巡回を CPS で実装、二分木と遅延ストリーム、TailCalls
  2014/10/25 Appendix: 末尾再帰と繰り返し、末尾再帰をスタックオーバーフローせずに実行する
• 2014/11/01 自分型アノテーションと構造的部分型
  自分型アノテーションとは？、型の指定、実装の切り替え、構造的部分型とは？、ダック・タイピング
• 2014/11/01 ヒープ
  配列によるヒープの実装、ヒープの構築 (1)、ヒープの再構築、ヒープの構築 (2)、優先度つき待ち行列、実行例、PriorityQueue の使い方

はじめに

Scala はスイス連邦工科大学 (EPFL) の Martin Odersky 教授によって設計されたプログラミング言語です。Scala はオブジェクト指向言語と関数型言語を統合した言語で、Java プラットフォーム (Java 仮想マシン) 上で動作します。Scala のオブジェクト指向はクラスベースで、継承は「単一継承」のみサポートしています。「多重継承」はサポートされていませんが、そのかわり Trait (トレイト) を使って Ruby のような Mix-in (ミックスイン) が可能です。また、Java と簡単に連携できるので、Java のライブラリ資産を有効に活用することができます。

Scala は強く型づけされた言語で、コンパイル時に静的な型チェックを行うことで、多くのエラーを検出することができます。Scala には SML/NJ, OCaml, Haskell などの関数型言語で有名な「型推論」という機能があるので、型宣言を省略してプログラムを簡潔に記述することができます。もちろん、パターンマッチング、クロージャ、カリー化など、関数型言語でよく使われている便利な機能がサポートされています。

M.Hiroi は Scala でプログラミングするのは初めてです。また、Java にも詳しいわけではないので、いきなり Scala に挑むのは無謀なことなのかもしれません。そこで、最初は M.Hiroi が知っている関数型言語の機能を中心に、簡単なプログラムを作りながら Scala を勉強していきたいと思っております。なにぶん初心者が作るプログラムなので、間違いや Scala の作法に反することがあるかと思います。何かお気づきの点がありましたらご指摘お願いいたします。たいしたことはできませんが、よろしければお付き合いくださいませ。

●ダウンロード

Scala は次のサイトからダウンロードできます。Windows 用のバイナリが用意されているので、とても簡単にインストールすることができます。

• The Scala Programming Language

なお、Scala を実行するには Java の実行環境が必要です。Oracle 社の Web サイト Java SE - Downloads からダウンロードすることができます。M.Hiroi は Java SE Development Kit 8 (JDK 8) をインストールしました。

●プログラムの実行

Scala はプログラムをコンパイルするコマンド scalac と、コンパイルしたプログラムを実行するコマンド scala があります。これは Java のコマンド javac, java と同じ関係です。また、引数を指定せずにコマンド scala を実行すると、対話モード (REPL : Read-Eval-Print-Loop) で Scala を使用することができます。

C>scala
Welcome to Scala version 2.11.1 (Java HotSpot(TM) Client VM, Java 1.8.0_05).
Type in expressions to have them evaluated.
Type :help for more information.

scala> 1 + 2 * 3;
res0: Int = 7

scala>:quit

C>

REPL で Scala のプログラムを入力して簡単に実行することができます。終了する場合はコマンド :quit (または :q) か CTRL-D を入力してください。

次はお馴染みの Hello, world! を表示するプログラムを作ってみましょう。

リスト : Hello.scala

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

ファイル名は Hello.scala とします。拡張子は scala です。ファイル名は object の名前 Hello と同じにしてください。 ^[*1] Scala の場合、ファイル名は object の名前 Hello と同じにする必要はありませんが、ここでは同じ名前にしています。たとえば、test.scala でもかまいません。

C>scalac Hello.scala

C>dir /B Hello.*
Hello.class
Hello.scala

C>scala Hello
Hello, world!

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

scala> Hello.main(Array())
Hello, world!

scala>

リスト：たらいまわし関数 (Scala)

object Tarai {
    def tak(x: Int, y: Int, z: Int): Int = {
        if (x <= y) z
        else tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
    }

    def main(args: Array[String]) {
        val start = System.currentTimeMillis
        tak(22, 11, 0)
        println((System.currentTimeMillis - start) + "msec")
    }
}

リスト：たらいまわし関数 (Java)

public class Tarai {
  static int tak(int x, int y, int z){
    if(x <= y)
      return z;
    else
      return tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y));
  }

  public static void main(String[] args){
    long start = System.currentTimeMillis();
    System.out.println(tak(22, 11, 0));
    long end = System.currentTimeMillis();
    System.out.println((end - start)  + "ms");
  }
}

• 2014/09/14 Yet Another Scala Problems (1), 解答
  整数の総和、多角数、めのこ平方、平方根、最大値と最小値、リストの削除、集合演算、連想リスト、選択ソート (配列)、リストの選択ソート
• 2014/09/21 Yet Another Scala Problems (2), 解答
  素因数分解、約数の個数、約数の合計値、約数、完全数、友愛数、リストの分割、分数を循環小数に変換、循環小数を分数に変換、バブルソート (配列)
• 2014/09/27 Yet Another Scala Problems (3), 解答
  zipWith、foldl2, foldr2、整数の分割 (分割数と列挙)、集合の分割、ベル数、完全順列、モンモール数、カッコ列の生成、カッコ列の総数 (カタラン数)
• 2014/10/04 Yet Another Scala Problems (4), 解答
  二分木をカッコ列に変換、カッコ列を二分木に変換、二分木の列挙、二分木の生成、リストの二分割、二分木の列挙 (2)、二分木の高さ、葉の個数、データの探索、二分木の高階関数、二分木の巡回 (深さ優先、幅優先)
• 2014/10/11 Yet Another Scala Problems (5), 解答
  配列の挿入ソート、配列のシェルソート、配列のクイックソート、リストのマージ、リストのマージソート、べき集合、連続した記号を部分リストにまとめる、ランレングス符号化、集合を要素数が等しい部分集合に分割
• 2014/10/19 Yet Another Scala Problems (6), 解答
  リストと Boolean による無符号整数 uint の実装、半加算器、全加算器、Int と uint の変換、論理演算、加算、減算、シフト、比較、乗算、除算
• 2014/10/26 Yet Another Scala Problems (7), 解答
  Int とリストによる無符号多倍長整数 (Bignum) の実装、Long と Bignum の変換、論理演算、ビットシフト、比較、加算、減算、乗算、除算、文字列と Bignum の変換

参考文献, URL

1. The Scala Programming Language (本家)
2. Scala プログラミング入門 (神戸大学, 田村直之先生)
3. スケーラブルで関数型でオブジェクト指向なScala入門 (@IT, 中村修太さん)
4. ひしだま's ホームページ, Scalaメモ(Hisidama's Scala Memo) (ひしだまさん)

権利・免責事項など

『お気楽 Scala プログラミング入門』の著作権は筆者「広井誠 (Makoto Hiroi) 」が保持します。無断使用や無断転載は禁止いたします。『お気楽 Scala プログラミング入門』で作成したプログラムはフリーソフトウェアとします。ご自由にお使いください。プログラムの改造や配布もご自由にどうぞ。その際は、出典を明記してくださるようお願いいたします。

ただし、これらのプログラムは無保証であり、使用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi) 」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。