open netshop

Chapter 1. データ処理

Table of Contents

1. シーケンス
1.1. コレクション
1.2. シーケンス
1.3. シーケンス式
1.4. Seqモジュール
1.5. 配列、リストにおけるシーケンス式
2. リスト処理
2.1. リストの基本
2.2. リスト処理テクニックの応用範囲
2.3. リスト処理の基本
2.4. リスト処理の応用

1. シーケンス

1.1. コレクション

.NET Frameworkには、データ列を表現するための抽象的なインターフェイスとして、IEnumerable<T>インターフェイスが存在します。このインターフェイスを実装するクラスに対してGetEnumeratorメソッドを呼び出すと、列挙子(イテレータ)としてIEnumerator<T>インターフェイスが返されます。この列挙子は「データを読み込む操作」を抽象化したもので、これを使うとデータの集合から1要素ずつ順番に読み込むことができます。.NET Frameworkでは、このようにIEnumerable<T>インターフェイスを実装するクラスをコレクションと呼びます。

コレクションが返す列挙子は、現在の読み取り位置の値を表すCurrentプロパティ、読み取り位置を次に進めるMoveNextメソッド、読み取り位置を最初の位置にリセットするResetメソッドの3つのメンバをもちます。データを読み取る側からすると、コレクションはこの3つのメンバのさえ備えていれば、内部の実装はどのようでも構いません。つまりコレクションとは、現在位置の値を読み取れて、読み取り位置を次に進められて、読み取り位置をリセットできるものであれば何でもよいのです。したがって、ごく普通の固定長の配列データだけでなく、終端に達して始めて要素の個数が確定するような可変長のデータ、初めからデータはどこにも存在せず読み取り位置が進むたびオンデマンドに要素が作り出されるようなデータ、そして終端のない無限に続くデータ(無限リストと呼ぶ)など、さまざまな性質を持つコレクションを表現することができます。

F#においても、配列やリストなどはこのIEnumerable<T>インターフェイスを実装しています。F#でもこのインターフェイスはよく利用されるため、標準でseq<'T>または'T seqという別名がつけられています。

Note

F#ではリストの型名'a listlist<'a>と書くこともできます。これは記法の違いで実際には両方ともまったく同じものを意味します。この2種類の記法はリスト以外の型でも使うことができます。たとえばseq<int>int seqと書いても同じ意味になります。

例として、リストからseq<'T>を取り出し、それを経由してリストの中身にアクセスしてみましょう。

> let p = [1..3] :> seq<int>;; // list<int>からseq<int>にアップキャスト
val p : seq<int> = [1; 2; 3]

> let e = p.GetEnumerator();; // 列挙子を取り出す
val e : System.Collections.Generic.IEnumerator<int>

> e.MoveNext();; // 先頭の要素に読み取り位置を移動
val it : bool = true
> e.Current;; // 先頭の要素を読み取る
val it : int = 1
> e.MoveNext();; // 2番目の要素に読み取り位置を移動
val it : bool = true
> e.Current;; // 2番目の要素を読み取る
val it : int = 2
> e.MoveNext();; // 3番目の要素に読み取り位置を移動
val it : bool = true
> e.Current;; // 3番目の要素を読み取る
val it : int = 3
> e.MoveNext();; // 4番目の要素に読み取り位置を移動(終端なのでfalseが返る)
val it : bool = false

また、このseq<'T>を自分で実装することで任意のデータ列を生成するコレクションを作ることができます。たとえば、無限に1ずつ増える多倍長整数のデータ列は以下のように定義することができます。ここでは、IEnumerator<bigint>IEnumerable<bigint>(さらにこれらが継承するIEnumeratorIEnumerableIDisposable)を自分で実装していますが、後で紹介するF#のSeqモジュールを利用すると、以下の実装と同等のものを簡単に作り出すことができます。

// 0Iから次々と数字を生み出す補助クラス
type internal NumGenerator() =
  let counter = ref 0I
  interface IEnumerator<bigint> with
    [<OverloadID("1")>]
    member v.Current = !counter
    [<OverloadID("2")>]
    member v.Current = !counter :> obj
    member v.MoveNext() = counter := !counter + 1I; true
    member v.Reset() = counter := 0I
    member v.Dispose() = ()

// 無限に多倍長整数値を生み出すクラス
type InfiniteNumber() =
  interface IEnumerable<bigint> with
    [<OverloadID("1")>]
    member v.GetEnumerator() = new NumGenerator() :> IEnumerator<bigint>
    [<OverloadID("2")>]
    member v.GetEnumerator() = new NumGenerator() :> IEnumerator

これを利用することで、以下のように列挙子を取り出して無限に値を列挙することができます。

> let e = new InfiniteNumber() :> seq<bigint>;; // InfiniteNumberのインスタンスをseq<bigint>(すなわちIEnumerable<bigint>)にアップキャスト
val e : seq<bigint>

> let n = e.GetEnumerator();; // 列挙子を取り出す
val n : IEnumerator<bigint>

> n.MoveNext();; // 先頭に移動
val it : bool = true
> printfn "value=%A" n.Current;; // 1番目の要素を出力
value=1
val it : unit = ()

> n.MoveNext();; // 次に移動
val it : bool = true
> printfn "value=%A" n.Current;; // 2番目の要素を出力
value=2
val it : unit = ()

> n.MoveNext();; // 次に移動
val it : bool = true
> printfn "value=%A" n.Current;; // 3番目の要素を出力
value=3
val it : unit = ()

1.2. シーケンス

前小節ではseq<'T>を実装することで、要素が要求されるたびにその場で値を生成して返すようなコレクションが実現できることを説明しました。このようなコレクションは、値を次々と生成するための規則を持っており、次のが要求されるたびにその規則に従って1つずつ値を生成していきます。プログラミング言語論では、このようにある規則に従って次々と値を作り出すコレクションのことを、ジェネレータ(generator)と呼びます。それに対して、通常の配列やリストは初めからすべての値がメモリ上に存在しており、要求されると単にそのメモリ上の値を返すだけなのでそれらをジェネレータとは呼びません。

F#には、ジェネレータを簡単に作り出すことができるシーケンス(sequence)というものが用意されており、これを使うと配列やリストのような手軽さで遅延リストを生成することができます。シーケンスを作るには場合は次の構文を使います。

seq { シーケンス式 }

seq{}内にはシーケンス式というものを書くことができます。シーケンス式(sequence expression)は、毎回値を生み出すのに使うための「規則」を記述することができます。この規則を表現する構文にはさまざまなものがありますが、そのうちいくつかの例をみてみましょう。シーケンス式の詳しい構文については次小節で説明するので、ここではとりあえずシーケンス式の雰囲気をつかんでください。

// 1から5の範囲で、毎回1ずつ増加させる規則
seq { 1..5 } // 1,2,3,4,5

// 1から25の範囲で、毎回5ずつ増加させる規則
seq { 1..5..25 } // 1,6,11,16,21

// 1から7の範囲の値を毎回iに束縛し、毎回iを2乗したものを返す規則
seq {
  for i in 1..7 do
    yield i * i
} // 1,4,9,16,25,36,49

// まず1から2の範囲の値を毎回xに束縛し、
// 次に1から3の範囲の値を毎回yに束縛し、
// xとyから作ったタプル(x,y)を返す規則
seq {
  for x in 1..2 do
    for y in 1..3 do
      yield (x,y)
} // (1,1),(1,2),(1,3),(2,1),(2,2),(2,3)

// まず1から100の範囲の値を毎回xに束縛し、
// xが3と5で割り切れるならば値を返し、
// そうでなければ値を返さないで次の値を試す規則
seq {
  for x in 1..100 do
    if x % 3 = 0 && x % 5 = 0 then yield x
} // 15,30,45,60,75,90

このように、シーケンス式にはさまざまな規則を表現するための構文があります。シーケンスはこの規則を記憶しており、要求されるたびにこの規則に従って値を作り出します。ここで示した例は、シーケンス式のほんの一部に過ぎませんが、これらを見るだけでも非常に高い表現力を持つことがわかります。

Note

(このNoteは理解できなければ飛ばしてください)

Haskellをかじったことがある方なら気づいたかも知れませんが、シーケンス式は実際にはリストモナドとして実装されています。リストモナドのおかげでシーケンス式はこの高い表現力をもっているのです。

応用編で解説しますが、F#におけるモナド構文にはcomputation expressionという名前がついています。シーケンス式は、実際にはこのcomputation expressionを用いて実装されています。

1.3. シーケンス式

シーケンス式は、seq {}の括弧の中だけで書くことができる特殊な式です。この括弧の中には通常のF#の式を直接書くことはできないため、ここでは必ずシーケンス式の文法に従って書く必要があります。ただシーケンス式の文法といっても、そんなに特殊な形をしているわけではなく、通常のF#の式とよく似た形をしています。ここでは、そのシーケンス式の文法を1つずつ紹介していきます。ここでも、シーケンスはジェネレータ(すなわち要求されたときに値が生成されるコレクション)であるということを意識しながら説明を読んでいってください。

1.3.1. シーケンス式同士の結合

シーケンス式1 ; シーケンス式2

