2013-07-15

Rust 基礎文法最速マスター (rust 0.7 編)

Rust

警告 (2014/1/25 追記)

以下の記事ですが、今となっては通用しない記述が多く含まれています。 0.7 から現在までに行われた大きな変更としては、思いつくだけでも

言語組み込み機能としての managed box が非推奨になった (将来削除され、ライブラリによる実装と置き換わる)
rusti ツールが削除された

というものがあります。おそらく、文中のコード例はコンパイルすら通らなくなっていることでしょう。また、今後も 1.0 に向け大きな変更が予定されています (DST や GC の実装など)。

文中の、言語の基本的なコンセプトに関する部分はかろうじて現在でも通用すると思いますが、その他の部分についてはきちんとメンテナンスされている文章 (公式のドキュメントなど) を参照してください。

以下、オリジナルの記事です。

ブログ移転後の最初の記事っということで、最近僕がハマっているプログラミング言語、 Rust の文法的な特徴について、簡単に紹介しようと思います。 Rust という言語は非常に良いものだと思うので、是非とも流行って欲しいです！！！

前書き

まず、文法について説明する前に、簡単に Rust 言語の立ち位置や目指すところについて簡単に説明します。また、Rust を実行する環境の構築方法および実行方法も簡単に説明しますので、本記事を読む際は、是非、環境を整えて、実際にコードを実行してみてください。

Rust とは？

Rust とは、プログラミング言語の名前です。Rust を日本語にすると、「さび」。命名の由来は分かりません。

Rust を開発したのは Graydon Hoare さん。当初は個人のプロジェクトでしたが、現在は Mozilla (Firefox/Thunderbird の開発元) のプロジェクトとなっており、GitHub で活発に開発が行われています。

Rust は、安全 (safe) で、並列 (concurrent) で、実用的 (practical) 、という 3 点をキーワードとして掲げています。サポートするパラダイムは、「手続き型プログラミング」、「メッセージパッシング方式の並列プログラミング」、「オブジェクト指向プログラミング」、「関数型プログラミング」と一通り網羅しており、好みのスタイルでプログラミング可能です。

言語の主要なターゲットは「システムプログラミング領域」で、C/C++ 並のパフォーマンスと、安全性の両立を実現しようとしています。具体的には、Rust を用いると、以下の2つの要件を満たしたプログラムを (比較的) 容易に作成することが可能になります。

C/C++ のように、「ポインタを用いたメモリ操作」や、「GC に依存しないメモリ獲得・解放」など、明示的なメモリ管理が可能
自動でメモリ管理される言語のように、「ダングリング・ポインタ (dangling pointer, 不正な領域を指すポインタ)」や「null ポインタ」、「ダブルフリー」、「メモリリーク」など実行時に発生しないことがコンパイル時に保証される

Rust の安全性に関しては、 Rust 開発者の一人である Tim Chevalier さんのプレゼンテーション資料にまとまっています。その他、Rust の言語仕様で特徴的な部分を以下に列挙します。

C/C++ 風の構文
ファーストクラスのオブジェクトとして扱える関数
クロージャ
代数的データ型と、パターンマッチによる分岐
ローカル変数の型推論
強い静的型付け
ジェネリクス
Haskell の型クラス風の trait を利用したオブジェクト指向プログラミング
並列タスクを考慮したメモリ管理体系 (タスクローカルなヒープとタスク間で共通なヒープの区別)
コンパイラによる、変数・値の有効範囲の静的なチェック

Rust で作成された大規模なソフトウェアしては、 Rust のコンパイラ rustc や、 Mozilla が実験的に開発中のブラウザ向けレンダリングエンジン Servo が存在します。

Rust のインストール

2013/07/07 時点での最新版は Rust 0.7 です。

公式サイトからソースをダウンロードしてコンパイルします。 Windows の場合はインストーラが用意されています。また Homebrew や pacman や apt-get 等で、バイナリからのインストールもできると思います。

GitHub から最新ソースをダウンロードしてコンパイルする方法については、以下を参照してください。

Note getting started developing Rust

Rust のプログラム実行

Rust プログラムを実行するためには、

コンパイラ (rustc) を使う
REPL (rusti) を使う

という2つの方法があります。それぞれについて説明します。

`rustc` の使い方

rustc は、Rust のソースコードから実行バイナリを生成します。実行バイナリを作成する場合は、ソースコード中に main 関数を含んでいる必要があります。本記事中のコード例を実行する場合は、以下のファイルをテンプレートとして用いると良いでしょう。

// extern mod 文や use 文はここに書く

fn main() {
    // ここにコード本体を書く
}

コンパイルは以下のよう行います。なお、 Rust のソースコードの拡張子は ".rs" が使われています。

$ rustc ./foo.rs    # foo.rs をコンパイルする
$ ./foo             # コンパイルして生成されたバイナリ foo (windows なら foo.exe) を実行する

コンパイルと実行を同時に行ってくれるコマンド rust run も存在します。

$ rust run ./foo.rs # foo.rs をコンパイルし、実行する

Unix 系システムの場合は、以下のようにソースコードの先頭に shebang を書いて、ファイルに実行属性 (x) を与えれば、スクリプトのように実行することが可能です。

#!rust run

fn main() {
    println("Hello, World");
}

$ chmod +x foo.rs
$ ./foo.rs
Hello, World

`rusti` の使い方

rusti は REPL (対話的実行環境) なので、事前にソースコードのファイルを用意する必要はありません。以下の様に起動 & ソースコードの評価を行えます。

$ rusti
WARNING: The Rust REPL is experimental and may be
unstable. If you encounter problems, please use the
compiler instead. Type :help for help.
rusti> 1 + 2               # コードを入力
3                          # 評価結果が出力される
rusti> :exit               # rusti を終了する

複数行にわたるソースコードを入力する場合は、:{ と :} で囲みます。

rusti> :{
rusti| 1 +
rusti| 2 +
rusti| 3 +
rusti| 4
rusti| :}
10

rusti コマンド起動時のメッセージから分かるとおり、rusti は実験的・不安定な機能なため、rustc では正しく動作するはずのコードが動作しないなどの問題が発生する可能性があります。本記事のサンプルコードについては rusti でも動作確認を行っておりますが、何か問題が発生した場合は rustc を使ってコードを実行してみることをオススメします。

注意事項

本記事中のソースコードは、2013/7/3 にリリースされた rust 0.7 で動作確認しています。

$ rust -v
rust 0.7
host: x86_64-unknown-linux-gnu

