Fold

説明

データのコレクション内の各項目に対してアルゴリズムを実行して新しい項目を作成し、 それによってまったく新しいコレクションを作成します。

ここでの語源は私には明確ではありません。Rust コンパイラでは ‘fold’ と ‘folder’ という用語が使われていますが、 通常の意味での fold というよりは map に近いように思えます。詳細については、以下の議論を参照してください。

例

// フォールドするデータ、単純な AST。
mod ast {
    pub enum Stmt {
        Expr(Box<Expr>),
        Let(Box<Name>, Box<Expr>),
    }

    pub struct Name {
        value: String,
    }

    pub enum Expr {
        IntLit(i64),
        Add(Box<Expr>, Box<Expr>),
        Sub(Box<Expr>, Box<Expr>),
    }
}

// 抽象フォルダー
mod fold {
    use ast::*;

    pub trait Folder {
        // リーフノードはノード自身をそのまま返す。場合によっては、これを
        // 内部ノードに対しても行える。
        fn fold_name(&mut self, n: Box<Name>) -> Box<Name> { n }
        // 子をフォールドすることで新しい内部ノードを作成する。
        fn fold_stmt(&mut self, s: Box<Stmt>) -> Box<Stmt> {
            match *s {
                Stmt::Expr(e) => Box::new(Stmt::Expr(self.fold_expr(e))),
                Stmt::Let(n, e) => Box::new(Stmt::Let(self.fold_name(n), self.fold_expr(e))),
            }
        }
        fn fold_expr(&mut self, e: Box<Expr>) -> Box<Expr> { ... }
    }
}

use fold::*;
use ast::*;

// 具体的な実装例 - すべての名前を 'foo' にリネームする。
struct Renamer;
impl Folder for Renamer {
    fn fold_name(&mut self, n: Box<Name>) -> Box<Name> {
        Box::new(Name { value: "foo".to_owned() })
    }
    // 他のノードにはデフォルトメソッドを使用する。
}

AST に対して Renamer を実行した結果は、古い AST と同一だが、 すべての名前が foo に変更された新しい AST です。実際のフォルダーでは、構造体自体の中でノード間にわたって 状態を保持することもあります。

フォルダーは、あるデータ構造を別の（ただし通常は類似した）データ構造へマップするように定義することもできます。 たとえば、AST を HIR ツリーへフォールドできます （HIR は高レベル中間表現を意味します）。

動機

データ構造内の各ノードに対して何らかの操作を実行することで、 データ構造をマップしたいことはよくあります。単純なデータ構造に対する単純な操作であれば、 これは Iterator::map を使って実行できます。より複雑な操作、 たとえば前のノードが後のノードに対する操作に影響する場合や、 データ構造の反復処理が自明でない場合には、fold パターンを使用する方が 適切です。

visitor パターンと同様に、fold パターンを使うと、 データ構造の走査と、各ノードに対して実行される操作を分離できます。

議論

このような方法でデータ構造をマップすることは、関数型言語では一般的です。OO 言語では、データ構造をその場で変更する方が一般的でしょう。 Rust では「関数型」のアプローチが一般的で、これは主に不変性が好まれるためです。 古いデータ構造を変更するのではなく、新しいデータ構造を使用すると、 ほとんどの場合、コードについての推論が容易になります。

効率性と再利用性のトレードオフは、 fold_* メソッドがノードを受け取る方法を変更することで調整できます。

上記の例では Box ポインターを操作しています。これらはデータを排他的に所有するため、 データ構造の元のコピーを再利用することはできません。一方で、 ノードが変更されない場合、それを再利用するのは非常に効率的です。

借用参照を操作する場合、元のデータ構造を再利用できます。しかし、 ノードが変更されていなくてもクローンする必要があり、これは高コストになる可能性があります。

参照カウント付きポインターを使用すると、両方の利点を得られます。つまり、 元のデータ構造を再利用でき、変更されていないノードをクローンする必要もありません。 ただし、それらは使い勝手がやや悪く、データ構造を可変にできないことを意味します。

関連項目

イテレーターには fold メソッドがありますが、これはデータ構造を 新しいデータ構造ではなく、値へフォールドします。イテレーターの map の方が、 この fold パターンに近いものです。

他の言語では、fold は通常、このパターンではなく Rust のイテレーターにおける意味で使われます。 一部の関数型言語には、データ構造に対して柔軟な map を実行するための強力な構文があります。

visitor パターンは fold と密接に関連しています。 どちらも、データ構造をたどりながら各ノードに対して操作を実行するという概念を共有しています。 ただし、visitor は新しいデータ構造を作成せず、古いデータ構造を消費することもありません。