一般的なプログラミング言語の場合、関数を呼び出す前に引数が評価され、その結果が関数に渡されます。これを「正格 (strict) な評価」といいます。これに対し、引数や変数の値が必要になるまで評価を行わない方法もあります。具体的には、引数や引数を参照するときに評価が行われます。これを「遅延評価 (delayed evaluation または lazy evaluation)」といいます。
プログラミング言語では関数型言語の Haskell が遅延評価です。F# は「lazy 式 (遅延式)」を使って式を遅延評価することができます。そして、その評価結果は保存されることに注意してください。再度変数や引数を参照すると、保存されている値が返されます。今回は F# の遅延評価について簡単に説明します。
lazy 式の構文を示します。
lazy expression => 遅延オブジェクト
lazy 式は式 expression を評価しないで、クラス Lazy<'T> のインスタンスを返します。本稿では、Lazy<'T> のインスタンスを「遅延オブジェクト」と呼ぶことにします。評価はメソッド Force() で行います。このとき、評価結果が遅延オブジェクトに保存されることに注意してください。再度 Force() を評価すると、保存された値が返されます。
簡単な使用例を示します。
> let a = lazy (printfn "oops"; 2 + 3);; val a: Lazy<int> = Value is not created. > a.Force();; oops val it: int = 5 > a.Force();; val it: int = 5
遅延オブジェクトを変数 a にセットします。このとき、引数の式はまだ評価されていません。a.Force() を評価すると、lazy 式に渡された式が評価されるので、画面に oops が表示されて計算結果の 30 が返されます。a.Force() を再度評価すると、同じ式を再評価しないで遅延オブジェクトに保存された値を返します。この場合 oops は表示されません。
遅延評価の簡単な例題として「たらいまわし関数」を取り上げます。次のリストを見てください。
リスト : たらいまわし関数 let rec tarai x y z = if x <= y then y else tarai (tarai (x - 1) y z) (tarai (y - 1) z x) (tarai (z - 1) x y) let rec tak x y z = if x <= y then z else tak (tak (x - 1) y z) (tak (y - 1) z x) (tak (z - 1) x y)
関数 tarai(), tak() は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。Common Lisp のプログラムは ぬえ 鵺 NUE の TAK Function にあります。
tarai() は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。tak() は tarai() のバリエーションで、John Macarthy 先生によって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。
それでは、さっそく実行してみましょう。実行環境は Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz です。
> let rec tarai x y z = - if x <= y then y - else tarai (tarai (x - 1) y z) (tarai (y - 1) z x) (tarai (z - 1) x y);; val tarai: x: int -> y: int -> z: int -> int > let rec tak x y z = - if x <= y then z - else tak (tak (x - 1) y z) (tak (y - 1) z x) (tak (z - 1) x y);; val tak: x: int -> y: int -> z: int -> int > #time;; --> 今すぐタイミング オン > tarai 14 7 0;; リアル: 00:00:01.467、CPU: 00:00:01.520、GC 全般0: 0, 全般1: 0, 全般2: 0 val it: int = 14 > tak 22 11 0;; リアル: 00:00:01.633、CPU: 00:00:01.670、GC 全般0: 0, 全般1: 0, 全般2: 0 val it: int = 11
このように、たらいまわし関数は引数の値が小さくても実行に時間がかかります。
たらいまわし関数は遅延評価を使って高速化することができます。tarai() のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。ただし、もう一つの tak() は遅延評価で高速化することはできません。ご注意くださいませ。
lazy 式を使うと、たらいまわし関数は次のようになります。
リスト : lazy 式による遅延評価
let rec taraiLazy x y (z: Lazy<int>) =
if x <= y then y
else
let zz = z.Force()
taraiLazy (taraiLazy (x - 1) y z)
(taraiLazy (y - 1) zz (lazy x))
(lazy (taraiLazy (zz - 1) x (lazy y)))
遅延評価したい処理を lazy に包んで引数 z に渡します。そして、x > y のときに引数 z を評価 (z.Force()) します。すると、遅延オブジェクト内の式が評価されて z の値を求めることができます。たとえば、lazy 0 を z に渡す場合、z.Force() とすると返り値は 0 になります。lazy x を渡せば、x に格納されている値が返されます。lazy (taraiLazy ...) を渡せば、taraiLazy が評価されてその値が返されるわけです。
それでは実行してみましょう。
> let rec taraiLazy x y (z: Lazy<int>) = - if x <= y then y - else - let zz = z.Force() - taraiLazy (taraiLazy (x - 1) y z) - (taraiLazy (y - 1) zz (lazy x)) - (lazy (taraiLazy (zz - 1) x (lazy y)));; val taraiLazy: x: int -> y: int -> z: Lazy<int> -> int > #time;; --> 今すぐタイミング オン > taraiLazy 140 70 (lazy 0);; リアル: 00:00:00.003、CPU: 00:00:00.000、GC 全般0: 1, 全般1: 0, 全般2: 0 val it: int = 140
tarai() の場合、遅延評価の効果はとても大きいですね。
ところで、lazy 式を使わなくても、ラムダ式 (クロージャ) だけで遅延評価を行うことができます。次のリストを見てください。
リスト : クロージャによる遅延評価
let rec taraiLazy1 x y z =
if x <= y then y
else
let zz = z()
taraiLazy1 (taraiLazy1 (x - 1) y z)
(taraiLazy1 (y - 1) zz (fun () -> x))
(fun () -> taraiLazy1 (zz - 1) x (fun () -> y))
遅延評価したい処理をクロージャに包んで引数 z に渡します。そして、x > y のときに引数 z の関数を呼び出します。すると、クロージャ内の処理が評価されて z の値を求めることができます。たとえば、fun () -> 0 を z に渡す場合、z() とすると返り値は 0 になります。fun () -> x を渡せば、x に格納されている値が返されます。fun () -> taraiLazy1 ... を渡せば、taraiLazy1 が評価されてその値が返されるわけです。ただし、クロージャでは評価結果を保存 (キャッシュ) できないことに注意してください。
> let rec taraiLazy1 x y z = - if x <= y then y - else - let zz = z() - taraiLazy1 (taraiLazy1 (x - 1) y z) - (taraiLazy1 (y - 1) zz (fun () -> x)) - (fun () -> taraiLazy1 (zz - 1) x (fun () -> y));; val taraiLazy1: x: int -> y: int -> z: (unit -> int) -> int > #time;; --> 今すぐタイミング オン > taraiLazy1 140 70 (fun () -> 0);; リアル: 00:00:00.001、CPU: 00:00:00.000、GC 全般0: 0, 全般1: 0, 全般2: 0 val it: int = 140
要素を一列に並べたデータ構造を「シーケンス (sequence)」とか「列」と呼びます。リスト、一次元配列 (ベクタ)、文字列などはシーケンスとして考えることができます。プログラミング言語によっては、これらのデータ型を列型 (sequence) として統一的に扱うことができるもの (たとえば Common Lisp など) があります。
F# の場合、標準ライブラリにシーケンスを表すデータ型 seq<'T> が用意されています。seq<'T> は .NET の標準ライブラリにあるインターフェース IEnumerable<T> のエイリアス (別名) なので、IEnumerable<T> を継承している型であればシーケンスとして扱うことができます。シーケンスの操作関数はモジュール Seq に定義されています。今回はシーケンス seq<'T> の基本的な使い方について簡単に説明します。
シーケンスは「シーケンス式」を使って簡単に生成することができます。
seq { expr1; expr2; ... }
[軽量構文]
seq { expr1
expr2
... }
{ } の中の式 expr を評価した値がシーケンスの要素になります。expr の評価結果は同じデータ型でなければいけません。評価結果が unit の場合はシーケンスに格納されません。expr はセミコロンで区切ります。軽量構文を使うとセミコロンを省略することができます。
シーケンスを生成する一番簡単な方法は、範囲指定 s .. e を使うことです。簡単な使用例を示しましょう。
> seq { 1 .. 8 };;
val it: seq<int> = seq [1; 2; 3; 4; ...]
> seq { 1 .. 2 .. 8 };;
val it: seq<int> = seq [1; 3; 5; 7]
> seq { 1.0 .. 8.0 };;
val it: seq<float> = seq [1.0; 2.0; 3.0; 4.0; ...]
> seq { 'a' .. 'd' };;
val it: seq<char> = seq ['a'; 'b'; 'c'; 'd']
シーケンスは for 文で要素を順番に取り出すことができます。
> for x in seq {1 .. 5} do printfn "%d" x;;
1
2
3
4
5
val it: unit = ()
シーケンスの要素は遅延評価されます。次の例を見てください。
> let a = seq {1; printfn "one"; 2; printfn "two"; 3; printfn "three"; 4; printfn "four"; 5; printfn "five"};;
val a: seq<int>
> a;;
one
two
three
four
val it: seq<int> = seq [1; 2; 3; 4; ...]
> a;;
one
two
three
four
val it: seq<int> = seq [1; 2; 3; 4; ...]
シーケンスの要素にアクセスするとき、その要素に対応する式が評価されます。上記の例のように、シーケンスを変数 a にセットするとき、シーケンスの要素は評価されません。REPL で変数 a の値を表示するとき、先頭から 4 つの要素の値を表示するので、ここで要素が評価されます。
なお、F# のシーケンスはデフォルトで評価結果をキャッシュしないので、同じ式が再度評価されます。モジュール Seq の関数 cache を使うと、評価結果をキャッシュするシーケンスを作成することができます。
F# の seq は { ... } の中に for を書いて、シーケンスを生成することができます。Python や Haskell のリスト内包表記と同様の機能です。
1. seq {for 変数 in コレクション -> 式1; 式2; ...; 式n}
2. seq {for 変数 in コレクション do 式1; 式2; ...; 式n}
1. の場合、シーケンスに格納されるのは最後の式n の評価結果だけです。他の式の評価結果は捨てられます。このとき、ワーニングも表示されます。2. の場合、式の評価結果はすべてシーケンスに格納されます。2. は式の前にキーワード yield を指定してもかまいません。for で in のかわりに to や downto を使いたい場合は、2 のように do を使ってください。-> を使うとエラーになります。
簡単な使用例を示しましょう。
> let b = seq {for x in 1..5 do x * x};;
val b: seq<int>
> for x in b do printfn "%d" x;;
1
4
9
16
25
val it: unit = ()
> let c = seq {for x in 1..5 do x; x * x};;
val c: seq<int>
> for x in c do printfn "%d" x;;
1
1
2
4
3
9
4
16
5
25
val it: unit = ()
> let d = seq {for x in 1..5 -> x * x * x};;
val d: seq<int>
> for x in d do printfn "%d" x;;
1
8
27
64
125
val it: unit = ()
do の中では if を使って条件を指定することができます。ただし、-> の中で if を使うことはできません。
> let e = seq {for x in 1..10 do if x % 2 = 0 then x};;
val e: seq<int>
> for x in e do printfn "%d" x;;
2
4
6
8
10
val it: unit = ()
> let f = seq {for x in 1..10 do if x % 2 = 0 then x; let y = x * x in if y % 2 = 0 then y};;
val f: seq<int>
> for x in f do printfn "%d" x;;
2
4
4
16
6
36
8
64
10
100
val it: unit = ()
for は多重ループにしてもかまいません。ただし、最後の for 以外は -> ではなく do を使ってください。
> let g = seq {for x in 1..4 do for y in 5..8 -> (x, y)};;
val g: seq<int * int>
> for x in g do printfn "%A" x;;
(1, 5)
(1, 6)
(1, 7)
(1, 8)
(2, 5)
(2, 6)
(2, 7)
(2, 8)
(3, 5)
(3, 6)
(3, 7)
(3, 8)
(4, 5)
(4, 6)
(4, 7)
(4, 8)
val it: unit = ()
シーケンスの中に別のシーケンスを含める (平坦化する) にはキーワード yiled! を使います。
seq {
...
yield! sequence
...
}
yield! に渡す引数はシーケンスだけではなくリストや配列でもかまいません。簡単な例を示しましょう。
> seq {
- 1
- yield! seq {2 ;3; 4}
- yield! [5; 6; 7; 8]
- yield! [|9; 10|]
- };;
val it: seq<int> = seq [1; 2; 3; 4; ...]
> for x in it do printf "%d " x;;
1 2 3 4 5 6 7 8 9 10 val it: unit = ()
> let a = seq {for i = 0 to 3 do yield! seq {10; 20; 30}};;
val a: seq<int>
> for x in a do printf "%d " x;;
10 20 30 10 20 30 10 20 30 10 20 30 val it: unit = ()
yield! を使うと二分木をシーケンスに変換することも簡単です。F# の seq { ... } は for や if だけではなく他の式も記述することができます。次のリストを見てください。
リスト : 二分木をシーケンスに変換
type tree = Leaf of int | Node of tree * tree
let rec fromTree xs =
seq {
match xs with
Leaf n -> n
| Node (l, r) -> yield! fromTree l
yield! fromTree r
}
二分木 tree は葉 Leaf に値 (整数) を格納します。節 Node は左右の部分木を格納します。関数 formTree は二分木 xs をシーケンスに変換します。seq の中で引数 xs をパターンマッチングします。Leaf n とマッチングすれば n を返します。これで seq {n} が生成されます。Node (l, r) とマッチングすれば、fromTree を再帰呼び出しします。そして、その返り値を yield! で平坦化します。これで左右の部分木を平坦化して連結することができます。
それでは実際に試してみましょう。
> type tree = Leaf of int | Node of tree * tree;;
type tree =
| Leaf of int
| Node of tree * tree
> let rec fromTree xs =
- seq {
- match xs with
- Leaf n -> n
- | Node (l, r) -> yield! fromTree l
- yield! fromTree r
- };;
val fromTree: xs: tree -> seq<int>
> let tree = Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Leaf 4));;
val tree: tree = Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Leaf 4))
> let b = fromTree tree;;
val b: seq<int>
> for x in b do printfn "%d " x;;
1
2
3
4
val it: unit = ()
正常に動作していますね。
モジュール Seq にはシーケンスを操作する関数が多数用意されています。それらの関数には、リストや配列の操作関数と似たような動作をする関数もあります。
Seq.empty => sequence seq.isEmpty sequence => bool
> Seq.empty;;
val it: seq<'a>
> Seq.isEmpty Seq.empty;;
val it: bool = true
> seq {1; 2; 3} |> Seq.isEmpty;;
val it: bool = false
Seq.empty は空のシーケンスを返します。List や Array の empty と同じです。Seq.isEmtpy は引数が空のシーケンスであれば真を返します。List や Array の isEmpty と同じです。
Seq.length sequence => int
> Seq.length Seq.empty;;
val it: int = 0
> seq {1..8} |> Seq.length;;
val it: int = 8
シーケンスの長さは Seq.length で求めることができます。List や Array の length と同じです。
Seq.head sequence => item Seq.tail sequence => sequence
> let a = seq {1..8};;
val a: seq<int>
> Seq.head a;;
val it: int = 1
> Seq.tail a;;
val it: seq<int> = seq [2; 3; 4; 5; ...]
> for x in Seq.tail a do printf "%d " x;;
2 3 4 5 6 7 8 val it: unit = ()
Seq.head はシーケンスの先頭要素を返します。Seq.tail はシーケンスの先頭要素を取り除いたシーケンスを返します。List の head, tail と同じです。
Seq.item index sequence => item
> for i = 0 to 7 do Seq.item i a |> printf "%d ";; 1 2 3 4 5 6 7 8 val it: unit = ()
Seq.item は sequence の index 番目の要素を求めます。List や Array の item と同じです。配列のように角カッコを使ってアクセスすることはできません。
Seq.insertAt index item sequence => new_sequence Seq.removeAt index sequence => new_sequence
> let b = Seq.insertAt 0 0 a;; val b: seq<int> > a;; val it: seq<int> = seq [1; 2; 3; 4; ...] > b;; val it: seq<int> = seq [0; 1; 2; 3; ...] > let c = Seq.insertAt 8 10 a;; val c: seq<int> > for x in c do printf "%d " x;; 1 2 3 4 5 6 7 8 10 val it: unit = () > for x in Seq.removeAt 0 a do printf "%d " x;; 2 3 4 5 6 7 8 val it: unit = () > for x in Seq.removeAt 3 a do printf "%d " x;; 1 2 3 5 6 7 8 val it: unit = () > for x in Seq.removeAt 7 a do printf "%d " x;; 1 2 3 4 5 6 7 val it: unit = ()
Seq.insertAt は sequence の index 番目に item を挿入した新しいシーケンスを返します。Seq.removeAt は sequence の index 番目の要素を削除した新しいシーケンスを返します。List の insertAt, removeAt と同じです。
Seq.init count func => sequence
> Seq.init 8 (fun x -> x * x);; val it: seq<int> = seq [0; 1; 4; 9; ...]
Seq.init は長さ (要素数) が count のシーケンスを返します。要素は添字を引数の関数 func に渡して生成します。List や Array の init と同じです。
Seq.append seq1 seq2 => sequence
> Seq.append (seq {1; 2; 3}) (seq {4; 5; 6});;
val it: seq<int> = seq [1; 2; 3; 4; ...]
> for x in Seq.append (seq {1; 2; 3}) (seq {4; 5; 6}) do printfn "%d" x;;
1
2
3
4
5
6
val it: unit = ()
Seq.append は引数 seq1 と seq2 を連結した新しいシーケンスを返します。List や Array の append と同じです。
Seq.rev sequence => new_sequence
> a;; val it: seq<int> = seq [1; 2; 3; 4; ...] > for x in Seq.rev a do printf "%d " x;; 8 7 6 5 4 3 2 1 val it: unit = ()
Seq.rev は引数のシーケンスを反転した新しいシーケンスを返します。List.rev と同じです。
Seq.take n sequence => new_sequence Seq.skip n sequence => new_sequence
> Seq.take 4 a;; val it: seq<int> = seq [1; 2; 3; 4] > Seq.skip 4 a;; val it: seq<int> = seq [5; 6; 7; 8]
Seq.take は sequence の先頭から n 個の要素を取り出し、それを格納した新しいシーケンスを返します。Seq.skip は sequence の先頭から n 個の要素を取り除いた新しいシーケンスを返します。List の take, skip と同じです。
Seq.ofList list => sequence Seq.toList sequence => list Seq.ofArray array => sequence Seq.toArray sequence => array
> Seq.ofList [1..10];;
val it: seq<int> = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
> seq {1..10} |> Seq.toList;;
val it: int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
> Seq.ofArray [|1..10|];;
val it: seq<int> = seq [1; 2; 3; 4; ...]
> seq {1..10} |> Seq.toArray;;
val it: int[] = [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|]
リストとシーケンスの変換は Seq.ofList, Seq.toList を使います。配列とシーケンスの変換は Seq.toArray, Seq.ofArray を使います。
Seq にはシーケンス用の高階関数も用意されています。
> Seq.map;;
val it: (('a -> 'b) -> seq<'a> -> seq<'b>)
> Seq.filter;;
val it: (('a -> bool) -> seq<'a> -> seq<'a>)
> Seq.fold;;
val it: (('a -> 'b -> 'a) -> 'a -> seq<'b> -> 'a)
> Seq.foldBack;;
val it: (('a -> 'b -> 'b) -> seq<'a> -> 'b -> 'b)
> Seq.iter;;
val it: (('a -> unit) -> seq<'a> -> unit)
map, filter, fold, foldBack, iter は今までに説明した高階関数のシーケンスバージョンです。
簡単な使用例を示しましょう。
> seq {1..8} |> Seq.map (fun x -> x * x) |> Seq.toList;;
val it: int list = [1; 4; 9; 16; 25; 36; 49; 64]
> seq {1..8} |> Seq.filter (fun x -> x % 2 = 0) |> Seq.toList;;
val it: int list = [2; 4; 6; 8]
> seq {1..8} |> Seq.fold (+) 0;;
val it: int = 36
> Seq.foldBack (+) (seq {1..8}) 0;;
val it: int = 36
> seq {1..4} |> Seq.iter (fun x -> printfn "%d" x);;
1
2
3
4
val it: unit = ()
Seq.contains item sequence => bool Seq.exists pred sequence => bool Seq.forall pred sequence => bool
> seq {1..8} |> Seq.contains 5 ;
- ;;
val it: bool = true
> seq {1..8} |> Seq.contains 8;;
val it: bool = true
> seq {1..8} |> Seq.contains 0;;
val it: bool = false
> seq {1..8} |> Seq.exists (fun x -> x % 8 = 0);;
val it: bool = true
> seq {1..8} |> Seq.exists (fun x -> x % 9 = 0);;
val it: bool = false
> seq {1..2..9} |> Seq.forall (fun x -> x % 2 = 1);;
val it: bool = true
> seq {1;3;5;7;9;10} |> Seq.forall (fun x -> x % 2 = 1);;
val it: bool = false
要素の有無は Seq.contains で調べることができます。List や Array の contains と同じです。述語 pred を満たす要素があるか調べるには Seq.exists を使います。Seq.forall は sequence の要素がすべて pred を満たすならば真を返します。満たさない要素が一つであれば偽を返します。List や Array の exists, forall と同じです。
Seq.find pred seq => item Seq.findIndex pred seq => int Seq.tryFind pred seq => item option Seq.tryFindIndex pred seq => int option
> seq {11..20} |> Seq.find (fun x -> x % 2 = 0);;
val it: int = 12
> seq {11..20} |> Seq.findIndex (fun x -> x % 2 = 0);;
val it: int = 1
> seq {11..20} |> Seq.tryFind (fun x -> x % 2 = 0);;
val it: int option = Some 12
> seq {11..20} |> Seq.tryFind (fun x -> x > 20);;
val it: int option = None
> seq {11..20} |> Seq.tryFindIndex (fun x -> x % 2 = 0);;
val it: int option = Some 1
> seq {11..20} |> Seq.tryFindIndex (fun x -> x > 20);;
val it: int option = None
述語 pred を満たす要素を探すには Seq.find を使います。要素の位置 (添字) を求めるには Seq.findIndex を使います。List や Array の find, findIndex と同じです。見つからない場合、これらの関数ではエラーが送出されます。返り値が option 型の関数 tryFind, tryFindIndex もあります。
Seq.takeWhile pred sequence => new_sequence Seq.skipWhile pred sequence => new_sequence
> seq {1..8} |> Seq.takeWhile (fun x -> x < 5);;
val it: seq<int> = seq [1; 2; 3; 4]
> seq {1..8} |> Seq.skipWhile (fun x -> x < 5);;
val it: seq<int> = seq [5; 6; 7; 8]
Seq.takeWhile は sequence の先頭から述語 pred を満たす要素が続く限り取り出して、それらを新しいシーケンスに格納して返します。Seq.skipWhile は sequence の先頭から述語 pred を満たす要素が続く限りそれらを取り除いた新しいシーケンスを返します。List の takeWhile, skipWhile と同じです。
「ストリーム (stream)」はデータの流れを抽象化したデータ構造です。たとえば、ファイル入出力はストリームと考えることができます。また、配列や連結リストを使ってストリームを表すこともできます。ただし、単純な配列や連結リストでは有限個のデータの流れしか表すことができません。
ところが、遅延評価を用いると擬似的に無限個のデータを表すことができるようになります。これを「遅延ストリーム」とか「遅延リスト」と呼びます。シーケンスの要素は遅延評価されるので、シーケンスを遅延リストのように取り扱うことができます。本ページでは、無限シーケンスと呼ぶことにします。
無限シーケンスは以下の関数で生成することができます。
Seq.initInfinite initFunc => sequence Seq.unfold genFunc initState => sequence
Seq.initInfinite は添字を関数 initFunc に渡して要素を生成します。Seq.init のように大きさの指定はないので、無限シーケンスが生成されます。Seq.unfold は状態 state を genFunc に渡して、シーケンスに格納する要素と新しい状態を生成します。Seq.unfold の型を示します。
> Seq.unfold;;
val it: (('a -> ('b * 'a) option) -> 'a -> seq<'b>)
'a が状態の型、'b がシーケンスの要素の型を表します。genFunc の返り値は option 型です。None を返すとシーケンスが終了します。None を返さなければ無限シーケンスになります。なお、List にも unfold があります。一般に unfold のような動作を「逆畳み込み」とか「解きほぐし」といいます。
簡単な使用例を示しましょう。
> let ints = Seq.initInfinite (fun x -> x + 1);; val ints: seq<int> > for x in Seq.take 10 ints do printf "%d " x;; 1 2 3 4 5 6 7 8 9 10 val it: unit = () > for x in Seq.skip 100 ints |> Seq.take 10 do printf "%d " x;; 101 102 103 104 105 106 107 108 109 110 val it: unit = () > let ints1 = Seq.unfold (fun x -> Some (x, x + 1)) 1;; val ints1: seq<int> > for x in Seq.take 10 ints1 do printf "%d " x;; 1 2 3 4 5 6 7 8 9 10 val it: unit = () > for x in Seq.skip 100 ints1 |> Seq.take 10 do printf "%d " x;; 101 102 103 104 105 106 107 108 109 110 val it: unit = ()
initInfinite と unfold で自然数の数列を生成します。どちらも無限シーケンスになりますが、要素の型が int なので有限の自然数しか生成できません。多倍長整数 (bigint) を使うと、メモリの許す限り自然数を生成することができます。
もう一つ簡単な例としてフィボナッチ数列を作ってみましょう。
> let fibo = Seq.unfold (fun (a, b) -> Some (a, (b, a + b))) (0I, 1I);; val fibo: seq> for x in Seq.take 10 fibo do printf "%A " x;; 0 1 1 2 3 5 8 13 21 34 val it: unit = () > for x in Seq.skip 40 fibo |> Seq.take 10 do printf "%A " x;; 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 val it: unit = () > Seq.item 100 fibo;; val it: System.Numerics.BigInteger = 354224848179261915075 {IsEven = false; IsOne = false; IsPowerOfTwo = false; IsZero = false; Sign = 1;}
状態 (0I, 1I) の 0I がフィボナッチ数列の最初の項で、1I が次の項です。したがって、ラムダ式の引数 (a, b) の a がストリームに格納する要素で、次の状態が (b, a + b) になります。bigint を使っているので、メモリの許す限りフィボナッチ数列を生成することができます。
次はシーケンス s1 と s2 の要素を交互に出力するシーケンスを作ります。次のリストを見てください。
リスト : シーケンスの要素を交互に出力
let rec interleave<'a> (s1: seq<'a>) (s2: seq<'a>) =
if Seq.isEmpty s1 then s2
else
seq {
Seq.head s1
yield! interleave s2 (Seq.tail s1)
}
関数 interleave はシーケンス s1 と s2 を受け取ります。そして、s1 の要素を新しいシーケンスに格納したら、次は s2 の要素を新しいシーケンスに格納します。これは seq { ... } の中で interleave を呼び出すとき、引数 s1 と s2 の順番を交換するだけです。このとき、s1 は Seq.tail を適用して次の要素を求めます。これで s1 と s2 の要素を交互に出力することができます。
簡単な実行例を示しましょう。
> let rec interleave<'a> (s1: seq<'a>) (s2: seq<'a>) =
- if Seq.isEmpty s1 then s2
- else
- seq {
- Seq.head s1
- yield! interleave s2 (Seq.tail s1)
- };;
val interleave: s1: seq<'a> -> s2: seq<'a> -> seq<'a>
> let a = interleave (seq {1;2;3}) (seq {4;5;6});;
val a: seq<int>
> for x in a do printf "%d " x;;
1 4 2 5 3 6 val it: unit = ()
Seq.append の場合、無限シーケンスを結合することはできませんが、interleave ならば無限シーケンスにも対応することができます。簡単な例を示しましょう。
> let ones = Seq.initInfinite (fun _ -> 1);; val ones: seq<int> > ones |> Seq.take 10 |> Seq.toList;; val it: int list = [1; 1; 1; 1; 1; 1; 1; 1; 1; 1] > let twos = Seq.initInfinite (fun _ -> 2);; val twos: seq<int> > twos |> Seq.take 10 |> Seq.toList;; val it: int list = [2; 2; 2; 2; 2; 2; 2; 2; 2; 2] > Seq.append ones twos |> Seq.take 10 |> Seq.toList;; val it: int list = [1; 1; 1; 1; 1; 1; 1; 1; 1; 1] > interleave ones twos |> Seq.take 10 |> Seq.toList;; val it: int list = [1; 2; 1; 2; 1; 2; 1; 2; 1; 2]
ones は 1 を無限に出力するシーケンスで、twos は 2 を無限に出力するシーケンスです。Seq.append で ones と twos を結合しても無限に 1 を出力するだけですが、interleave で ones と twos を結合すれば、1 と 2 を交互に出力することができます。これで無限シーケンスの要素を混ぜ合わせることができます。
最後に簡単な例題として、シーケンスを使って素数を求めるプログラムを作ってみましょう。考え方は簡単です。最初に、2 から始まる整数列を生成するシーケンスを用意します。2 は素数なので、素数シーケンスの要素になります。次に、この整数列から 2 で割り切れる整数を取り除き除きます。これは Seq.filter を使うと簡単です。
2 で割り切れる整数が取り除かれたので、次の要素は 3 になります。今度は 3 で割り切れる整数を取り除けばいいのです。これも Seq.filter を使えば簡単です。このとき、入力用のシーケンスは 2 で割り切れる整数が取り除かれています。したがって、このシーケンスに対して 3 で割り切れる整数を取り除くように Seq.filter を設定すればいいわけです。
このように、素数を見つけたらそれで割り切れる整数を取り除いていくアルゴリズムを「エラトステネスの篩」といいます。ようするに、2 から始まる整数シーケンスに対して、見つけた素数 2, 3, 5, 7, 11, ... を順番に Seq.fiter で設定して素数でない整数をふるい落としていくわけです。
プログラムは次のようになります。
リスト : 素数の生成
let rec sieve (s: seq<int>) =
seq {
let x = Seq.head s
x
yield! (sieve (Seq.filter (fun n -> n % x <> 0) (Seq.tail s)))
}
sieve の引数 s には 2 から始まる整数列を生成するシーケンスを渡します。s に Seq.tail を適用し、さらに Seq.filter を適用すると、整数列から 2 で割り切れる整数を取り除いたシーケンスが返されます。次の要素 3 を取り出すとき、このシーケンスに対して 3 で割り切れる整数を取り除くことになるので、2 と 3 で割り切れる整数が取り除かれることになります。次の要素は 5 になりますが、そのシーケンスからさらに 5 で割り切れる整数が Seq.filter で取り除かれることになります。
このように Seq.filter が設定されていくことで、素数でない整数をふるい落としていくことができるわけです。それでは実行してみましょう。
> let rec sieve (s: seq<int>) =
- seq {
- let x = Seq.head s
- x
- yield! (sieve (Seq.filter (fun n -> n % x <> 0) (Seq.tail s)))
- };;
val sieve: s: seq<int> -> seq<int>
> let ps = sieve (Seq.initInfinite (fun x -> x + 2));;
val ps: seq<int>
> Seq.take 25 ps |> Seq.toList;;
val it: int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
73; 79; 83; 89; 97]
> Seq.take 100 ps |> Seq.toList;;
val it: int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151;
157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233;
239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317;
331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419;
421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499; 503;
509; 521; 523; 541]
関数 sieve は簡単にプログラムできますが、生成する素数の個数が多くなると、その実行速度はかなり遅くなります。実をいうと、sieve なみに簡単で sieve よりも高速な方法があります。
整数 n が素数か確かめる簡単な方法は、√n 以下の素数で割り切れるか試してみることです。割り切れる素数 m があれば、n は素数ではありません。そうでなければ、n は素数であることがわかります。
これをそのままプログラムすると次のようになります。
リスト : 素数列の生成
let rec primesFrom (n: int) =
if isPrime n then seq {n; yield! primesFrom (n + 2)}
else primesFrom (n + 2)
and isPrime n =
let rec iter s =
let p = Seq.head s
if p * p > n then true
else if n % p = 0 then false
else Seq.tail s |> iter
Seq.tail primes |> iter
and primes = seq {2; 3; 5; yield! primesFrom 7}
変数 primes は無限の素数列を表します。実際に素数を生成する処理は関数 primesFrom で行います。primesFrom は述語 isPrime を呼び出して n が素数かチェックします。そうであれば、seq { ... } で n をシーケンスに追加します。そうでなければ primesFrom を再帰呼び出しするだけです。偶数は素数ではないので、引数 n には奇数を与えていることに注意してください。isPrime は primes をたどって n が素数か判定するだけです。
それでは実行してみましょう。
> let rec primesFrom (n: int) =
- if isPrime n then seq {n; yield! primesFrom (n + 2)}
- else primesFrom (n + 2)
- and isPrime n =
- let rec iter s =
- let p = Seq.head s
- if p * p > n then true
- else if n % p = 0 then false
- else Seq.tail s |> iter
- Seq.tail primes |> iter
- and primes = seq {2; 3; 5; yield! primesFrom 7};;
=> ワーニング (略)
val primesFrom: n: int -> seq<int>
val isPrime: n: int -> bool
val primes: seq<int>
> Seq.take 25 primes |> Seq.toList;;
val it: int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
73; 79; 83; 89; 97]
> Seq.take 100 primes |> Seq.toList;;
val it: int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151;
157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233;
239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317;
331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419;
421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499; 503;
509; 521; 523; 541]
> Seq.item 99 primes;;
val it: int = 541
> Seq.item 500 primes;;
val it: int = 3581
100 以下の素数は全部で 25 個あります。また、100 番目の素数は 541 になります。F# のリストは 0 から数えるので、Seq.item 99 primes で 100 番目の素数になります。実行時間ですが、Seq.item で 1000 番目の素数を求めたところ、sieve では約 6 秒かかりましたが、primes は 0.2 秒で求めることができました。
F# のシーケンスはデフォルトで評価結果をキャッシュしません。Seq.cache を使うと評価結果をキャッシュするようになります。最初の評価に時間がかかっても、次からは高速に素数を求めることができます。
> let psc = Seq.cache ps;; リアル: 00:00:00.001、CPU: 00:00:00.000、GC 全般0: 0, 全般1: 0, 全般2: 0 val psc: seq<int> > Seq.item 1000 psc;; リアル: 00:00:06.075、CPU: 00:00:06.100、GC 全般0: 456, 全般1: 37, 全般2: 0 val it: int = 7927 > Seq.item 1000 psc;; リアル: 00:00:00.000、CPU: 00:00:00.000、GC 全般0: 0, 全般1: 0, 全般2: 0 val it: int = 7927
興味のある方はいろいろ試してみてください。