rust は現在アルファ版のリリース過程にあり、言語仕様やライブラリへの破壊的変更が行われている真っ最中で、本記事に書かれた内容が将来に渡って通用しない可能性があります。 (0.6 リリース以降は、1.0 のリリースまで、言語仕様への大きな変更は行わない方針のようではありますが。。。)

本記事についても今後のリリースに併せて随時改訂していく予定ですが、問題が発生した場合はコメント欄等でご指摘いただけると大変助かります。また、筆者が把握している限りで今後仕様が変更されることが予想されるポイントについては、適宜注釈を入れておきます。

さて、前置きが長くなりました。次の節から rust の文法について説明します。

基礎

Rust のプログラムは、以下のような見た目をしています。

fn main() {
    let mut cond = false;
    loop {
        if cond {
            break;
        }
        cond = fun();
    }
}

if の後の括弧の有無、キーワードの違い等はありますが、Rust は、中括弧 {} を利用する、C 風の構文を採用しています。

コメントは、C 系列言語と同じです。 //, /* */ の代わりに ///, /** */ を利用すると、ドキュメントコメントとなります。

// 一行コメント
/* 複数
   行
   コメント
 */

端末への出力

プログラムから標準出力に文字列を出力するには、print 関数か println 関数を利用します。 print 関数は指定された文字列をそのまま出力しますが、println は末尾に改行を付与して出力します。

print("Hello World\n");
println("Hello World");

fmt! 構文拡張 (syntax extension) を利用することで、C の printf のようなフォーマット付き出力が利用できます。

println(fmt!("%d + %d = %d", 1, 2, 1+2)); //=> 1 + 2 = 3

fmt! で利用可能なフォーマット指定子は以下の通り。

println(fmt!("%d %i", 123, 456)); // %d, %i: 符号付き整数  => 123 456
println(fmt!("%u", 123));         // %u: 符号無し整数      => 123
println(fmt!("%s", "string"));    // %s: 文字列            => string
println(fmt!("%c", 'c'));         // %c: 文字              => c
println(fmt!("%b", true));        // %b: ブール型          => true
println(fmt!("%x", 127));         // %x: 16進整数 (小文字) => 7f
println(fmt!("%X", 127));         // %X: 16進整数 (大文字) => 7F
println(fmt!("%o", 10));          // %o: 8進整数           => 12
println(fmt!("%f", 1.23));        // %f: 浮動小数          => 1.23
println(fmt!("%?", ("asd", 123, true))); // %?: 任意の型 (ここではタプル型) => ("asd", 123, true)

%10d のように桁数を指定することも可能です。指定可能な内容については、 fmt! のテストセットに網羅的に書かれています。

fmt! は C の printf とは異なり、フォーマット文字と引数の不整合 (引数の数の不一致や、型の不一致) をコンパイル時にチェックしてくれます。素敵ですね！

fmt!("%d", "asdf");   // 型が不一致 (%d に対し、文字列)