複数のシーケンス式は、セミコロンで区切ることで1つのシーケンス式に結合することができます。結合されたシーケンス式は、まず左側が評価されてその次に右側という順番で評価が行われます。軽量構文では、2つのシーケンス式の間に改行をはさんだ場合、セミコロンは省略可能となります。

1.3.2. yield

yield 

ある列挙子に対して要素を要求すると、その列挙子はシーケンス内の現在位置の要素を返します。さらに続けて要素を要求すると、その続きの要素が返され、要素の最後に達すると列挙が終了します。つまり列挙子は現在位置を記憶しており、次回の要求に対してはその続きの要素を生成して返します。yieldはちょうどその値を返す処理をするシーケンス式で、yieldが評価された瞬間に列挙子は値を返すと同時に、その呼ばれたときのシーケンスの位置を記憶して、処理を呼び出し側に返します。

たとえば以下の例をみてください。

> seq { yield 3 };;
val it : seq<int> = seq [3]

> seq { yield 3; yield 4 };; // 2つのシーケンス式同士の結合
val it : seq<int> = seq [3; 4]

1番目のシーケンスは単純に1つの値をyieldするだけなので、1つの要素を返したらその時点でシーケンスの終わりに達してしまいます。2番目のシーケンスは、yieldを結合して1つのシーケンス式にしたものです。こちらは、要素が要求されると、まず最初にあるyield 3を評価したところで一旦停止して制御を返します。そしてさらに要素が要求されると、2つめのyield 4を評価して制御を返します。2番目のシーケンスは、この時点で終端に達します。

このシーケンスの要素を1つずつ要求する様子を詳しく調べるために、GetEnumerator()によって列挙子を取り出して、自分で1つずつ列挙してみましょう。

> let s = seq { yield 3; yield 4 };;
val s : seq<int>

> let e = s.GetEnumerator();;
val e : System.Collections.Generic.IEnumerator<int>

> e.MoveNext();; // 読み取り位置を進める
val it : bool = true
> e.Current;; // 値を取り出す
val it : int = 3
> e.MoveNext();; // 読み取り位置を進める
val it : bool = true
> e.Current;; // 値を取り出す
val it : int = 4
> e.MoveNext();; // 読み取り位置を進める
val it : bool = false
// 終端に達したのでfalseが返ってきた

この例のように、このシーケンス式はyieldのところで一旦処理と値を返し、次に値を要求されたときにその続きから処理を再開します。

Note

このyieldは、ちょうどC# 2.0から導入されたyield returnと同じ働きをします。視点を変えると、このyieldは処理を中断したり再開したりすることができる、一種のサブルーチンであると考えることができ、このようなものをプログラミング言語論ではコルーチン(coroutine)と呼びます。このコルーチンにおける中断や再開は、プログラムのメインルーチンとは独立した実行単位と考えられます。

1.3.3. yield!

yield! コレクション

yieldは1つの要素を作り出すことができるシーケンス式でしたが、yield!を使うとより柔軟に任意の個数の要素を作り出すことができます。yield!は引数にコレクションを受け取り、そのコレクション内の要素をシーケンスの要素として展開します。まず1つの例を見てください。

> seq { yield 1; yield! [2;3;4]; yield 5 };;
val it : seq<int> = seq [1; 2; 3; 4; 5]

このシーケンス式は、1番目と3番目がyieldで、2番目がyield!となっています。1番目と3番目は、そのまま1つの値を渡していますが、2番目はコレクションとしてリストを渡しています。ここで注目すべきなのは、[2;3;4]というコレクションの内容が、シーケンス内で展開されていることです。これにより、このシーケンス式全体は3つのシーケンス式で構成されているにもかかわらず、全体として5つの要素を持つシーケンスとなっています。

Note

F#インタプリタは識別子の値を画面に表示する際、表示が長すぎたら途中でその表示を省略します。コレクションの要素数が多い場合などでも、その制限によってすべての要素が表示されないことがあります。標準ではその表示幅は100に設定されていますが、以下のようにしてその幅を増やすことができます。

> fsi.PrintWidth <- 400;;
val it : unit = ()

本節で示す例では、コレクションの要素数に応じて、適宜この幅を調節しているので注意してください。

いくつか他の例も見てみましょう。

> seq { yield 1; yield! []; yield 5 };; // 0個のコレクションを渡す
val it : seq<int> = seq [1; 5]

> seq { yield 1; yield! [2]; yield 5 };; // 1個のコレクションを渡す
val it : seq<int> = seq [1; 2; 5]

> seq { yield 1; yield! [2..6]; yield 0 };; // コレクションの表現に範囲式を使う
val it : seq<int> = seq [1; 2; 3; 4; 5; 6; 0]

> seq { yield 1; yield! [2..6]; yield! [5..-1..1] };; // yield!を2つ使う
val it : seq<int> = seq [1; 2; 3; 4; 5; 6; 5; 4; 3; 2; 1]

このように、任意の個数の要素をその場に展開することができます。さらに、yield!にはリストではなく任意のコレクションを渡すことができます。

> seq { yield 1; yield! [2..4]; yield 5 };; // リストを渡す
val it : seq<int> = seq [1; 2; 3; 4; 5]

> seq { yield 1; yield! [|2..4|]; yield 5 };; // 配列を渡す
val it : seq<int> = seq [1; 2; 3; 4; 5]

> seq { yield 1; yield! seq { yield 2; yield 3; yield 4 }; yield 5 };; // シーケンスを渡す
val it : seq<int> = seq [1; 2; 3; 4; 5]

どの場合でも同じ結果になっていることがわかります。

1.3.4. 範囲式

開始値..終了値
開始値..増加値..終了値

範囲式(range expression)は、開始値から終了値までの値を生成します。増加値が省略された場合は、値が1ずつ増加していき、終了値を超えた時点でシーケンスは終了します。すなわち、生成される値xは開始値≦x≦終了値以下の範囲の値となります。

> seq { 1..4 };; // 整数の範囲指定
val it : seq<int> = seq [1; 2; 3; 4]

> seq { 1.0..3.0 };; // 小数の範囲指定
val it : seq<float> = seq [1.0; 2.0; 3.0]

> seq { 'a'..'d' };; // 文字の範囲指定
val it : seq<char> = seq ['a'; 'b'; 'c'; 'd']

1.3.5. for

for 識別子 in コレクション do シーケンス式
for パターン in コレクション do シーケンス式

これは通常のfor式と同じで、まずコレクションの中から値が1つずつ取り出され、その値が識別子に束縛されて毎回シーケンス式で評価されます。シーケンス式の中ではその識別子を参照することができ、そこには列挙子から取り出された値が束縛されています。パターンが使用された場合は、列挙子から取り出した値に対してパターンマッチを行われるので、複雑なデータ構造から簡単に値を取り出すことができます。例を見てみましょう。

