Fold pattern (แพตเทิร์นโฟลด์)

คำอธิบาย

ประมวลผลอัลกอริทึมลงบนสมาชิกแต่ละตัวในโครงสร้างข้อมูลเพื่อสร้างสมาชิกชุดใหม่ขึ้นมา ซึ่งส่งผลให้ได้โครงสร้างข้อมูลชุดใหม่ขึ้นมาทั้งชุด

ที่มาและรากศัพท์ของคำนี้ในบริบทนี้อาจดูแปลกตาไปบ้าง โดยคำว่า ‘fold’ และ ‘folder’ ถูกนำมาใช้อย่างแพร่หลายในตัวคอมไพเลอร์ของ Rust แม้ว่าในมุมมองทั่วไปมันจะดูคล้ายคลึงกับการ map มากกว่าการ fold ในความหมายทางคณิตศาสตร์หรือการยุบรวมข้อมูลตามปกติ (ดูรายละเอียดเพิ่มเติมได้ในหัวข้อการอภิปรายด้านล่าง)

ตัวอย่าง

// The data we will fold, a simple 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>),
    }
}

// The abstract folder
mod fold {
    use ast::*;

    pub trait Folder {
        // A leaf node just returns the node itself. In some cases, we can do this
        // to inner nodes too.
        fn fold_name(&mut self, n: Box<Name>) -> Box<Name> { n }
        // Create a new inner node by folding its children.
        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::*;

// An example concrete implementation - renames every name to 'foo'.
struct Renamer;
impl Folder for Renamer {
    fn fold_name(&mut self, n: Box<Name>) -> Box<Name> {
        Box::new(Name { value: "foo".to_owned() })
    }
    // Use the default methods for the other nodes.
}

ผลลัพธ์จากการรัน Renamer บนต้นไม้ AST คือการได้ AST ตัวใหม่ที่มีโครงสร้างเหมือนกับตัวเดิมทุกประการ แต่ชื่อตัวแปรทั้งหมดจะถูกเปลี่ยนเป็น foo ในการใช้งานจริง ตัว Folder มักจะมีการเก็บสถานะ (state) บางอย่างไว้ภายใน struct เพื่อส่งต่อข้อมูลระหว่างแต่ละโหนดได้ด้วย

นอกจากนี้ Folder ยังสามารถถูกออกแบบให้แปลง (map) โครงสร้างข้อมูลชนิดหนึ่งไปเป็นอีกชนิดหนึ่ง (ซึ่งมักจะมีโครงสร้างที่ใกล้เคียงกัน) ได้ด้วย เช่น เราสามารถ fold ต้นไม้ AST ให้กลายเป็นต้นไม้ HIR ได้ (HIR ย่อมาจาก High-level Intermediate Representation)

แรงจูงใจ

เป็นเรื่องปกติที่เราต้องการแปลงโครงสร้างข้อมูลโดยประมวลผลตรรกะบางอย่างกับแต่ละโหนด สำหรับการทำงานที่ไม่ซับซ้อนบนโครงสร้างข้อมูลพื้นฐาน เราสามารถใช้ Iterator::map ได้อย่างง่ายดาย ทว่าสำหรับการประมวลผลที่มีความซับซ้อนสูง เช่น กรณีที่โหนดลำดับก่อนหน้าส่งผลต่อการประมวลผลโหนดลำดับถัดไป หรือในกรณีที่โครงสร้างข้อมูลมีความซับซ้อนจนไม่สามารถวนซ้ำแบบปกติได้ การเลือกใช้ Fold pattern ย่อมมีความเหมาะสมกว่ามาก

เช่นเดียวกับ Visitor pattern แพตเทิร์น Fold ช่วยให้เราสามารถแยกตรรกะการท่องผ่านโครงสร้างข้อมูล (traversal) ออกจากการดำเนินการ (operations) ที่กระทำกับแต่ละโหนดได้อย่างเป็นอิสระ

การอภิปราย

การแปลงโครงสร้างข้อมูลในลักษณะนี้พบเห็นได้ทั่วไปในภาษาโปรแกรมเชิงฟังก์ชัน ส่วนในภาษาเชิงวัตถุ มักจะนิยมแก้ไขข้อมูลในตำแหน่งเดิม (in-place mutation) มากกว่า ทั้งนี้ แนวทางแบบเชิงฟังก์ชันถือเป็นที่นิยมอย่างยิ่งในภาษา Rust เนื่องด้วยการให้ความสำคัญกับความไม่เปลี่ยนแปลงค่า (immutability) โดยการสร้างโครงสร้างข้อมูลชุดใหม่ขึ้นมาทดแทนการแก้ไขของเดิม ช่วยให้การตรวจสอบและวิเคราะห์การทำงานของโค้ดทำได้ง่ายและปลอดภัยกว่าในเกือบทุกสถานการณ์

เราสามารถปรับเปลี่ยนจุดสมดุลระหว่างประสิทธิภาพและความสามารถในการนำกลับมาใช้ซ้ำได้ ด้วยการปรับรูปแบบการรับพารามิเตอร์ของแต่ละโหนดในเมท็อด fold_*:

ในตัวอย่างข้างต้น เราทำงานกับพอยน์เตอร์ Box เนื่องจากพอยน์เตอร์เหล่านี้เป็นเจ้าของข้อมูลแต่เพียงผู้เดียว โครงสร้างข้อมูลชุดเดิมจึงไม่สามารถนำกลับมาใช้ซ้ำได้อีก ทว่าหากโหนดใดไม่มีการเปลี่ยนแปลง การส่งต่อโหนดนั้นกลับไปใช้ต่อจะทำได้อย่างมีประสิทธิภาพสูงมาก

หากเราเลือกทำงานผ่านการยืมแบบ reference โครงสร้างข้อมูลเดิมจะยังคงสามารถนำกลับมาใช้ใหม่ได้ ทว่าเราจำเป็นต้องโคลนข้อมูลในโหนดนั้นเสมอแม้ว่าจะไม่มีการแก้ไขค่าใดๆ ซึ่งอาจมีต้นทุนทางประสิทธิภาพสูง

การเลือกใช้ Smart Pointer แบบนับจำนวนการอ้างอิง (Reference-Counted Pointer เช่น Rc หรือ Arc) จะช่วยรวมจุดเด่นของทั้งสองแนวทางเข้าด้วยกัน — ทำให้เราสามารถนำโครงสร้างข้อมูลเดิมกลับมาใช้ซ้ำได้โดยไม่ต้องคัดลอกโหนดที่ไม่มีการแก้ไข อย่างไรก็ดี วิธีนี้จะลดความสะดวกในการเขียนโค้ดลง และส่งผลให้โครงสร้างข้อมูลเหล่านั้นไม่สามารถแก้ไขค่าได้โดยตรง

ดูเพิ่มเติม

ตัว Iterator เองมีเมท็อดชื่อ fold เช่นกัน ทว่าเมท็อดดังกล่าวทำหน้าที่ยุบรวมโครงสร้างข้อมูลให้กลายเป็นค่าเดี่ยว (single value) ไม่ใช่การสร้างโครงสร้างข้อมูลชุดใหม่ขึ้นมา เมท็อด map ของ Iterator จึงมีความใกล้เคียงกับ Fold pattern ในบทนี้มากกว่า

สำหรับภาษาอื่นๆ คำว่า fold มักถูกใช้ในความหมายเดียวกับเมท็อด fold บน Iterator ของ Rust มากกว่าแพตเทิร์นในบทนี้ โดยภาษาเชิงฟังก์ชันบางภาษาจะมีโครงสร้างอันทรงพลังสำหรับทำการ map บนโครงสร้างข้อมูลได้อย่างยืดหยุ่นสูง

แพตเทิร์น Visitor มีความสัมพันธ์อย่างใกล้ชิดกับ Fold โดยทั้งคู่มีแนวคิดร่วมกันในการท่องผ่านโครงสร้างข้อมูลเพื่อดำเนินการกับแต่ละโหนด ทว่า Visitor จะไม่ได้สร้างโครงสร้างข้อมูลชุดใหม่ขึ้นมา และไม่ได้ยึดครองหรือทำลาย (consume) ข้อมูลเดิม