<anon>:28:12: 28:18 error: mismatched types: expected `int` but found `&'static str` (expected int but found &'static str)
<anon>:28 fmt!("%d" , "asdf");
                      ^~~~~~
note: in expansion of fmt!
<anon>:28:0: 28:20 note: expansion site

fmt!("%d %d", 123); // 引数の数が不一致 (%d 2個に対し、引数1個)

<anon>:28:0: 28:20 error: not enough arguments to fmt! for the given format string
<anon>:28 fmt!("%d %d" , 123);
          ^~~~~~~~~~~~~~~~~~~~

なお、紙面 (?) の都合で、上記エラーメッセージは普通色の文字として記載していますが、実際はカラフルな表示 (error は赤, warning は黄, note は緑) となります。

変数の宣言

ローカル変数の宣言

関数内部で利用するローカル変数は、let で宣言します。

let foo: int = 123;

let で定義した変数は immutable (変更不可) です。値を変更しようとすると、コンパイルエラーとなります。

let foo: int = 123;
foo = 1;

<anon>:39:0: 39:3 error: re-assignment of immutable variable `foo`
<anon>:39 foo = 1;
          ^~~
<anon>:33:4: 33:7 note: prior assignment occurs here
<anon>:33 let foo: int = {
              ^~~

定義語に値を変更可能な変数を宣言するには、let mut を利用してください。

let mut bar: bool = true;  // mutable (変更可能) な変数を宣言
bar = false;

ローカル変数は型推論されるため、上記の例の型指定を省略することも可能です。

let foo = 123;
let bar = true;

`static` 変数の宣言

let は関数内部でのみ利用できます。複数の関数から利用可能な定数を宣言するには、static を使います。 letと違い、型推論はされません。

static foo: int = 123;

mutable な static 変数を定義することも可能です。グローバルで mutable な変数の利用は危険なので、利用する場合は危険な操作を行うことを示す unsafe ブロックで利用箇所を囲む必要があります。

static mut foo: int = 123;
// 利用する場合は unsafe 宣言が必要
unsafe {
    foo = 1;
}
let bar = unsafe { foo };
// 以下はエラー
foo = 1;

式とセミコロン

C と Rust の文法の大きな違いとして、C では「文」として扱われる構文の多くが、Rust では「式」として扱われることが挙げられます。条件に応じて適切な値を変数に設定したい場合、C を学んだ人が普通に書くと、以下のような書き方になると思います。

let price;
if weight > 100 {
    price = 10;
} else if weight > 50 {
    price = 5;
} else {
    price = 1;
}

Rust の if は「式」なので、以下のように書くことで price の繰り返しを避けることが可能です。

let price = if weight > 100 {
    10
} else if weight > 50 {
    5
} else {
    1
};

if だけでなく、ブロックも式として扱われます。ブロックの返す値は、ブロック内の最後の文の値です。

let foo = {
    let a = 1;
    let b = 2;
    a + b
}; // foo == 3

最後の式にはセミコロンがついていないことに注意してください。式の末尾にセミコロンを付けると、その式の値は無視され、() という特別な値が返却されます。

let a = { 123 };  // a == 123
let b = { 123; }; // b == ()

基本的な型

bool 型

真を表す true と、偽を表す false の2つの値のみをとれる型です。以下の演算が存在します。

true && false //=> false
true || false //=> true
!true         //=> false

C などと同じく、&&, || は短絡評価です。

数値

言語組み込みの数値型は「符号付き整数」、「符号なし整数」、「浮動小数」の3種類があります。それぞれの種類について、サイズが異なる型がいくつか存在します。

符号付き整数
- int: マシンのレジスタサイズと同じサイズ (32bit OS なら 32bit, 64bit OS なら 64bit)
- i8, i16, i32, i64: 型名の数値と同じサイズ (i8 なら 8bit)
符号なし整数
- uint: マシンのレジスタサイズと同じサイズ
- u8, u16, u32, u64: 型名の数値と同じサイズ
浮動小数
- float: f64 と同じ (0.7 時点。今後変更の可能性もある？)
- f32, f64: 型名の数値と同じサイズ

それぞれの数値型に対応したリテラルが存在します。

符号付き整数の場合
- int: 数値の末尾に i をつける (例: 12i)
- i8, i16, i32, i64: 数値の末尾に iXX をつける (例: 12i8, -12i32)
符号なし整数の場合
- uint: 数値の末尾に i をつける (例: 12u)
- u8, u16, u32, u64: 数値の末尾に uXX をつける (例: 12u8, 12u32)
浮動小数
- float: 数値の末尾に f をつける (例: 1.2f, 1f)
- f32, f64: 数値の末尾に fXX をつける (例: 1.2f32, -1f64)

i, i32, u64 等の型を表すサフィックスを省略した場合、当該リテラルの利用され方からどの型か自動的に推論されます。

let x: uint = 12;   // x は uint 型の 12
let y: float = 1.2; // y は float 型の 1.2

整数のリテラルが浮動小数として解釈されたり、浮動小数のリテラルが整数として解釈されることはありません。

let x: float = 12;  // エラー
let y: uint  = 1.2; // エラー

なお、ここで紹介した float 型は、将来無くなるかもしれません (Github の関連 Issue)

数値の演算

数値に関する演算です。

四則演算

1 + 2   //=> 3
1 - 2   //=> -1
1 * 2   //=> 2
1 / 2   //=> 0
5 % 2   //=> 1
-(5)    //=> -5

1.0 + 2.5 //=> 3.5
1.0 - 2.5 //=> -1.5
1.0 * 2.5 //=> 2.5
1.0 / 2.5 //=> 0.4
-(5.0)    //=> -5

比較演算子

1 >= 2 //=> false
1 > 2  //=> false
1 == 2 //=> false
1 != 2 //=> true
1 < 2  //=> true
1 <= 2 //=> true

ビット演算 (整数のみ)

3 << 2      //=> 12
16 >> 2     //=> 4
0xff & 0x01 //=> 1    (論理積)
0xff | 0x01 //=> 255  (論理和)
0xff ^ 0x01 //=> 254  (排他的論理和)
!(-100)     //=> 99   (ビット反転、C の ~)

代入演算子 (一部)

let mut a = 1; // a == 1
a += 3;        // a == 4
a *= 2;        // a == 8
a ^= 1;        // a == 9

インクリメント演算子 ++、デクリメント演算子 -- はありません。 += 1, -= 1 を使います。

異なる型との演算

2項演算子による演算は、同じ数値型同士の場合のみ行えます。異なる型同士の演算はエラーとなります。暗黙の型変換はありません。

1.2 + 1

<anon>:29:6: 29:7 error: mismatched types: expected `<VF0>` but found `<VI0>` (expected floating-point variable but found integral variable)
<anon>:29 1.2 + 1;
                ^

サイズの違う整数型/浮動小数型同士の演算もエラーです。

1u32 + 1u64

<anon>:29:7: 29:11 error: mismatched types: expected `u32` but found `u64` (expected u32 but found u64)
<anon>:29 1u32 + 1u64;
                 ^~~~

異なる型同士の演算を行う場合は、as を使って明示的にキャストしましょう。

let sum = 123.4;
let count = 10;
let avg = sum / (count as float);
println(fmt!("%f", avg)); //=> 12.34

Rust のメモリモデル

Rust には4種類のポインタ型 ~T, @T, &T, *T があります。

Owned box (`~T`)

Owned box は、ヒープ上に獲得された領域の事を指します。 Owned box は、 C++ の unique_ptr のように、単一の変数のみが所有権を持ちます。

let x = ~5;    // 5 をヒープ上に確保
let y = x;     // y に所有権が移る
// *y = 3;     // y は immutable なので、変更不可能
let mut z = y; // z に所有権が移る
*z = 3;        // z は mutable なので、変更可能
// *y + 3;     // y に格納されていた値は z に所有権が移っているため、y からはアクセスできない

Owned box として獲得された領域は、領域への参照が無くなった時点で解放されます。この解放タイミングは、ソースコードから静的に解析可能で、ガベージコレクタは必要ありません。

Managed box (`@T`)

Managed box は、ヒープ上に獲得された領域の事を指します。 Managed box は、C++ の shared_ptr のように、複数の変数から同一の領域を指すことが可能です。

let x = @5;   // 5 をヒープ上に確保
let y = x;    // x と y は同じ領域を指す

Managed box として獲得された領域は、領域への参照が無くなった時点で解放されます。この開放処理は、ガベージコレクタにより行われます。

Borrowed pointer (`&T`)

Borrowed pointer は、C++ の参照型のようなもので、任意の値を参照するために用いることができます。また、指し示した値が無効にならないことを、コンパイラが静的に保証します。

let ptr; // uint 型の borrowed pointer を宣言
{
    let x = 1;  // ブロック内でのみ有効な変数 x の宣言
    ptr = &x;   // x を指す borrowed pointer を ptr に代入
}
println(fmt!("%?", ptr)); // ブロックの外で x の値を参照

<anon>:35:19: 35:21 error: borrowed value does not live long enough
<anon>:35 { let x = 1; ptr = &x; println(fmt!("%?" , ptr)); }
                             ^~
<anon>:25:22: 1:0 note: borrowed pointer must be valid for the block at 25:22...
<anon>:35:0: 35:51 note: ...but borrowed value is only valid for the block at 35:0
<anon>:35 { let x = 1; ptr = &x; println(fmt!("%?" , ptr)); }
          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

上記プログラムは、ブロック内でのみ有効な変数 x を、ブロックを抜けた時点で参照しようとしています。 Rust コンパイラは、このような不正なメモリアクセスを検知し、エラーとしてくれます。

ヒープの種類

Rust には exchange heap と、 local heap という2種類のヒープが用意されています。 exchange heap 上の値は複数のタスク (スレッドのようなもの) から同時にアクセス可能ですが、 local heap 上の値は単一タスクからしかアクセスできません (タスク毎に固有の local heap があります)。

owned box は exchange heap 上に獲得され、managed box は local heap 上に獲得されます。すなわち、タスク間でデータをやりとりする場合は、必ず owned box にしなければなりません。この仕様により、以下が実現できます。

複数のタスクが同時に同一のメモリ領域にアクセスしない (タスク毎のメモリ領域を完全に分離)
タスク間でデータを受け渡す際に、データ全体をコピーしなくて良い (Owned box のポインタの値を渡すだけで良い)

文字列と配列

文字列・文字

Rust の文字列型は、どの領域に値を格納するかに応じて、&str (スタック上に確保), ~str (Exchange heap 上に確保), @str (local heap 上に確保) の3種類があります。それぞれの違いについては、後の節で説明します。

文字型は char です。

文字列リテラル、文字リテラルは以下の様に書きます。

let a = ~"string"; // ~str 型の文字列
let b = @"string"; // @str 型の文字列
let c = "string";  // &str 型の文字列
let d = 'c';       // 文字 (char 型)

エスケープシーケンスも使えます。

let new_line = "aaa\nbbb";

文字列の操作

各種文字列操作です

結合

"aaa" + "bbb"                       // => "aaabbb"
["aaa", "bbb", "ccc"].connect(",")  // => "aaa,bbb,ccc"
["aaa", "bbb", "ccc"].concat()      // => "aaabbbccc"

分割

文字列分割関数は、他の言語のように配列を返すのでは無く、イテレータを返します。余計なメモリ獲得を極力避けるという、 Rust の効率性に対する意気込みが感じられます。

let mut iter = "aaa,bbb,ccc".split_iter(',')  //=> イテレータ
iter.collect::<~[&str]>                       //=> ~["aaa", "bbb", "ccc"] イテレータから配列を作成

let mut iter = "aaa<>bbb<>ccc".split_str_iter("<>")  //=> イテレータ
iter.collect::<~[&str]>                              //=> ~["aaa", "bbb", "ccc"] イテレータから配列を作成

長さ

"aaa".len()         //=> 3
"日本語".len()      //=> 9 (バイト数)
"日本語".char_len() //=> 3 (文字数)

切り出し

"abcd".slice(0, 2)         //=> "ab"
"日本語".slice_chars(0, 2) //=> "日本"

検索

// 文字列の見つかった範囲のイテレータを返す
"abcd efdh abcd".matches_index_iter("cd").collect::<~[(uint, uint)]>() //=> ~[(2, 4), (12, 14)]

// 最初に見つかった文字の位置を返す
"abcd abcd".find('b') //=> Some(2)
"abcd abcd".find('x') //=> None

// 最後に見つかった文字の位置を返す
"abcd abcd".rfind('b') //=> Some(6)
"abcd abcd".rfind('x') //=> None

// 最初に見つかった文字列の位置を返す
"abcd abcd".find_str("cd") //=> Some(2)
"abcd abcd".find_str("xx") //=> None

配列 (Vector)

Rust の配列型は、可変長の配列と固定長の配列の2種類があります。可変長の配列は、要素の型を T とすると、&[T], ~[T], @[T] の3種類に更に分類されます。 int の配列は &[int] や ~[int], @[int] などと書きます。

固定長の配列は、 [T, ..　N] と書かれます。N は要素数です。要素数3の int の配列は [int, ..　3] と書きます。

let a = ~[1, 2, 3];         // ~[int] 型
let b = @["a", "b", "c"];   // @[&str] 型
let c = &[1.0, 2.0, 3.0];   // &[float] 型
let d = [1, 2, 3];          // [int, .. 3] 型

配列に異なる型の要素を混ぜることはできません。複数の型を混ぜたい場合は、後述のタプルを使います。

[1i32, 1.0f, "aaa"]

<anon>:29:7: 29:11 error: mismatched types: expected `i32` but found `float` (expected i32 but found float)
<anon>:29 [1i32, 1.0f, "aaa"];
                 ^~~~
<anon>:29:13: 29:18 error: mismatched types: expected `i32` but found `&'static str` (expected i32 but found &'static str)
<anon>:29 [1i32, 1.0f, "aaa"];
                       ^~~~~

配列の操作

各種配列操作です

配列の生成方法

use std::vec;

// 要素数関数から生成
vec::from_fn(4, |i| i + 1) //=> ~[1, 2, 3, 4]

// 要素数と要素から生成
vec::from_elem(4, "123") //=> ~["123", "123", "123", "123"]

配列の参照と代入

let mut v = ~[1, 2, 3];
let n = v[2];   // n == 3 (配列の添え字は 0 から始まる)
v[0] = 3;       // v == ~[3, 2, 3]

要素の個数

~[1, 2, 3].len() //=> 3

先頭の要素を取り出す

let mut v = ~[1, 2, 3];
v.shift();          //=> 1, v == ~[2, 3]

先頭に要素を追加

let mut v = ~[1, 2, 3];
v.unshift(4);        // v == ~[4, 1, 2, 3]

末尾の要素を取り出す

let mut v = ~[1, 2, 3];
v.pop()             //=> 3, v == ~[1, 2]

末尾に要素を追加

let mut v = ~[1, 2, 3];
v.push(4);          // v == ~[1, 2, 3, 4]

配列の一部への参照 (slice) を得る

let v = ~[1, 2, 3, 4];
let s = v.slice(1, 3);        // s == &[2, 3]
s.len()                       //=> 2

let mut v = ~[1, 2, 3, 4];
let mut s = v.mut_slice(1, 3);    // s == &mut [2, 3]
s[0] = 5;                         //=> v == ~[1, 5, 3, 4]

マップ

他の言語ではハッシュや連想配列と呼ばれるものです。 Rust のマップ型は言語組み込みではなく、標準ライブラリで定義されているものです。

マップ

キーと値のペアです。型は HashMap<K, V> です。 K はキーの型、 V は値の型です。

マップの生成

new という名前の静的メソッドを呼び出します (静的メソッドについては、後で説明します)。

use std::hashmap::HashMap;
let mut map = HashMap::new::<uint, ~str>(); // キーが uint, 値が ~str のマップ

値の設定

map.insert(0, ~"zero");
map.insert(1, ~"one");

値の参照

map.find(&0)  //=> Some(&~"zero")
map.find(&1)  //=> Some(&~"one")
map.find(&10) //=> None

map.get(&0)  //=> &~"zero"
map.get(&10) // 異常終了

キーの存在確認

map.contains_key(&0)  //=> true
map.contains_key(&10) //=> true

キーの削除

map.remove(&0)  //=> true (要素を存在する場合 true が返る)
map.remove(&10) //=> false

制御構文

条件分岐

既に何度か登場していますが、条件分岐には if 文を用います。 cond の部分には真偽値 (bool 型の値) をもつ式を書きます。 C と違い、int 型等の数値を真偽値として利用することはできません。また、C 等では if の後に括弧 ( ) が必要ですが、Rust では不要です。

if cond {
  foo();
}

if cond {
    foo();
} else {
    bar();
}

if cond1 {
    foo();
} else if cond2 {
    bar();
} else {
    baz();
}

パターンマッチ

Rust の match 構文は、C の switch 文を拡張したものであると言えます。 C の switch では、case の後に定数しか書けませんが、Rust では「パターン」を書くことができ、より一般的な条件分岐が可能です。

match number {
    0     => println("zero"),              // 0 の場合
    1 | 2 => println("one or two"),        // 1 または 2 の場合 ("|" は、いずれかにマッチすることを表す)
    3..10 => println("three to ten"),      // 3 以上10以下の場合 (".." は、範囲を表す)
    _     => println("something else")     // 上記以外の場合 ("_" は、任意の値にマッチする)
}

各 => の左側に書かれているものが「パターン」です。 match 構文では、渡された値 (上記の例では number) が「パターン」に当てはまるかどうか順番にチェックしていき、最初に当てはまったものに対応する式 (=> の右側に書かれているもの) が実行されます。

C の switch とは異なり、"fall through" ではありません。

=> の後にはブロックを書くこともできます。この場合、各式の末尾の , は省略することができます。

match number {
    0     => { println("zero") }
    1 | 2 => { println("one or two") }
    3..10 => { println("three to ten") }
    _     => { println("something else") }
}

パターンの網羅性

パターンは、すべての有り得る値を網羅するように書かなければなりません。以下のように、一部の数値に対応するパターンが存在しない match を書いた場合、コンパイルエラーとなります。

let n: uint = fun(); // n は uint 型
match n {
    0 => "zero",
    1 => "one" // 2 以上の値に対応するパターンなし
}

<anon>:43:0: 43:35 error: non-exhaustive patterns
<anon>:43 match n { 0 => "zero", 1 => "one" }
          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

この仕様により、特定の値に対する処理のみが漏れてしまうことを防ぐことができます。

条件付きパターンマッチ

パターンには、条件を付与することが可能です。例えば、正の数、負の数、0でそれぞれ処理を変えたい場合、以下のように int の数値の範囲を明に書くことでも実現可能ですが、

let s = match n {
    0                      => "zero",
    1..9223372036854775807 => "positive",
    _                      => "negative"
};

パターンの後に if を使って条件を付与する方法で書いた方が直感的に分かりやすいと思います。 (この例だと、match ではなく、素直に if 式を使って書いた方が良い気もしますが。)

let s = match n {
    0          => "zero",
    _ if n > 0 => "positive",
    _          => "negative"
};

このパターンマッチ機能ですが、後で説明する「複合型」と組み合わせることでその真価を発揮します。詳しくは、「複合型」の項で説明します。

ループ

`while`

C の while 文と同等です。

let mut i = 100;
while i > 0 {
    i -= 1;
}

C の break は break, continue は loop です。

let mut i = 0;
while i < 100 {
  i += 1;
  if f(i) == 0 { loop; }
  if g(i) > 0 { break; }
}

`loop`

無限ループです。while true {} と同じですが、専用の構文が用意されています。

let mut x = 5;
loop {
    x += x - 3;
    if x % 5 == 0 { break; }
    println(fmt!("%d", x));
}

`for`

配列等の要素をイテレーションするものです。将来的に意味 (構文) が変化しそうなので、ここでは見た目の紹介に留めておきます。

rust 0.6 の `for`

for は、内部イテレータを呼び出すための構文です。

let v = ~[1, 2, 3];
for v.each |x| {  // 内部イテレータ each() の呼出し
    println(fmt!("%d", *x));
}

rust 0.7 の `for`

for 自体は 0.6 の頃から変わっていませんが、ライブラリ側が内部イテレータから外部イテレータへと移行しているため、 for を利用するためには内部イテレータへの変換が必要です。

let v = ~[1, 2, 3];
// iter() で作成した外部イテレータを、 advance() で内部イテレータに変換
for v.iter().advance |x| {
    println(fmt!("%d", *x));
}

(近い？)将来のバージョン

for が外部イテレータをサポートするようになり、内部イテレータは廃止されます。

// 外部イテレータを直接呼出し。Iterable な型の場合、 iter() の呼出しを省略できる。
for ~[1,2,3] |x| {
    println(fmt!("%d", *x));
}

[2013/9/22 追記] rust 0.8 以降の for は以下の構文となっています。

for x in ~[1, 2, 3].iter() {
    println(fmt!("%d", *x));
}

新しい for 構文は、クロージャではなく単純なループのシンタックスシュガーなので、クロージャを意識させる以前の構文とは全く異なったものになっています。なお、Iterable な型については、0.8 時点ではサポートされず、明示的に iter() を書いてイテレータを取得する必要があります。

複合型

タプル

配列と同じようにいくつかの値をまとめて一つの型として扱えるようにするものです。配列と異なり、要素数は固定ですが、異なる型の値を一つのタプルに含むことができます。

let a = (1, "foo", true);   // (int, &str, bool) 型
let b = (1, "bar", a);      // (int, &str, (int, &str, bool)) 型

n0, n1 などのメソッドで、n 番目の値を得ることができます。

let tuple = (123, "a", true);
tuple.n0() // 123
tuple.n1() // "a"
tuple.n2() // true

構造体 (struct)

C の構造体とほぼ同じです。

// Point 構造体の定義
struct Point {
    x: float,
    y: float
}

// Point 型の値を定義
let pt = Point { x: 1.0, y: 1.0 };

型引数をとる構造体を定義することも可能です。見た目は C++ の template と似ています。

struct Stack<T> {
  elements: ~[T]
}

列挙型 (enum)

名前こそ C の enum と同じですが、どちらかというと union の方が近いです、関数型言語に親しんでいる方には、「代数的データ型」と言えば、ピンと来ると思います。

列挙型は、複数種類の値をもつ型です。例えば、以下の Shape 型は、 Circle と Rectangle という 2 種類の値をもちます。

enum Shape {
    Circle(Point, float),     // 中心の座標 + 半径
    Rectangle(Point, Point)   // 左上の座標 + 右上の座標
};

Circle と Rectangle は同じ Shape 型の値なので、ひとつの配列に格納することができます。

let shapes = ~[Circle(pt, 1.0), Rectangle(pt1, pt2)]; // Circle と

もちろん、C の enum のような使い方もできます。

enum Direction {
    North,
    East,
    South,
    West
}
enum Color {
  Red   = 0xff0000,
  Green = 0x00ff00,
  Blue  = 0x0000ff
}

構造体と同様、型引数をとる列挙型を定義することもできます。 Rust のあらゆるところで使われている Option<T> 型 (Haskell の Maybe a 型のようなもの) は、以下のように定義されています。

enum Option<T> {
  Some(T),
  None
}

複合型とパターンマッチ

パターンマッチには、複合型を扱う上で非常に役に立つ分割 (destructuring) 機能、および変数の束縛機能があります。例えば、2 次元のタプルを座標と見なして、原点からの角度を取得する関数 angle は、以下のように定義することができます。

fn angle(vector: (float, float)) -> float {
    use std::float::consts::pi;
    match vector {
      (0f, y) if y < 0f => 1.5 * pi,
      (0f, y)           => 0.5 * pi,
      (x,  y)           => float::atan(y / x)
    }
}

パターン中に登場する変数名 (上記では x, y) は、_ と同様、任意の値にマッチし、対応した値が束縛されます。例えば、(x, y) というパターンがあった場合、x にはタプルの1番目の要素の値が、y には2番目の要素の値が束縛されます。

また、値を分割して束縛する機能は、 let で変数宣言する際にも利用可能です。

let (a, b) = (123, 456);               // パターンマッチでタプル型の値から変数 a, b を生成
println(fmt!("a = %d, b = %d", a, b)); //=> a = 123, b = 456

構造体のパターンマッチ

構造体のパターンマッチは以下のように書けます。

struct Point { x: float, y: float };

fn print_point(point: Point) {
    match point {
      Point { x: 0f, y: yy } => { println(fmt!("%f", yy)); }
      Point { x: xx, y: yy } => { println(fmt!("%f %f", xx, yy)); }
    }
}

構造体のフィールド名と同じ名前の変数に値を束縛する場合、以下のように変数名を省略して書くことが可能です。

fn print_point(point: Point) {
    match point {
      Point { x: 0f, y } => { println(fmt!("%f", y)); }
      Point { x,     y } => { println(fmt!("%f %f", x, y)); }
    }
}

列挙型のパターンマッチ

列挙型のパターンマッチは以下のように書けます。

struct Point { x: float, y: float }
enum Shape {
    Circle(Point, float),
    Rectangle(Point, Point)
}

fn area(sh: Shape) -> float {
    use std::float::consts::pi;
    match sh {
        Circle(_, size) => pi * size * size,
        Rectangle(Point {x, y}, Point {x: x2, y: y2}) => (x2 - x) * (y2 - y)
    }
}

関数

関数は fn で定義します。2つの int 型引数をとり、戻り値として int 型の値を返す関数は以下のように書けます。

fn sum(a: int, b: int) -> int {
    return a + b;
}

ブロックの最後の return は省略可能なので、以下のようにも書けます (末尾のセミコロンが省略されていることに注意)。

fn sum(a: int, b: int) -> int {
    a + b
}

Rust では return を省略するスタイルが推奨されています。

また、戻り値が () の場合は、以下のように戻り値型の指定を省略することもできます。

fn void_function() -> () { return (); }

fn void_function2() { }

引数として任意の型をとることのできる、ジェネリックな型は以下のように書くことができます。

fn fun<T, U>(a: T, b: U) {
    // 中身は省略
}

クロージャ

クロージャを使ったコードの例です。

let mut n = 1;
let plus_n = |x| n + x; // クロージャ。x が引数

plus_n(3); //=> 4

n = 3;
plus_n(3); //=> 6

// 型を明記する場合
let plus_n_2 = |x: int| -> int n + x;

// 複数の文からなるクロージャ
let plus_n_3 = |x| {
  println(fmt!("%d", x));
  x + 3
};

`do` 記法

do 記法を用いる事で、Ruby のブロック構文のようなことが可能になります。

fn each(v: &[int], op: &fn(v: &int)) {
    let mut i = 0;
    while i < v.len() {
        op(&v[i]);
        i += 1;
    }
}

// 普通に呼び出す場合
each([1, 2, 3], |n| {
    println(fmt!("%d", *n));
});

// do 記法を用いる場合
do each([1, 2, 3]) |n| {
    println(fmt!("%d", *n));
}

`trait` / `impl`

Rust は、trait と impl という仕組みでオブジェクト指向を実現しています。クラスベースやプロトタイプベースのオブジェクト指向よりも、Haskell の型クラスに近い考え方になっています。

// 表示可能であることを示す trait
trait Print {
    fn print(&self);
}

// int 型に Print を実装
impl Print for int {
    fn print(&self) { println(fmt!("%d", *self)); }
}

// ~str 型に Print を実装
impl Print for ~str {
    fn print(&self) { println(*self); }
}

以下のようにして使います。

123.print();      // int 型の print メソッドを呼び出す
(~"123").print(); // ~str 型 の print メソッドを呼び出す

(~[1, 2, 3]).print(); // ~[int] 型は print を実装していない

<anon>:38:0: 38:21 error: type `~[<VI2>]` does not implement any method in scope named `print`
<anon>:38 (~[1, 2, 3]).print();
          ^~~~~~~~~~~~~~~~~~~~~

静的なメソッドを定義することも可能です。 self 引数がないメソッドは静的なメソッドとなります。

trait Shape { fn new(area: float) -> Self; }
struct Circle { radius: float }
struct Square { length: float }

impl Shape for Circle {
    fn new(area: float) -> Circle { Circle { radius: sqrt(area / pi) } }
}
impl Shape for Square {
    fn new(area: float) -> Square { Square { length: sqrt(area) } }
}

let area = 42.5;
let c: Circle = Shape::new(area);
let s: Square = Shape::new(area);

参考文献・関連サイトまとめ

日本語文献は少ないです。。。

言語の背景や経緯の紹介

Rust 公式サイト (英語)
Rust - Wikipedia (日本語) ちょっと情報が古いですが、言語の概要が簡潔にまとまっています
Rust - Mozilla の開発したシステムプログラミング言語 - に関するインタビュー - Graydon Hoare さんへのインタビュー

言語仕様について

公式のチュートリアル
Rust 公式チュートリアルの非公式日本語訳 (rust 0.4 ベースなので、少し内容が古いです)
Rust: A Friendly Introduction Rust の開発者 Tim Chevalier によるプレゼンテーション
Rust for CXX programmers C++ プログラマ向けの紹介

2013-07-15

デザインのテスト

見出しのデザインを考えるためのテスト記事です。

最高レベルの見出し

本文

2 番目のレベルの見出し

本文

3 番目のレベルの見出し

本文

4 番目のレベルの見出し

本文

5 番目のレベルの見出し

本文

2013-07-06

はてなブログに移転しました

はてなブログに記事をインポート＆はてなダイアリーからのリダイレクト設定をしました。さんざん放置してたダイアリーの移転なので、特にこれといって変化はないでしょうが、今後はちょくちょく記事書いて日常のあれやこれやを記録に残せたらなあ、と思います。

適当に頑張ります。

2012-10-06

rust-incoming-git の PKGBUILD

Rust

rust の最新の変更の commit 先が master ブランチから incoming ブランチに変更されたため、 master ブランチの動きが少なくなってしまい寂しかったので、 incoming ブランチ用の PKGBUILD を作成しました。ついでに、AUR にアップしておきました。

AUR (en) - Page Not Found

正確には、この PKGBUILD 自体は半月前くらいに作成したものなのですが、以下のコミットの影響で正しくインストールできなくなってしまったので、それの修正がてら、ついでにAURに投稿したという経緯です。

Use both DESTDIR and prefix · 27a984e · mozilla/rust · GitHub

コンパイルに clang 使うオプション有効にしたまま投稿してしまったので、依存パッケージとか全然足りてない気がするけど、それはそれで、まあ、良いと言うことで。。。気が向いたら、というか指摘されたら直します。。。

2012-05-28

rust-git の PKGBUILD

Arch Linux Rust

AUR にある rust-git が、makepkg しようとすると毎回 llvm やら libuv のサブモジュールを clone しようとして時間がかかって仕方が無いので、初回だけ clone するように修正してみた。ついでに、コンパイラとして clang を使う設定もいれてみた。
既にある物の改造版を AUR にアップして良い物かわからないので、ここに貼り付けておきます。

# Author: NAKASHIMA, Makoto <makoto.nksm@gmail.com>

pkgname=rust-git
pkgver=20120528
pkgrel=1
pkgdesc="A safe, concurrent, practical language from Mozilla."
arch=(i686 x86_64)
url="http://www.rust-lang.org/"
license=('MIT')
depends=('gcc-libs')
makedepends=('git' 'gcc'
             'libffi' 'python2'  # for LLVM
            )
optdepends=('pandoc: to build rust.pdf'
            'llnextgen: for build-time grammar verification'
            'naturaldocs: to build library doc')

_gitroot="git://github.com/mozilla/rust.git"
_gitname="rust"

build() {
  cd "$srcdir"
  msg "Connecting to git server...."

  if [ -d $_gitname ] ; then
    cd $_gitname && git pull origin
    git submodule sync
    git submodule update --init --recursive
    git submodule foreach --recursive git clean -dxf
    git submodule foreach --recursive git checkout .
    msg "The local files are updated."
  else
    git clone --recursive $_gitroot $_gitname
    cd $_gitname
  fi

  msg "git checkout done or server timeout"

  rm -rf "$srcdir/$_gitname-build"
  cp -r "$srcdir/$_gitname" "$srcdir/$_gitname-build"
  cd "$srcdir/$_gitname-build"

  ./configure --prefix=/usr --enable-clang
  msg 's/python$/python2/'
  find . \
    -type f -executable -exec grep -qe 'env python$' '{}' ';' \
    -exec sed -i 's/env python$/env python2/' '{}' ';' -print

  msg "Starting make..."
  make || return 1
}

package() {
  mkdir "$pkgdir/usr"
  cd "$srcdir/$_gitname-build"
  make install DESTDIR="$pkgdir/usr/"

  _docdir=$pkgdir/usr/share/doc/rust
  mkdir -p "$_docdir"
  for _doc in rust.pdf rust.html tutorial.html rust.css core std rust.md ; do
    if ! [ -e "doc/$_doc" ] ; then continue ; fi
    cp -r "doc/$_doc" "$_docdir/"
    chmod -R 644 "$_docdir/$_doc"
    chown -R root:root "$_docdir/$_doc"
  done
  find "$_docdir" -type d -exec chmod 755 '{}' ';'
}

2012-03-04

Rust で ProjectEuler #8 ~ #12

Rust Project Euler

Problem 8

入力された数列に含まれる5つの連続した数の積のうち、最大のものを求める問題。

最新版ソース

use std;

fn main() {
    const prod_len: uint = 5u;
    let input = "
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
";
    let nums = vec::filter_map(str::chars(input)) { |c| uint::from_str(str::from_char(c)) };
    if (vec::len(nums) < prod_len) {
        fail;
    }

    let max = 0u;
    uint::range(0u, vec::len(nums) - prod_len) { |i|
        let prod = 1u;
        uint::range(0u, prod_len) { |j|
            prod *= nums[i + j];
        }
        max = uint::max(prod, max);
    }

    std::io::println(#fmt("%u", max));
}

まず、str::charsで文字列をcharの配列にして、それに対してvec::filter_mapを呼び出すことで、uint 型の数値の配列に変換しています。vec::filter_mapは配列の各要素に対して、第2引数の関数を呼び出します。関数の戻り値はoption型で、値がsome(x)を返した要素のみからなる新たな配列を生成します。これで改行文字列等を除去した数値のみの配列が得られます。
その後の積の最大値を求める処理は単純です。(0u, 4u) ~ (vec::len(nums) - 5u, vec::len(nums) - 1u)の範囲についてそれぞれ積を求めて、それらの最大値を求めています。対象とする数が十分少ないので、このような単純な方法で十分高速に解を求められます。

Problem 9

和が1000になるピタゴラス数を求める。

最新版ソース

use std;

fn isqrt(n: u64) -> u64 {
    let (min, max) = (0u64, n);
    while min < max {
        let mid = (min + max + 1u64) / 2u64;
        if (mid * mid) == n {
            ret mid;
        } else if (mid * mid) >= n {
            max = mid - 1u64;
        } else {
            min = mid;
        }
    }
    ret min;
}

fn find_pyrhagorean(sum: u64) -> [(u64, u64, u64)] {
    let answer = [];
    uint::range(2u64, sum - 2u) { |c|
        uint::range(1u64, uint::min((sum - c) / 2u, isqrt(c*c / 2u))) { |a|
            let b = sum - c - a;
            if a * a + b * b == c * c {
                answer += [(a, b, c)];
            }
        }
    }
    ret answer;
}

fn main() {
    for (a, b, c) in find_pyrhagorean(1000u) {
        std::io::println(#fmt("%u^2 + %u^2 = %u^2", a, b, c));
        std::io::println(#fmt("prod: %u", a * b * c));
    }
}

愚直な作りです。 $a^2 + b^2 = c^2$ , $a+b+c=1000$ なので、まず $b=1000-a-b$ とおき、 $c\in[2,1000-2$ ], $a\in[1,\mathrm{min}((1000-c)/2,\sqrt{c^2/2})$ ]の範囲で動かして、条件を満たすかどうか確かめています。

Problem 10

200万以下の素数の和を求める

最新版ソース

use std;

fn gen_prime(&primes: [u64]) {
    let num = alt vec::last(primes) {
      none       { primes =  [2u64]; ret }
      some(2u64) { primes += [3u64]; ret }
      some(x)    { x + 2u64 }
    };

    while true {
        for p in primes {
            if p * p > num {
                primes += [num];
                ret;
            }
            if num % p == 0u64 {
                break;
            }
        }
        num += 2u64;
    }
    fail;
}

fn main() {
    let sum = 0u;

    let primes = [];
    while true {
        gen_prime(primes);
        let p = vec::last_total(primes);
        if p >= 2000000u64 {
            break;
        }
        sum += p;
    }

    std::io::println(#fmt("%u", sum));
}

200万以下の素数を作って、足しているだけです。

Problem 11

行列の中から、縦、横、対角方向で連続する4つの数の積のうち最大の物を求める

最新版ソース

use std;

fn find_max_row(row: [uint], prod_len: uint) -> uint {
    if vec::len(row) < prod_len {
        ret 0u;
    }
    let max = 0u;
    uint::range(0u, vec::len(row) - prod_len) { |i|
        let prod = 1u;
        uint::range(0u, prod_len) { |j|
            prod *= row[i + j];
        }
        max = uint::max(max, prod);
    }
    ret max;
}

fn find_max_grid(grid: [[uint]], prod_len: uint) -> uint {
    vec::foldl(0u, grid) { |max, row|
        uint::max(max, find_max_row(row, prod_len))
    }
}

fn find_max_v(grid: [[uint]], prod_len: uint) -> uint {
    if vec::is_empty(grid) {
        ret 0u;
    }

    let max = 0u;
    uint::range(0u, vec::len(grid[0])) { |i|
        max = uint::max(max, find_max_row(vec::map(grid) { |row| row[i] }, prod_len));
    }
    ret max;
}

fn find_max_d(grid: [[uint]], prod_len: uint) -> uint {
    if vec::is_empty(grid) {
        ret 0u;
    }
    let num_row = vec::len(grid);
    let num_col = vec::len(grid[0]);
    let max = 0u;
    int::range(-(num_row as int) + 1, num_col as int) { |i|
        let tl_br = vec::filter_map(vec::enum_uints(0u, uint::min(num_row, num_col) - 1u)) { |d|
            let (x, y) = (i + (d as int), d);
            if x < 0 || x as uint >= num_col || y >= num_row {
                ret none;
            }
            ret some(grid[y][x]);
        };
        max = uint::max(max, find_max_row(tl_br, prod_len));

        let bl_tr = vec::filter_map(vec::enum_uints(0u, uint::min(num_row, num_col) - 1u)) { |d|
            let (x, y) = (d, (num_col as int - 1 - i) - (d as int));
            if x >= num_col || y < 0 || y as uint >= num_row {
                ret none;
            }
            ret some(grid[y][x]);
        };
        max = uint::max(max, find_max_row(bl_tr, prod_len));
    }
    ret max;
}

fn main() {
    let input = "
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
";

    let grid = vec::map(str::lines(str::trim(input))) { |row|
        vec::map(str::split_char(row, ' ')) { |cell|
            alt uint::from_str(cell) {
              some(x) { x }
              none    { fail }
            }
        }
    };
    let max = find_max_grid(grid, 4u);
    max = uint::max(max, find_max_v(grid, 4u));
    max = uint::max(max, find_max_d(grid, 4u));
    std::io::println(#fmt("%u", max));
}

find_max_row関数で1次元配列中の隣接するn要素のうち、最大の積をもつものを求めています。行方向の配列、列方向の配列、対角方向の配列をそれぞれ作ってやって、find_max_row関数に渡してやることで、これらすべての方向に隣接する数値の積の最大値を求めることができます。

Problem 12

三角数のうち、最初に約数の数が500を越える物を求める。

最新版ソース

use std;

fn gen_triangles(&trigs: [uint]) {
    alt vec::len(trigs) {
      0u { trigs = [1u]; }
      x  { trigs += [trigs[x - 1u] + x + 1u]; }
    }
}

fn gen_prime(&primes: [u64]) {
    let num = alt vec::last(primes) {
      none       { primes =  [2u64]; ret }
      some(2u64) { primes += [3u64]; ret }
      some(x)    { x + 2u64 }
    };

    while true {
        for p in primes {
            if p * p > num {
                primes += [num];
                ret;
            }
            if num % p == 0u64 {
                break;
            }
        }
        num += 2u64;
    }
    fail;
}

fn div_mult(&num: u64, f: u64) -> u64 {
    let exp = 0u64;
    while (num % f == 0u64) {
        exp += 1u64;
        num /= f;
    }
    ret exp;
}

fn factorize(num: u64, &primes: [u64]) -> [(u64, u64)] {
    let itr = num;
    let result = [];

    for p in primes {
        let exp = div_mult(itr, p);
        if exp > 0u64 {
            result += [(p, exp)];
        }
    }

    while itr != 1u64 {
        gen_prime(primes);
        let p = vec::last_total(primes);
        let exp = div_mult(itr, p);
        if exp > 0u64 {
            result += [(p, exp)];
        }
    }

    ret result;
}

fn num_factors(num: u64, &primes: [u64]) -> u64 {
    let facts = factorize(num, primes);
    ret vec::foldl(1u, facts) { |prod, tuple|
        let (_base, exp) = tuple;
        prod * (exp + 1u)
    };
}

fn main() {
    let trigs  = [];
    let primes = [];
    while true {
        gen_triangles(trigs);
        let t = vec::last_total(trigs);
        let num = num_factors(t, primes);
        if num > 500u {
            std::io::println(#fmt("%u -> %u", t, num_factors(t, primes)));
            break;
        }
    }
}

三角数の配列を作り、それを素因数分解して、各素因数の指数から約数の数を求めています。愚直。

2012-02-25

Rust で ProjectEuler #4 ~ #7