> seq { for x in 1..10 do yield x };; // 1から10の値を毎回xに束縛する
val it : seq<int> = seq [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

> seq { for x in [|1..10|] do yield x };; // 1から10の値を含む配列から値を取り出して毎回xに束縛する
val it : seq<int> = seq [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

> seq { for x in 1..10 do yield x*x };; // 1から10の値をそれぞれ2乗する
val it : seq<int> = seq [1; 4; 9; 16; 25; 36; 49; 64; 81; 100]

> seq { for x in 0..3 do yield [0..x] };; // 0からxまでのリストを毎回生成する
val it : seq<int list> = seq [[0]; [0; 1]; [0; 1; 2]; [0; 1; 2; 3]]

> seq { for x in 0..3 do yield! [0..x] };; // 0からxまでのリストを毎回生成してそれをリスト内に展開する
val it : seq<int> = seq [0; 0; 1; 0; 1; 2; 0; 1; 2; 3]

1.3.6. while

while bool式 do シーケンス式

これは通常のwhile式と同じで、bool式trueを返す限りシーケンス式が何度も評価されます。

> let e = (System.IO.Directory.GetFiles(@"C:\") :> seq<string>).GetEnumerator();; // C:\直下のファイル一覧の列挙子を取得
val e : System.Collections.Generic.IEnumerator<string>

> seq { while e.MoveNext() do yield e.Current };; // 列挙子がfalseを返すまで値を取得する
val it : seq<string> =
  seq ["C:\.rnd"; "C:\autoexec.bat"; "C:\config.sys"; "C:\hiberfil.sys"; ...]

> seq { while true do yield 0 };; // 無限に続く0のシーケンスを作成する
val it : seq<int> = seq [0; 0; 0; 0; ...]

1.3.7. if

if bool式 then シーケンス式
if bool式 then シーケンス式0 else シーケンス式1

上の式ではbool式trueのときのみシーケンス式が評価されます。もしfalseだった場合は、空のシーケンスが生成されることになります。下の式ではbool式trueのときにシーケンス式0が評価され、falseのときにシーケンス式1が評価されます。

> seq { if false then yield 10 };; // falseのときは空のシーケンスになる
val it : seq<int> = seq []

> seq { if true then yield 10 };; // trueのときはyield 10が評価される
val it : seq<int> = seq [10]

> seq { if true then yield -1 else yield 1 };; // trueのときはyield -1が評価される
val it : seq<int> = seq [-1]

1.3.8. match

match  with パターン0 -> シーケンス式0 [ | パターンi -> シーケンス式i ]+

これは通常のmatch式と同様、パターンにマッチした場合に、その矢印の右側のシーケンス式が評価されます。

> seq { match [2;3] with [x] -> yield x | [x;y] -> yield x + y | _ -> yield 0 };; // 2番目のパターンにマッチ
val it : seq<int> = seq [5]

1.3.9. let

let 識別子 =  in シーケンス式
let パターン =  in シーケンス式

これは通常のlet束縛と同じで、識別子に束縛します。パターンが指定された場合は、パターンをパターンマッチし、成功したらパターン内の識別子に値を束縛します。ここで束縛した識別子は、シーケンス式の中で使うことができます。また、軽量構文では改行記号によってinを省略することができます。

> seq { let n = 5 in yield! [0..n] };; // 5をnに束縛
val it : seq<int> = seq [0; 1; 2; 3; 4; 5]

> seq { let (x,y) = (2,3) in yield! [x+y; x*y] };; // (x,y)というパターンにマッチさせ、xとyを同時に束縛
val it : seq<int> = seq [5; 6]

1.3.10. use

use 識別子 = IDisposableのインスタンス in シーケンス式
use パターン = IDisposableのインスタンス in シーケンス式

uselet束縛とほとんど同じように使うことができますが、ひとつ違う点があります。let束縛は任意の値に対して識別子を束縛することができましたが、useIDisposableインターフェイスを実装したものにしか識別子を束縛することができません。このuseによって束縛された値は、そのスコープが終了する際にIDisposable.Dispose()が呼び出されて、リソースが開放されます。

通常のlet束縛によって束縛された値も、誰からも参照されなくなればガーベッジコレクタによって開放されますが、その開放されるタイミングを予測することは困難です。したがって、ファイルやデータベースへのコネクションなど、その時点で確実に開放しておきたいものの場合には、letではなくuseを使って識別子を束縛するべきです。

> let lines = seq {
  use f = new System.IO.StreamReader(@"C:\Projects\FSharp\test.fs")
  while not f.EndOfStream do yield f.ReadLine()
};; // 要求されるたびにファイルの内容を1行ずつ返すシーケンス
val lines : seq<string>

> lines.MoveNext();;
val it : bool = true
> e.Current;;
val it : string = "#light"
> e.MoveNext();;
val it : bool = true
> e.Current;;
val it : string = ""
> e.MoveNext();;
val it : bool = true
> e.Current;;
val it : string = "module Test"

1.3.11. 通常の式とシーケンス式の結合

 ; シーケンス式
シーケンス式 ; 

通常のF#の式もシーケンス式と結合することができ、その結合された式全体が1つのシーケンス式となります。この結合されたシーケンス式も左から順番に評価されますが、それぞれのunit型でなければなりません。シーケンス式同士の結合の場合と同様、軽量構文では改行記号でセミコロンを省略することができます。

> let s = seq { printfn "hello" ; yield 10 };;
val s : seq<int>

> let s = seq { yield 10; printfn "hello" };;
val s : seq<int>

> let s = seq { printf "hello"; yield 10; printf "world"; yield 20; printfn "!" };;
val s : seq<int>

1.3.12. try-finally

try シーケンス式 finally 

これは後の章で紹介する例外処理のtry-finally式と同じで、シーケンス式の評価が終わったら、次に必ずが評価されます。シーケンス式の評価中に例外が発生した場合でも、必ずは評価されます。

> seq {
  try
    use f = new System.IO.StreamReader("") // ファイル名が空なのでここで例外が発生する
    yield f.ReadLine()
  finally
    printfn "hello, world!" // 例外が発生しても必ずこの式は評価される
};;
hello, world!
val it : seq<string> = Error: パス名を空にすることはできません。

1.4. Seqモジュール

F#標準ライブラリのMicrosoft.FSharp.Collections名前空間の下には、コレクションを操作するためのモジュールがいくつか定義されています。ここで定義されているモジュールにはArray、List、Map、Set、Seqなどがあり、各モジュールではそれぞれ異なる種類のコレクションを扱う関数が定義されています。この中でも特に注目すべきモジュールは、Seqモジュールです。Seq以外のモジュールでは、リスト、配列、集合といった具体的なコレクションの型を扱うのに対し、Seqモジュールでは、抽象的なコレクションインターフェイスであるseq<'T>(すなわちIEnumerable<T>)を扱います。

したがって、Seqモジュールはコレクション(つまりseq<'T>を実装するもの)であればどのようなものでも扱うことができます。例えば、リストや配列といった具体的なコレクションから、無限リストやジェネレータのようなメモリ上に実体のない抽象的なコレクションまで幅広く扱うことができます。

またこのSeqモジュール内の関数は、コレクションをseq<'T>インターフェイス経由で扱います。これにより、ジェネレータを扱う場合でも「要求されるたびに値を生成する」という性質を保存したまま、そのジェネレータを加工することができます。例えば以下の例を見てください。

> let x = seq { while true do yield 2 };; // 2が無限に続くコレクション(ジェネレータ)
val x : seq<int>

> x;; // 値を確認
val it : seq<int> = seq [2; 2; 2; 2; ...]

> Seq.map ((*) 5) x;; // 各要素に5を掛けたコレクション(ジェネレータ)を生成する
val it : seq<int> = seq [10; 10; 10; 10; ...]

まず1番目の入力で2が無限に生成するジェネレータを生成し、2番目の入力でその内容を確認しています。3番目では、Seqモジュール内のmap関数を使って各要素を5倍したジェネレータを生成しています。F#インタプリタはコレクションの要素が多すぎて表示しきれない場合は、先頭の数個だけ表示して後は省略するため、無限に続くシーケンスは途中で表示が打ち切られます。

もし、Seq.mapが与えられたコレクションをジェネレータとして扱わずに、無限個の要素をすべて処理しようとしたならば、無限ループに陥ってプログラムは停止しなくなるはずですが、Seq.mapはそれを正しく処理できていることがわかります。なぜこのようなことが可能なのでしょうか。

この不思議な性質を考える上で重要なのは、シーケンスは具体的な値でなく「規則」を保持しているということです。つまり上記の例は、「毎回2を生成する」という規則の後に「要素に5を掛ける」という規則が付け足されたと考えることができます。こう考えれば、無限に続くコレクションの加工も自然に考えることができます。

とはいっても、無限に続くコレクションは常に上手く扱えるわけではなく、不用意に扱ってしまうと無限ループに陥ってしまいます。例えば以下のような操作をすると、無限ループに陥ってプログラムが停止しなくなります。

> let x = seq { while true do yield 2 };; // 2が無限に続くコレクション(ジェネレータ)
val x : seq<int>

> Seq.length x;; // xの長さを求める

- Interrupt ← Ctrl+Cで強制的に停止させた

ここでは、Seq.lengthにより無限リストの長さを求めようとしています。この関数の内部では、長さを求めるために列挙子のMoveNext()falseを返すまでループを回し続けますが、無限リストなのでfalseが返ることはなく、結局無限ループになってしまいます。このように、無限リストを扱う場合は無限ループに陥らないように注意してください。

Seqモジュールには他にもいくつもの関数がありますが、ここではその一部を紹介します。

関数シグネチャ 概要 
val append : seq<'T> -> seq<'T> -> seq<'T>第1引数のコレクションの末尾に、第2引数のコレクションを連結した、新たなコレクションを生成する
val cast : IEnumerable -> seq<'T>IEnumerableインターフェイスをもつコレクションを、ジェネリックバージョンのIEnumerable<'T>インターフェイス(すなわちseq<'T>)をもつコレクションに変換する
val choose : ('T -> 'U option) -> seq<'T> -> seq<'U>第2引数のコレクション(seq<'T>)の各要素に対して、第1引数の関数('T -> 'U option)を適用して新たなコレクション(seq<'U>)を生成する。ただし、適用した結果がNoneの要素は新たなコレクションに追加しない。
val empty<'T> : seq<'T>空のシーケンス(要素の型は'T)を作成する。
val init : int -> (int -> 'T) -> seq<'T>第1引数(int)で指定された要素数をもつシーケンスを作成する。ただし各要素の初期化には、第2引数に渡された関数(int -> 'T)が用いられる。この第2引数の関数は、要素番号を受け取り、その番号に応じて要素を初期化する。。
val initInfinite : (int -> 'T) -> seq<'T>無限個の要素をもつシーケンスを作成する。ただし各要素の初期化には、第2引数に渡された関数(int -> 'T)が用いられる。この第2引数の関数は、要素番号を受け取り、その番号に応じて要素を初期化する。
val of_array : 'T array -> seq<'T>'T型の要素をもつ配列から、'T型の要素をもつシーケンスを作成する。。
val of_list : 'T list -> seq<'T>'T型の要素をもつリストから、'T型の要素をもつシーケンスを作成する。
val tryFind : ('T -> bool) -> seq<'T> -> 'T optionシーケンスの中から、第1引数の述語('T -> bool)を満たす最初の要素を見つけてその値をSomeに包んで返す。もし見つからなかった場合はNoneを返す。
  

Seqモジュール内の関数一覧はこちらのサイトに書かれています。

1.5. 配列、リストにおけるシーケンス式

ここまでに紹介してきたように、配列やリストを作成する場合は、基本的には[1,2,10,100][|3.1,5.0,-20.0|]['a'..'c']といったように、基本的にはそこに含まれる要素すべてを書き下します。一方シーケンスを作成する場合は、要素を書き下していくのではなくシーケンス式によって「規則」を書きます。

この違いは、数学の集合論における「外延的記法」と「内包的記法」に似ています。この2つの記法はどちらも、ある集合がどういった元(要素)から構成されているかを表現するためのものです。外延的記法はその集合に含まれる元を単純にすべて列挙していく直接的な記法であり、内包的記法はその集合に含まれる元が満たすべき条件を書く間接的な記法です。

たとえば、1と3と5という3つの元を含む集合を外延的記法で書くと{ 1, 3, 5 }と表現でき、内包的記法で書くと{ x | xは正の整数 かつ 0 < x ≦ 5 かつ x は奇数 }と表現できます。このような数個の元しかもたないような集合を表記する場合には外延的記法で十分ですが、ある規則性に従って生み出されるような巨大な集合を表記する場合には内包的記法でないと手に負えなくなります。

シーケンス式はちょうど内包的記法に相当し、ある規則性によって生み出されるコレクションを表現する場合に大変便利です。そこでF#では、配列やリストを作成する場合でもシーケンス式を使うことを許可しています。実際に例を見てみましょう。

> [ for x in 1..10 do yield x * x ];; // シーケンス式によってリストを作成
val it : int list = [1; 4; 9; 16; 25; 36; 49; 64; 81; 100]

> [| for x in 1..10 do yield x * x |];; // シーケンス式によって配列を作成
val it : int array = [|1; 4; 9; 16; 25; 36; 49; 64; 81; 100|]

> [| for x in 7..9 do yield! [x;x;x] |];; // シーケンス式によって配列を作成
val it : int array = [|7; 7; 7; 8; 8; 8; 9; 9; 9|]

このように、シーケンス式を用いてリストや配列を作成できることがわかります。ただし、ここで気をつけなくてはいけないのは、リストや配列は「ジェネレータ」ではないために要素がすべて一気にメモリ上に展開されてしまうという点です。つまりコレクションに含まれる要素が非常に多い場合は、その分メモリを圧迫することになります。さらに、無限個の要素を持つような配列やリストを生成しようとすると、そこで無限ループに陥ってしまうので注意が必要です。以下は無限ループに陥ってしまう例です。

> [ while true do yield 0 ];; // 0が無限に続くリストを作成しようとする

- Interrupt ← Ctrl+Cで強制的に停止させた

2. リスト処理

2.1. リストの基本

以前の章でリストを初めて紹介した際に、リストは関数型言語特有のデータ構造であり、関数型プログラミングではよく利用されると説明しました。ここではその理由を説明すると同時に、リストの特性を利用した非常に便利なデータ処理のテクニックを紹介していきます。また、ここで学んだテクニックはリストだけでなくシーケンス式を書くときにも非常に役に立ちます。

まず、リストは以下の図に示すような構造を持ちます。

この図を見るとわかるように、リストはデータ構造としては単方向リンクトリストと呼ばれるデータ構造を持っています。このような単方向リンクトリスト自体は、よくC言語やC#などの命令型言語でもよく実装される有名なデータ構造ですが、そのデータ構造を扱う方法が根本的に異なります。命令型言語で実装する単方向リンクトリストは、基本的に「可変なデータ(mutable data)」として扱われるため、要素の内容を書き換えたり、要素が指す先を書き換えたりしながら処理をするのが当たり前です。

ところが関数型言語におけるリストは、データの構造自体は命令型言語における実装と同じなのですが、それを「不変なデータ(immutable data)」として扱います。すなわち一度作ったリストは、その内容が後から書き換えられるということがありません。もし、そのリストの内容を加工したいと思った場合は、元のリストの内容を書き換えるのではなく、元のリストは残したまま新たなリストを生成するというアプローチをとります。

しかし、一見するとそのような方法はあまりに効率が悪く、とても実用的にはならないように聞こえます。たしかに巨大なデータを加工して、まったく異なる別の巨大なデータを生み出すような場合には向いていませんが、不変性は使い方によってはそれを補って余りある便利な性質となります。たとえば、不変性が保証されているデータ構造には排他処理が不要となるため、一切待ちが生じない高速なデータ構造を実現することが可能となります。

ここからは、さらに詳しくリストの構造を見ていきましょう。F#のリストは、実は内部的にはdiscriminated unionを使って実装されています。ここでいきなりその定義を示してもよいのですが、その定義は少々複雑なので、ここではそのリストの定義を自分で一から導出しながら説明をしていきます。

単方向線形リストにおけるそれぞれの要素は、以下の図に示すように「自分自身の値」と「後続するリストへの参照(ポインタ)」を持っています。

これらを1つ1つ連結していくことで可変長のデータ列を表現します。

そしてこのデータ列の終端には、終端を示す特殊な要素(番兵)を置きます。ここではこの終端の要素のことをNilと呼ぶことにします。Nilは値を含まず後続リストへの参照も持たない特殊な要素です。

このデータ構造は、discriminated unionを使うと以下のように表現できます。

type my_list =
  | Nil
  | Cons of int * my_list

このdiscriminated unionは、NilConsという2つのメンバを持ちます。Nilは先ほど説明したようにリストの終端を示す特殊な要素です。一方Consは、「自分自身の値」と「後続するリストへの参照」の2つ組タプルをパラメータに持つメンバです。ここが勘違いしやすいのですが、Consが持つのは「後続するリストへの参照」であって「次の要素への参照」ではないことに注意してください。つまり、

のように次の要素だけを指しているというイメージではなく、

のように後続するリスト全体を指しているというイメージで捉えてください。ここで、このdiscriminated unionを使って上の図のリストを表現してみましょう。まず、空のリストはNilだけを含みますから次のように書けます。

> Nil;;
val it : my_list = Nil

次に7を1つだけ含むリストを表現すると以下のようになります。

> Cons(7,Nil);;
val it : my_list = Cons (7,Nil)

このタプルの1番目がリストの要素の値を表現しており、2番目が後続するリストへの参照です。この場合の後続するリストは、Nilだけで構成されるリスト、すなわち空のリストです。

今度は、上の7を追加したリストにさらに31を追加します。

> Cons (31,Cons (7,Nil));;
val it : my_list = Cons (31,Cons (7,Nil))

このタプルの1番目にはリストの要素の値である31が入り、2番目には後続するリスト(Cons (7,Nil))が入っています。

同様にしてすべての要素をつなげると、以下のようになります。

> Cons (3,Cons (10,Cons (31,Cons (7,Nil))));;
val it : my_list = Cons (3,Cons (10,Cons (31,Cons (7,Nil))))

これで上の図を表現するリストが完成しました。Consが多くて見にくいですが、意味的には正しく上の図を表現できています。

ところで、このリストにはint型のデータしか格納することができません。実際のリストは任意の型のデータを格納することができるので、先ほどのdiscriminated unionの定義に対してジェネリックを使って汎用的なリストにすると、以下のような定義に書き直せます。

type 'T my_list =
  | Nil
  | Cons of 'T * my_list // 'Tと'T my_listのタプル

このリストの定義を使って、実際にいくつかの型のリストを作ってみましょう。

> Cons (3,Cons (10,Cons (31,Cons (7,Nil))));; // 上と同じint型のリスト
val it : int my_list = Cons (3,Cons (10,Cons (31,Cons (7,Nil))))

> Cons ("Hello,",Cons ("World!",Nil));; // string型のリスト
val it : string my_list = Cons ("Hello,",Cons ("World!",Nil));;

> Cons (3.14, Cons (2.718, Cons (1.4142,Nil)));; // float型のリスト
val it : float my_list = Cons (3.14,Cons (2.718,Cons (1.4142,Nil)))

相変わらずConsが多くて見にくいですが、どれも正しくリストを表現しています。実はF#のリストも、内部的にはこれとほとんど同じ実装になっています。実際にリストを使うときは、[3; 10; 31; 7]と書くだけですむので内部的な実装はわからないのですが、実際には上記のようなdiscriminated uninoによる定義に変換されています。ただし実際のリストでは、Nilの代わりに[]という記号が使われ、Consの代わりに::という記号が使われます。従って、実際のリストの定義は以下のようになります。

type 'T list =
  | ([])
  | (::) of 'T * 'T list

この2つのメンバを直接使って、最初のint型のリストを作ると以下のようになります。

> 3 :: (10 :: (31 :: (7 :: [])));;
val it : int list = [3; 10; 31; 7]

F#インタプリタの応答を見てください。これは今まで使ってきたF#のリストそのものです。ちなみに演算子の優先順位によって、余分な括弧は省略できるため、以下のようにもうすこしすっきり書くことができます。

> 3 :: 10 :: 31 :: 7 :: [];;
val it : int list = [3; 10; 31; 7]

他の型のリストも以下のように書くことができます。

> "Hello," :: "World!" :: [];;
val it : string list = ["Hello,"; "World!"]

> 3.14 :: 2.718 :: 1.4142 :: [];;
val it : float list = [3.14; 2.718; 1.4142]

2.2. リスト処理テクニックの応用範囲

前小節で紹介したように、リストは内部的には再帰的なdiscriminated unionによって定義されています。したがって、そのリストを処理するには再帰関数を使うとすっきりと書くことができます。またリスト処理のテクニックは、この章の最初に説明したシーケンスを使う場合にも応用することができます。なぜならばシーケンスもリストと同じように、先頭から順番にしか要素を取り出せないという性質を持ち、シーケンスを書く際にはリスト処理の考え方をそのまま適用することができるからです。ここでは、よく知られているさまざまなリスト処理の基本を紹介していきます。

まずは、単純にリストの長さを求める関数を示します。

> let rec length lst =
    match lst with
    | [] -> 0
    | x::xs -> 1 + length xs;;

val length : 'a list -> int

この再帰関数は、まずmatch式によって処理内容を振り分けます。空のリストに対しては長さ0を返し(base case)、そうでない場合は後続するリストの長さに1を足したものを返します(induction step)。ここで注目すべきなのは、マッチ式における2番目のパターン(x::xs)です。これは、パターンマッチのところでも少し紹介しましたが、consパターン(cons pattern)と呼ばれるもので、リストを「先頭の要素」と「後続するリスト」に分解してマッチさせるパターンです。この例の場合xが先頭の要素を表し、xsが後続するリストを表しています。このときのxxsの型に注意してください。xは先頭の要素だけを示すので'a型、xsは後続するリストを表現するので'a list型です。

このように再帰関数を使うと、長さを求める関数を簡潔に定義することができます。ここで、この関数の実行時のコストについて考えて見ましょう。ここでいうコストとは、実行時にどれくらい多くの時間およびメモリを消費するかということを意味します。空のリストに対するパターンマッチは単純で、ほとんどコストはかからないことはすぐわかると思います。一方consパターンは、リストを「先頭の要素」と「後続するリスト」に分解します。前小節で紹介したように、リストは単方向リンクトリストになっているため、この分解処理は単純で余分なメモリも食うことはないため、これにもコストはほとんどかかりません。

ここで、この長さを求める関数の配列バージョンを、まったく同じ再帰で書くことを考えてみます。まず、空の配列はすぐにチェックできます。一方、配列が空でなかった場合は「先頭の要素」と「後続する配列」に分解する必要があります。これらの処理のコストを考えてみると、先頭の要素の取り出しにはほとんどコストがかからないのに対して、「後続する配列」を作るのはその分だけ配列のコピーを作らなければならないため、大きなコストがかかりそうです。しかもこの後続する配列の作成は、毎回の再帰呼び出しのたびに発生するため、大きな配列の場合は無視できないレベルのコストが発生します。以上の理由から、再帰的な記述を好む関数型言語で何らかのコレクションを扱う場合には、配列として扱うよりもリストとして扱う方が適していることがわかります。

また、リストには他にも大きなメリットがあります。それは先ほども少し述べましたが、並列処理を記述する場合です。節の冒頭で、リストは「不変なデータ」であると書きました。これはすなわち、一度そのリストを作ったらそのリストの要素の値は書き換えられることがなく、各要素の参照している後続リストも変わらないことが保証されているということです。もしリストが可変なデータならば、複数のスレッドから同時にアクセスする際にはきちんと排他制御を行わなければならず、もし行わないと運悪くリストの書き換え中にアクセスしてしまった場合などに予期しない結果になる可能性があります。しかし不変なデータの場合はそもそも排他制御をする必要はないため、用途によっては非常に効率のよいデータ構造を実現することができます。

この不変なデータを用いた実装テクニックは、マルチスレッドにおけるデザインパターンであるImmutableパターン(Immutable pattern)としても知られており、実は古くから非常に身近なところで利用されています。予想外で驚くかもしれませんが、そのひとつの例が.NET Frameworkの文字列クラスであるSystem.Stringクラスです。System.Stringクラス、すなわち通常のstring型は、一度そのインスタンスを生成したら中の文字列を書き換えることはできません。

このことを今まで意識していなかった方は、System.Stringクラスは中身を書き換えられるクラスだと思い込んでいたのではないでしょうか。もしこのことを疑うならば、実際にMSDNドキュメントでSystem.Stringクラスの説明を見てください。クラスの解説にもはっきりと「String オブジェクトは、作成時点以降に値を変更できないことから、不変 (読み取り専用) と呼ばれます。」と記述されています。また、このクラスの各メソッドを見てみても中の文字列を書き換えるものはありません。Removeメソッドなどの一部のメソッドの説明では、中身を書き換えると誤解を与えるようなものもありますが、実際に詳しく見てみるとどれも既存の値を書き換えるのではなく「新たな文字列を生成するメソッド」に過ぎないということがわかるとおもいます。

2.3. リスト処理の基本

関数型言語では古くからリストが扱われており、そのリスト処理のテクニックは非常にバリエーションに飛んでいます。ここでは、その中でも基本であるmap、filter、foldによるリスト処理テクニックを紹介します。map、filter、foldは非常に汎用性がある高階関数で、これらの組み合わせでかなり多くの再帰的なリスト処理を表現することができます。

Note

foldという関数は、別の言語ではreduceという名前がつけられている場合があります。

mapとreduceと聞くと、Googleの並列分散処理フレームワークであるMapReduceを思い浮かべる方がいるかもしれませんが、MapReduceは実際にこの関数型言語のmapとreduceに影響を受けて作られました。

この3つの関数を紹介したあとは、さまざまなリスト処理がこれらの組み合わせで実現できることを示します。

2.3.1. map - 各要素を処理する

最初に紹介するのは、与えられたリストから1つずつ要素を取り出し、それらの値を1つずつ処理する再帰関数の例です。

// 各要素の値を2乗する関数
let rec square lst =
  match lst with
  | x::xs -> (x*x) :: square xs
  | [] -> []

// 各要素の値の絶対値をとる関数  
let rec abs_list lst =
  match lst with
  | x::xs -> abs x :: abs_list xs
  | [] -> []

// 各要素の値を画面に出力する関数
let rec print_elements lst =
  match lst with
  | x::xs -> printfn "%d" x :: print_elements xs
  | [] -> []

これらの関数の実行例は以下のようになります。

> square [1..5];;
val it : int list = [1; 4; 9; 16; 25]

> abs_list [1;-10;5;3;-2;-7];;
val it : int list = [1; 10; 5; 3; 2; 7]

> print_elements [1..5];;
1
2
3
4
5
val it : unit list = [null; null; null; null; null]

この3つの関数の定義をよく見ると、非常によく似ていることがわかります。本質的に異なるのは太字で示した部分のみです。この共通部分を何とかしてまとめることはできないでしょうか。とりあえずこの太字部分を取り出して並べてみましょう。

x * x
abs x
printf "%d, " x

これらはどれもリストの先頭の値xを受け取り、その値に対して処理を行う1引数関数です。これらの関数を、実際の上の関数定義野中から1引数関数としてくくり出してみましょう。

// くくりだした関数
let f1 x = x * x
let f2 x = abs x
let f3 x = printfn "%d" x

// 各要素の値を2乗する関数
let rec square lst =
  match lst with
  | x::xs -> f1 x :: square xs
  | [] -> []

// 各要素の値の絶対値をとる関数  
let rec abs_list lst =
  match lst with
  | x::xs -> f2 x :: abs_list xs
  | [] -> []

// 各要素の値を画面に出力する関数
let rec print_elements lst =
  match lst with
  | x::xs -> f3 x :: print_elements xs
  | [] -> []

このようにくくり出してみると、再帰関数squareabs_listprint_elementsはどれも全く同じ処理で、異なるのは関数名だけであることがわかります。そこでこの共通している部分を、ひとつの関数mapとして抜き出すことにします。このmapは各要素に対して適用すべき関数を、第1引数fとして受け取ります。

let rec map f lst =
  match lst with
  | x::xs -> f x :: map xs
  | [] -> []

このmapを使うと、先ほどの3つの再帰関数は次のように書きかえることができます。

// くくりだした関数
let f1 x = x * x
let f2 x = abs x
let f3 x = printfn "%d" x

let rec map f lst =
  match lst with
  | x::xs -> f x :: map xs
  | [] -> []

// 各要素の値を2乗する関数
let square lst = map f1 lst

// 各要素の値の絶対値をとる関数  
let abs_list lst = map f2 lst

// 各要素の値を画面に出力する関数
let print_elements lst = map f3 lst

さらにf1f2f3は短い関数なので、ラムダ式を使って関数定義の中に直接埋め込んでしまいましょう。

let rec map f lst =
  match lst with
  | x::xs -> f x :: map xs
  | [] -> []

// 各要素の値を2乗する関数
let square lst = map (fun x -> x * x) lst

// 各要素の値の絶対値をとる関数  
let abs_list lst = map (fun x -> abs x) lst

// 各要素の値を画面に出力する関数
let print_elements lst = map (fun x -> printfn "%d" x) lst

これでひとまず完成です。このようにmapという関数を定義することで、リストの各要素を処理するコードを簡潔に記述することができました。これは関数型プログラミングでは非常に基本的なテクニックであるため、ほとんどの関数型プログラミング言語では標準ライブラリですでにmap関数が定義されています。実はF#でもリストに対するmap関数であるList.mapが定義されています。これはF#標準ライブラリにあるListモジュールの中にあるmap関数です。

F#ではリスト以外にも、配列に対するmap関数(Array.map)やシーケンスに対するmap関数(Seq.map)といった、ほかのいくつかのコレクション型に対するmap関数が用意されています。この標準ライブラリのList.mapを利用することで、上のコードは最終的に次のように1行で定義することが可能になります。

// 各要素の値を2乗する関数
let square lst = List.map (fun x -> x * x) lst

// 各要素の値の絶対値をとる関数  
let abs_list lst = List.map (fun x -> abs x) lst

// 各要素の値を画面に出力する関数
let print_elements lst = List.map (fun x -> printf "%d, " x) lst

ここで上のList.mapに渡している3つの関数の型について考えると、それぞれ以下のような型になっていることがわかります。

fun x -> x * x // int -> int
fun x -> abs x // int -> int
fun x -> printf "%d, " x // int -> unit

1番目と2番目はint -> intという関数なので、これを使ってList.mapを呼び出すと「intのリスト」から新たな「intのリスト」を生み出します。一方、3番目はint -> unitという関数を渡すため、「intのリスト」から新たな「unitのリスト」を生み出します。1番目と2番目では呼び出しの結果として「intのリスト」を得ることが目的ですが、3番目の場合は関数を呼び出すことによる副作用(画面に文字を出力する)が目的であり、最終結果として出てくる「unitのリスト」は単なる副産物に過ぎません。したがって、ここで生成されるunitのリストは破棄してしまってもかまいません。

命令型プログラミングの章でも説明しましたが、関数型言語では不変性を用いたプログラミング(すなわち副作用を持たないプログラミング)が好まれ、副作用を伴う箇所には何らかの「しるし」がつきます。たとえばある関数が副作用を持つかどうかは、その戻り値を見ることで(100%ではありませんが)ある程度判断することができます。一般的には、戻り値がunitの場合は副作用を持ち、何らかの値を返す場合は副作用を持たないという判断することができます。ただし、何らかの値を返す関数でも中に無理やり副作用を持ち込むこともできますし、逆にunitを返す関数でも副作用を持たないようにもできます。したがって、この戻り値による判断は絶対的なものではありませんが、多くの場合はよい判断基準となります。

上の3番目の関数のように、各要素を1つずつ処理したいけれども、各要素を処理した後の戻り値に興味があるのではなく、各関数呼び出しにおける副作用に興味がある場合には、List.mapのかわりにList.iterというものを使うことができます。List.iterは基本的にList.mapと同じ処理を行いますが、副作用を起こす関数を第1引数に取り、戻り値を自動的に破棄するところが違います。この2つの違いを比べるために、List.mapList.iterの型を見てみましょう。

> List.map;;
val it : (('a -> 'b) -> 'a list -> 'b list) = <fun:clo@0-1>
> List.iter;;
val it : (('a -> unit) -> 'a list -> unit) = <fun:clo@0-2>

List.mapの引数の意味は、それぞれ「各要素に適用する関数 -> 入力リスト -> 出力リスト」というイメージであり、List.iterの引数の意味は「各要素に適用する(副作用をもつ)関数 -> 入力リスト -> unit」となっています。これによりList.mapを呼び出した最終結果として出力リストが返されますが、List.iterでは特に戻り値を返す必要がないため単純にunitが返されます。

このように関数のシグネチャを見るだけでも、List.mapは各要素に対して副作用を持たない処理を行って新たなリストを生成するはたらきをし、List.iterは各要素に副作用を持つ処理を行い戻り値自体は不要なので破棄するというはたらきをすると予想することができます。F#では、このようにして関数が副作用をもつかどうかを(ある程度)判断することができます。

Note

純粋関数型言語であるHaskellでは、副作用が発生する部分にしるし(IOモナド)をつけることが「必須」になります。もししるしをつけない場所があると、コンパイルエラーとなりコンパイルが通りません。したがって、Haskellのコードでは副作用の有無を完全に見分けることができます。

このように聞くと、なぜF#でもそのような方針にしなかったのかと思うかもしれませんが、Haskellにおけるその副作用の完全な分離を実現するためのしるしは取り扱いが難しく、そう簡単に理解できるものではありません。そこでF#では難解な概念による完璧な副作用の分離よりも、副作用の分離に関して多少妥協をして扱いやすくしています。

2.3.2. filter - 条件に一致する要素を抜き出す

次に紹介するのは、リストの中からある条件に一致する要素だけを抜き出して新しいリストを作りだす例です。

// リストの中から指定されたキーワードに前方一致する文字列を抜き出す
let rec find_match_strings_forward (word:string) (lst:string list) =
  match lst with
  | x::xs ->
    if x.StartsWith(word) then x::(find_match_strings_forward word xs)
    else find_match_strings_forward word xs
  | [] -> []

// リストの中から指定されたキーワードに後方一致する文字列を抜き出す
let rec find_match_strings_backward (word:string) (lst:string list) =
  match lst with
  | x::xs ->
    if x.EndsWith(word) then x::(find_match_strings_backward word xs)
    else find_match_strings_backward word xs
  | [] -> []

// リストの中から奇数を抜き出す
let rec extract_odd_numbers (lst:int list) =
  match lst with
  | x::xs ->
    if x % 2 = 1 then x::(extract_odd_numbers xs)
    else extract_odd_numbers xs
  | [] -> []

この例では、本質的に異なるのは太字で示した部分(述語)のみです。そこで先ほどのmapと同じように、共通部分を抜き出してみましょう。この抜き出した関数は「あるリストから条件に合致するものを取り出す」という働きをするので、filterという名前を付けます。

let rec filter (f:'a -> bool) (lst:'a list) =
  match lst with
  | x::xs ->
    if f x then x::(filter f xs)
    else filter f xs
  | [] -> []

filterは第1引数に述語を受け取り、第2引数にリストを受け取ります。この述語は'a型の値を受け取り、bool値を返します。また、リストは'a型のデータを保持するリストです。これを利用して先ほどの関数を書き換えてみましょう。

let rec find_match_strings_forward (word:string) (lst:string list) = filter (fun (x:string) -> x.StartsWith(word)) lst

let rec find_match_strings_backward (word:string) (lst:string list) = filter (fun (x:string) -> x.EndsWith(word)) lst

let rec extract_odd_numbers (lst:int list) = filter (fun x -> x % 2 = 1) lst

このようにすっきり書くことができました。実はこのfilter関数も、List.filterとして標準のListモジュールの中に定義されています。

2.3.3. fold - 畳み込み

次はあまり聞きなれない方もいるかもしれませんが、畳み込み(folding)と呼ばれる処理を紹介します。

Warning

信号処理理論の分野でも畳み込みという用語が出てきますが、こちらは英語ではconvolutionという言葉に相当し、関数型言語でいう畳み込み(folding)とはまた違う概念になるので注意してください。

ちなみにDictionary.comなどで英英辞典を引くと、foldという動詞はものを曲げたり折ったりするイメージですが、convolveという動詞はくるくると巻くイメージであると書かれています。

まずは以下の例を見てください。

// すべての要素を加算する
let rec sum (lst:int list) =
  match lst with
  | x::xs -> x + (sum xs)
  | [] -> 0

// すべての要素を掛ける  
let rec mul (lst:int list) =
  match lst with
  | x::xs -> x * (mul xs)
  | [] -> 1

// すべての要素のandをとる
let rec and_list (lst:bool list) =
  match lst with
  | x::xs -> x && (and_list xs)
  | [] -> true

// すべての要素のorをとる
let rec or_list (lst:bool list) =
  match lst with
  | x::xs -> x || (or_list xs)
  | [] -> false

// すべての文字列を連結する
let rec concat_string (lst:string list) =
  match lst with
  | x::xs -> x + (concat_string xs)
  | [] -> ""

// すべての要素から最大値を検索する
let rec find_max (lst:int list) =
  match lst with
  | x::xs -> max x (find_max xs)
  | [] -> System.Int32.MinValue

// すべての要素から最小を検索する
let rec find_min (lst:int list) =
  match lst with
  | x::xs -> min x (find_min xs)
  | [] -> System.Int32.MaxValue

// リストに含まれるtrueの要素を数える
let rec count_true (lst:bool list) =
  match lst with
  | x::xs -> (if x = true then 1 else 0) + (count_true xs)
  | [] -> 0

これらの関数定義はどれもほとんど同じ形をしており、本質的に異なるのは太字で示した部分のみです。この太字の部分を関数および値として抜き出してみましょう。

let sum_op : int -> int -> int = (+)
let sum_identity = 0

let mul_op : int -> int -> int = (*)
let mul_identity = 1

let and_list_op : bool -> bool -> bool = (&&)
let and_list_identity = true

let or_list_op : bool -> bool -> bool = (||)
let or_list_identity = false

let concat_string_op : string -> string -> string = (+)
let or_identity = ""

let find_max_op : int -> int -> int = max
let find_max_identity = System.Int32.MinValue

let find_min_op : int -> int -> int = min
let find_min_identity = System.Int32.MaxValue

let count_true_op : bool -> int -> int = fun elem sum -> (if elem = true then 1 else 0) + sum
let count_true_identity = 0

次に太字以外の共通部分を関数として抜き出してみましょう。ここでは、この共通部分にはfold_rightという名前をつけます(この名前の意味はすぐ後で説明します)。

let rec fold_right op identity (lst:'a list) =
  match lst with
  | x::xs -> op x (fold_right op identity xs)
  | [] -> identity

このfold_right関数の型は次のようになります。

val fold_right : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b

この型だけをみると一見非常に複雑に見えますが、これから以下の図でこのfold_rightという演算の動作イメージを理解すれば、悩むことなくすんなりと頭に入ってきます。fold_rightの動作は以下の図のように、ある初期値identityをもとにリストlstの各要素を2項演算子opを使い、右から順番につなぎ合わせていって、戻り値resultを得るというイメージです。

この図にfold_right関数の型を対応付けると以下のようになります。

まず初期値identity:'bを元にして、2項演算子op:'a->'b->'bを使って、lst:'a listの要素を末尾(右側)からひとつずつ合併吸収していき、最終結果result:'bを得ます。このような動作を畳み込み(folding)といいます。扇子の折り目を端から1段ずつ畳み込んでいくと、畳み込まれた部分が分厚くなっていき、最終的に1本の折りたたまれた扇子になるようなイメージです。

Note

数学における代数の言葉を知っている方は、上で抜き出したsummuland_listor_listconcat_stringfind_maxfind_minidentityopをよく見てみてください。たとえばsumに注目してみると、sum_op:int->int->intは集合int上の演算sum_opであり、sum_identity:intはその単位元であることがわかります。これは単位元が存在して結合法則を満たすためモノイドであると考えられます。さらに他の関数に関しても、それぞれがモノイドをなしていることがわかります。

このfold_rightを使ってこの小節の関数を再定義してみましょう。

let sum lst = fold_right (+) 0 lst
let mul lst = fold_right (*) 1 lst
let and_list lst = fold_right (&&) true lst
let or_list lst = fold_right (||) false lst
let concat_string lst = fold_right (+) "" lst
let find_max lst = fold_right max System.Int32.MinValue lst
let find_min lst = fold_right min System.Int32.MaxValue lst
let count_true lst = fold_right (fun elem sum -> (if elem = true then 1 else 0) + sum) 0 lst

このようにすっきり書くことができました。ここで例として、mul [3..5]という式がどのように展開されるかを考えてみましょう。(実際のF#の計算手順とは異なりますが)イメージとしては以下のように展開されていきます。

mul [3..5]
⇒ mul [3;4;5]
⇒ fold_right (*) 1 [3;4;5]
⇒ (*) 3 (fold_right (*) 1 [4;5])
⇒ (*) 3 (fold_right (*) 1 [4;5])
⇒ (*) 3 ((*) 4 (fold_right (*) 1 [5]))
⇒ (*) 3 ((*) 4 ((*) 5 1))
⇒ (3 * (4 * (5 * 1)))

最終的に展開された式を見ると、先ほど示した図のイメージのように演算子が糊の役割をしており、各要素と直前の計算結果が右から順番につなぎ合わさっていく様子がわかるとおもいます。

ここで自作したfold_right関数は、F#の標準ライブラリにおいてList.foldBackとして定義されています。ただし、先ほど自作したfold_rightとは第2引数と第3引数の順番が異なるので注意してください。

Note

F#の先祖であるOCamlでは、今回自作したfold_rightに相当するものがの標準ライブラリにList.fold_rightとして定義されています。F#においてもVisual Studio 2010 CTP以前のF#標準ライブラリでは、List.fold_rightという名前がつけられていましたが、CTP以降はList.foldBackという名前に置き換えられてしまいました。実は現在のバージョンのF#でも、OCamlとの互換性のためにList.fold_rightという名前を使うことができるのですが、実際に使用するとコンパイラやインタプリタから互換性のために残されているものであるとの警告が発生してしまいます。

List.foldBackは標準ライブラリでは以下のように定義されています。

val List.foldBack : ('T -> 'State -> 'State) -> 'T list -> 'State -> 'State

この定義と、先ど自作したfold_rightの定義を並べて書いてみましょう。

val List.foldBack : ('T -> 'State -> 'State) -> 'T list -> 'State -> 'State // 標準ライブラリ
val fold_right : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b // 自作

わかりやすいようにfold_rightの型変数名を、標準ライブラリの名前に合わせて書き換えるとこうなります。

val List.foldBack : ('T -> 'State -> 'State) -> 'T list -> 'State -> 'State // 標準ライブラリ
val fold_right    : ('T -> 'State -> 'State) -> 'State -> 'T list -> 'State // 自作

このように渡す関数の引数の順番が違っていますが、この違いは単純に定義方法の違いによるもので機能的な違いはありません。

最後の仕上げとして、fold_rightの代わりにList.foldBackを使って書き換えてみましょう。先ほどの定義とは、それぞれ第2引数と第3引数の順番が入れ替わっていることに注意してください。

let sum lst = List.foldBack (+) lst 0
let mul lst = List.foldBack (*) lst 1
let and_list lst = List.foldBack (&&) lst true
let or_list lst = List.foldBack (||) lst false
let concat_string lst = List.foldBack (+) lst ""
let find_max lst = List.foldBack max lst System.Int32.MinValue
let find_min lst = List.foldBack min lst System.Int32.MaxValue
let count_true lst = List.foldBack (fun elem sum -> (if elem = true then 1 else 0) + sum) lst 0

最終的に非常に簡潔に関数を定義することができました。

さて、ここまではリストを右側(末尾)から畳みこんでいく関数をみてきましたが、標準ライブラリには左側(先頭)から畳みこんでいく関数も定義されています。その関数はList.foldという名前で、以下のシグネチャを持ちます。

val List.fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State

Note

Visual Studio 2010 CTP以前のF#標準ライブラリおよびOCamlの標準ライブラリでは、List.foldのかわりにList.fold_leftという名前で定義されています。

上でList.foldBackを用いて定義したsummulなどの関数は、List.foldを用いても定義することができます。実際にList.foldを使って書き換えてみましょう。ここで第2引数と第3引数の順番が入れ替わっていることに気をつけてください。また、count_trueではラムダ式の引数も入れ替わっています。

let sum lst = List.fold (+) 0 lst
let mul lst = List.fold (*) 1 lst
let and_list lst = List.fold (&&) true lst
let or_list lst = List.fold (||) false lst
let concat_string lst = List.fold (+) "" lst
let find_max lst = List.fold max System.Int32.MinValue lst
let find_min lst = List.fold min System.Int32.MaxValue lst
let count_true lst = List.fold (fun sum elem -> (if elem = true then 1 else 0) + sum) 0 lst

ここで注意してほしいのが、List.foldBackは常にList.foldで書き換えられるわけではないということです。上の関数の場合はたまたまどちらを使っても書き換えることができましたが、一般には書き換えることはできません。

2.4. リスト処理の応用

ここでは前節で紹介したリスト処理のテクニックを利用して、実際のデータを処理する具体例をいくつか紹介します。前節では、Listモジュールにある関数を使ってリストを処理する方法を紹介しましたが、これらの関数はListモジュールだけでなくArrayモジュール(配列版)やSeqモジュール(シーケンス版)でも同じように定義されているため、map、filter、foldといったものを配列やシーケンスに対して適用することができます。

2.4.1. リスト処理の応用例1

まずはファイル情報を扱う例を紹介します。

open System.IO
open System.Text.RegularExpressions

// C/C++のソースファイル(*.cpp,*.hpp,*.h,*.c)かを判別する正規表現
let is_src_file name = Regex.IsMatch(name, ".*\.(cpp|hpp|h|c)$", RegexOptions.IgnoreCase)

// 指定したディレクトリ以下のすべてのソースファイルの情報を取得する関数
let rec get_src_files dir =
  // 現在のディレクトリ内のすべてのソースファイルの情報を取得
  let files =
    Directory.GetFiles dir     // ディレクトリ内のファイル名一覧を取得
    |> List.of_array           // 配列からリストに変換
    |> List.filter is_src_file // C/C++のソースファイル名だけを抽出
    |> List.map (fun filename -> new FileInfo(filename)) // ファイル名一覧からファイル情報一覧を生成
  // 下位のディレクトリに対しても再帰的に呼び出す
  let below_files =
    Directory.GetDirectories dir // ディレクトリ一覧を取得
    |> List.of_array             // 配列からリストに変換
    |> List.map get_src_files    // 各ディレクトリに対して再帰的に自分自身を適用
    |> List.concat               // 結果のリストを平滑化
  // 2つの結果を結合して返す
  List.append files below_files

これは指定したディレクトリ以下にあるC/C++ソースファイルの情報のリストを、list<FileInfo>として取得する関数get_src_filesです。ここで出てくるList.concatとは、list<list<'T>>というリストを平滑化してlist<'T>というリストを作る関数です。例えば、[[1];[2;3;4];[5];[];[6;7;8;9]] : list<list<int>>というリストに対して適用すると、[1;2;3;4;5;6;7;8;9] : list<int>というリストが作られます。

このプログラムでは、Listモジュール内のリスト処理関数群とパイプライン演算子(|>)を積極的に使っており、データ(ファイル情報の一覧)が加工されていく様子がよくわかります。F#におけるリスト処理ではこのようなプログラミングのスタイルはよく使われますが、このスタイルが自然だと感じるには多少の慣れが必要かもしれません。もし読んでいて混乱する場合は、リスト処理の格段において、どのような型のデータを受け取ってどのような型のデータが生成されるかに注目して読めばわかるはずです。例えばfilesを生成する部分の型を詳しく調べると、次のようになります。

let files : array<FileInfo> =
    Directory.GetFiles dir     // array<string>を生成
    |> List.of_array           // list<string> → array<string>
    |> List.filter is_src_file // array<string> → array<string>
    |> List.map (fun filename -> new FileInfo(filename)) // array<string> → array<FileInfo>

ここでget_src_files関数を利用したプログラムを書いてみます。例として、Visual Studio 2010に含まれるVisual C++のディレクトリ内にあるソースファイルの情報を調べてみましょう。Visual Studio 2010をインストールしていない方は、検索対象の拡張子やフォルダを適当に書き換えて試してみてください。

// Visual Studio 2010のVisual C++のディレクトリ以下にあるソースファイル一覧を取得
let src_files = get_src_files @"C:\Program Files\Microsoft Visual Studio 10.0\VC"

src_files
|> Array.of_list // リストを配列に変換
|> Array.sortBy (fun (x:FileInfo) -> x.Length) // ファイルサイズをキーにしてソート
|> Array.map (fun (x:FileInfo) -> (x.Name, x.Length)) // ファイル情報からファイル名とファイルサイズのタプルを生成
|> Array.iter (fun (name,length) -> printfn "%d\t%s" length name) // タプルの内容を1行ずつ表示

ここではListモジュールではなくArrayモジュールを中心に使用しています。ここでリストではなく配列を使う理由は、リストのままソートを行うとかなり時間がかかってしまうためです。しかしArrayモジュールにもmapやiterが定義されているため、リスト処理のテクニックがそのまま応用できます。

2.4.2. リスト処理の応用例2

次はリスト処理の基本で学んだテクニックをシーケンスに応用してみます。ここでは、エラトステネスのふるいという素数列を生成するアルゴリズムを使って、2からはじまる素数の列をもつシーケンスを構築する方法を解説します。ただし、ここで紹介するコードは簡潔さを優先して書いており、実行効率はかなり犠牲にしています。

エラトステネスのふるいは、次の手順に従って素数列を生成するアルゴリズムです。

  1. 2から始まる整数のリストを用意する。

    2, 3, 4, 5, 6, 7, 8,…

  2. リストを「先頭の値」と「残りの部分」に分ける。

    2, (3, 4, 5, 6, 7, 8, 9, 10,…)

  3. 「残りの部分」から「先頭の値」の倍数(2の倍数)を除去する。

    2, (3, 5, 7, 9, 11,…)

  4. (3, 5, 7, 9, 11…)の部分を、さらに「先頭の値」と「残りの部分」に分ける。

    2, 3, (5, 7, 9, 11, 13, 15, 17…)

  5. 「残りの部分」から「先頭の値」の倍数(3の倍数)を除去する。

    2, 3, (5, 7, 11, 13, 17…)

  6. この手順を繰り返すことで素数のリストを生成する。

    2, 3, 5, 7, 11,…

この手順をF#のシーケンスで実現してみましょう。まず2から始まる整数のシーケンスを作るには、Seq.initを使います。この関数はSeq.init : int -> (int -> 'a) -> seq<'T>という型をもっており、1番目の引数に生成する要素の数、2番目の引数に要素を生成する関数を渡します。2番目の関数は、1番目の引数で指定した回数呼び出され、各呼び出し時には引数に0、1、2…という値が順番に渡されます。これを利用すると、たとえば2から102までの整数のシーケンスは次のように作ることができます。

> Seq.init 100 (fun n -> n + 2);;
val it : seq<int> =
  seq
    [2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21;
     22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; ...]

次に必要になのは、シーケンスを「先頭の値」と「残りの部分」に分割する処理です。これらを実現するには、それぞれSeq.hd : seq<'T> -> seq<'T>Seq.skip : int -> seq<'T> -> seq<'T>を使います。Seq.hdはシーケンスの先頭の要素だけを取り出す関数で、Seq.skipはシーケンスを指定された数だけシーケンスの要素をスキップしたシーケンスを生成する関数です。

> let N = Seq.init 100 (fun n -> n + 2);; // 2から始まる整数列を生成
val N : seq<int>

> Seq.hd N;; // 先頭の要素を取り出す
val it : int = 2

> Seq.skip 1 N;; // 先頭の1要素をスキップした整数列のシーケンスを生成
val it : seq<int> =
  seq
    [3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22;
     23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; ...]

次はシーケンスから指定した値の倍数を除去します。これにはSeq.filterを使います。

> let N = Seq.init 100 (fun n -> n + 2);; // 2から始まる整数列を生成
val N : seq<int>

> Seq.filter (fun n -> n % 2 <> 0) N;; // Nから2の倍数を除去したシーケンスを生成
val it : seq<int> =
  seq
    [3; 5; 7; 9; 11; 13; 15; 17; 19; 21; 23; 25; 27; 29; 31; 33; 35; 37; 39;
     41; 43; 45; 47; 49; 51; 53; 55; 57; 59; 61; 63; 65; 67; 69; ...]

以上の結果を使って、2からmax_valueまでの整数列を生成する関数primes_toを定義します。

// 与えられた整数列nに対してエラトステネスのふるいを実行する
let rec primes_helper (n:seq<int>) =
  if Seq.isEmpty n then n
  else
    let hd = Seq.hd n // 先頭の要素をhdとして取り出す
    let tl = Seq.skip 1 n // 先頭を除いたシーケンスをtlとして生成
    let filtered = Seq.filter (fun x -> x % hd <> 0) tl // tlからhdの倍数を除去したシーケンスをtlとして生成
    Seq.append [hd] (primes_helper filtered) // filteredに対して再帰的にprimes_helperを呼び出してhdと結合

// 2からmax_valueまでの素数列のシーケンスを生成する
let primes_to max_value =
  let N = Seq.init (max_value-2) (fun x -> x + 2)
  primes_helper N

それでは実際にこの関数を使ってみましょう。

> primes_to 100;;
val it : seq<int> = seq [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.hdなどは、先頭の1要素しかアクセスしないので即座に処理が帰ってきますが、誤ってSeq.maxなどを適用してしまうと、すべての要素から最大値を探そうとするので永久に処理がかえって来ないことになります。

では、そのことに注意しながら無限の素数列を作ります。まず、整数列を生成するのにSeq.initではなくSeq.initInfinite : (int -> 'T) -> seq<'T>を使うようにします。この関数はSeq.initとは違って上限値を指定する必要がなく、無限に要素を作り出すことができます。といっても、インデックス番号はintで与えられており実際はそのintの限界に制限されてしまうため、ここではintの上限までの値を限界とするシーケンスを作ることにします。変更後のコードは以下のようになります。

// 与えられた整数列nに対してエラトステネスのふるいを実行する
let rec primes_helper (n:seq<int>) =
  if Seq.isEmpty n then n
  else
    let hd = Seq.hd n // 先頭の要素をhdとして取り出す
    let tl = Seq.skip 1 n // 先頭を除いたシーケンスをtlとして生成
    let filtered = Seq.filter (fun x -> x % hd <> 0) tl // tlからhdの倍数を除去したシーケンスをtlとして生成
    Seq.append [hd] (primes_helper filtered) // filteredに対して再帰的にprimes_helperを呼び出してhdと結合

// 2から始まるの無限の素数列のシーケンスを生成する
let primes =
  let N = Seq.initInfinite (fun x -> x + 2)
  primes_helper N

とりあえずはこの変更だけでうまくいきそうな気がします。ところが実際に実行してみると、無限ループに陥ってしまいます。どこが問題だったのでしょうか。といっても、この原因を突き止めるのは初学者には少々難しいかもしれないので答えをいってしまうと、primes_helperの最後の再帰呼び出しが無限ループの原因です(このあたりの説明は本章でも詳しく説明していないので、今は理解できなくても大丈夫です)。

これを防止するには、この無限ループに1クッションの遅延を入れる必要があります。その遅延を入れるには、Seq.delay : (unit -> seq<'T>) -> seq<'T>という関数を使います。

// 与えられた整数列nに対してエラトステネスのふるいを実行する
let rec primes_helper (n:seq<int>) =
  if Seq.isEmpty n then n
  else
    let hd = Seq.hd n // 先頭の要素をhdとして取り出す
    let tl = Seq.skip 1 n // 先頭を除いたシーケンスをtlとして生成
    let filtered = Seq.filter (fun x -> x % hd <> 0) tl // tlからhdの倍数を除去したシーケンスをtlとして生成
    Seq.append [hd] (Seq.delay (fun () -> primes_helper filtered)) // filteredに対して再帰的にprimes_helperを呼び出してhdと結合

// 2から始まるの無限の素数列のシーケンスを生成する
let primes =
  let N = Seq.initInfinite (fun x -> x + 2)
  primes_helper N

これで無限の素数列のシーケンスが完成しました。実際にこのシーケンスの内容を確認してみましょう。

> primes;;
val it : seq<int> =
  seq
    [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; ...]

ここではシーケンスを扱うのにリスト処理のテクニックを適用しましたが、当然シーケンス式を組み合わせて使うことも可能です。例えば上のプログラムのfilteredを生成するところは、シーケンス式を使って次のように書くこともできます。

let filtered = seq {
  for x in tl do
    if x % hd <> 0 then
      yield x
}

inserted by FC2 system