ซิปเปอร์

ซิปเปอร์ () เป็นโครงสร้างข้อมูลชนิดหนึ่งหรืออาจเรียกว่าเป็นวิธีการที่สามารถใช้แสดงข้อมูลที่เราสนใจอยู่พร้อมกับรายการของข้อมูลอื่น ๆ ที่อยู่ภายในโครงสร้างข้อมูลเดียวกัน กล่าวคือ ในการเข้าถึงข้อมูลใด ๆ ภายในโครงสร้างข้อมูลนี้จะต้องระบุทั้งข้อมูลที่เราสนใจและที่อยู่ของข้อมูลซึ่งก็คือรายการของข้อมูลที่อยู่ในวิถีจากข้อมูลนั้นไปยังรากหรือตอนต้นของรายการและจากข้อมูลนั้นไปยังใบหรือปลายสุดของรายการ อีกทั้งเมื่อเราเข้าถึงข้อมูลที่เราสนใจได้แล้วเรายังเปลี่ยนจุดสนใจไปยังข้อมูลที่อยู่รอบ ๆ ข้อมูลที่เราสนใจได้ด้วยหรืออาจใช้คำสั่งอย่างอื่น เช่น เพิ่ม เปลี่ยน หรือลบข้อมูล โดยคำสั่งส่วนใหญ่มีประสิทธิภาพการทำงานเป็น O(1)  แนวคิดนี้ถูกคิดค้นขึ้นโดย Gérard Huet เมื่อปี 1997 โดยตั้งชื่อตามการทำงานของโครงสร้างข้อมูลนี้ที่เปรียบเสมือนซิปที่เราสามารถรูดขึ้นลงได้

นอกจากนี้โครงสร้างข้อมูลชนิดนี้มักเขียนเป็นโปรแกรมด้วยการเขียนโปรแกรมเชิงฟังก์ชัน (Functional programming) และแนวคิดของซิปเปอร์สามารถนำไปประยุกต์ใช้กับโครงสร้างข้อมูลได้หลายอย่าง เช่น รายการ (List) และต้นไม้ (Tree)

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

ตัวอย่างการใช้งานซิปเปอร์ : ต้นไม้แบบทวิภาค
ซิปเปอร์สามารถนำไปประยุกต์ใช้กับโครงสร้างข้อมูลได้หลายอย่าง ในที่นี้จะยกตัวอย่างโดยใช้ซิปเปอร์กับต้นไม้แบบทวิภาคซึ่งจะเป็นการเขียน a*(b^c-d)+(e+f) ออกมาในรูปของต้นไม้ทวิภาคดังรูป

ในที่นี้ กำหนดให้ปมข้อมูล (node) แต่ละปมแทนด้วย
Node(value,left,right) โดย value คือค่าในปมข้อมูล, left คือปมลูกที่อยู่ทางซ้าย, right คือปมลูกที่อยู่ทางขวา
null ถ้าบริเวณนั้นไม่มีปมข้อมูลอยู่
กำหนดให้วิถีของแต่ละปม (path) ในต้นไม้นี้แทนด้วย
L(path,node) เมื่อปมข้อมูลที่เรากำลังพิจารณาเป็นปมลูกซ้าย โดย path เป็นวิถีของปมพ่อ และ node คือปมพ่อ
R(node,path) เมื่อปมข้อมูลที่เรากำลังพิจารณาเป็นปมลูกขวา โดย path เป็นวิถีของปมพ่อ และ node คือปมพ่อ
top เมื่อปมข้อมูลนั้นเป็นปมราก
และกำหนดให้ตำแหน่งของปมข้อมูลแทนด้วย
Pos(node,path) โดย node คือปมข้อมูลที่เราสนใจและ path คือวิถีของปมข้อมูลนี้ถึงปมราก
ดังนั้นต้นไม้ทวิภาคนี้จะสามารถเขียนเป็นฟังก์ชันได้ว่า
Node("+",Node("*",Node("a",null,null),Node("-",Node("^",Node("b",null,null),Node("c",null,null)),Node("d",null,null))),Node("+",Node("e",null,null),Node("f",null,null)))
ดังนั้น เราสามารถที่จะระบุตำแหน่งของเครื่องหมายลบในต้นไม้ทวิภาคนี้ได้เป็น
Pos(Node("-",Node("^",Node("b",null,null),Node("c",null,null)),Node("d",null,null))),R(Node("*",Node("a",null,null),Node("-",Node("^",Node("b",null,null),Node("c",null,null)),Node("d",null,null))),
L(top,Node("+",Node("*",Node("a",null,null),Node("-",Node("^",Node("b",null,null),Node("c",null,null)),Node("d",null,null))),Node("+",Node("e",null,null),Node("f",null,null)))))
เมื่อเราสามารถระบุตำแหน่งข้อมูลที่เราต้องการได้แล้ว เราก็สามารถใช้คำสั่งอื่น ๆ กับข้อมูลที่เราสนใจได้ เช่น เลื่อนตำแหน่งลง (goDown) เลื่อนตำแหน่งขึ้น (goUp) เลื่อนไปทางซ้าย (goLeft) เลื่อนไปทางขวา (goRight) เปลี่ยนค่าในปมข้อมูล (change) เพิ่มข้อมูล (insert) หรือแม้แต่ลบปมข้อมูลนั้น (delete) อย่างถ้าต้องการสั่งให้เลื่อนตำแหน่งลงก็ใช้คำสั่งเป็น goDown(Pos(n,p)) ได้เลย ในเมื่อเราสามารถระบุตำแหน่งปมข้อมูลที่เราต้องการและสั่งได้เช่นนี้แสดงว่าการทำงานของฟังก์ชันเหล่านี้เป็น O(1)

จุดเด่นของซิปเปอร์
จุดเด่นของซิปเปอร์คือเราสามารถแสดงข้อมูลอื่น ๆ ที่อยู่บนวิถีเดียวกันกับข้อมูลที่เราสนใจตามที่ได้กล่าวไว้ในหัวข้อลักษณะของซิปเปอร์ ทำให้แนวคิดนี้ถูกนำไปใช้กับโปรแกรมที่มีการเพ่งความสนใจข้อมูล (focus) รวมถึงสามารถย้ายตำแหน่งของจุดสนใจไปยังข้อมูลรอบ ๆ ได้ด้วย เช่น โปรแกรม Xmonad อีกทั้งประสิทธิภาพในการทำงานของคำสั่งส่วนใหญ่ที่มีประสิทธิภาพในการทำงานเป็น O(1) และจุดเด่นที่สำคัญอีกอย่างหนึ่งโครงสร้างข้อมูลชนิดนี้เขียนโดยใช้การเขียนโปรแกรมเชิงฟังก์ชัน  (Functional programming) ซึ่งการเขียนโปรแกรมแบบนี้อาจเป็นเรื่องใหม่สำหรับโปรแกรมเมอร์หลาย ๆ คน

การเขียนโปรแกรมเชิงฟังก์ชัน
การเขียนโปรแกรมเชิงฟังก์ชันเป็นการเขียนโปรแกรมที่ทำงานคล้ายกับฟังก์ชันของคณิตศาสตร์ โดยมีแนวคิดสำคัญว่าให้หลีกเลี่ยงการเกี่ยวข้องกับสถานะของโปรแกรม (state) และหลีกเลี่ยงการเปลี่ยนแปลงข้อมูลต่าง ๆ โดยคำสั่งหนึ่งที่ได้รับพารามิเตอร์เหมือนกันต้องให้คำตอบเดียวกัน อย่างเช่น ในคณิตศาสตร์ ถ้าให้ f(x) = x + 4 และ x = 4 จะได้ f(4) = 8 เสมอ แสดงว่าถ้าสร้างคำสั่ง foo(Object e) ขึ้นมา จะได้ว่าคำสั่ง foo มีการทำงานเหมือนเดิมตราบที่พารามิเตอร์คือ e ยังเป็นค่าเดิม ดังนั้นจะพบว่าการเขียนโปรแกรมแบบนี้จะมีตัวแปรอยู่ในโปรแกรมน้อยเพื่อเป็นการหลีกเลี่ยงการเปลี่ยนแปลงค่าในข้อมูลและสามารถมีฟังก์ชันประกอบ (Composite function) อยู่ในส่วนการทำงานของโปรแกรมได้มากมาย

บริการที่มักจะมี
บริการที่ย้ายจุดที่สนใจไปยังรอบ ๆ ข้อมูลที่สนใจ เช่น ซ้าย ขวา บน และล่าง
บริการเปลี่ยนค่าของข้อมูลที่จุดที่สนใจ
บริการแทรกและลบข้อมูลที่จุดที่สนใจ

ความเร็วที่ใช้ในการทำงาน
ความเร็วในการทำงานส่วนใหญ่จะเป็น O(1) ซึ่งเป็นเพราะการเขียนโปรแกรมเชิงฟังก์ชันซึ่งเปรียบเสมือนการใส่ข้อมูลตัวนั้นและที่อยู่ของมันที่อาจเป็นในลักษณะของฟังก์ชันประกอบ (Composite function) เพื่อให้โปรแกรมทำงานตามบริการที่เราต้องการ แต่ทั้งนี้ก็ขึ้นอยู่กับการออกแบบโครงสร้างข้อมูลของโปรแกรมเมอร์แต่ละคนด้วยว่าจะวางโครงสร้างไว้อย่างไร บางคำสั่งจึงไม่จำเป็นต้องมีการทำงานเป็น O(1) เสมอไป

อ้างอิง
 Huet, Gerard. "Functional Pearl: The Zipper" Journal of Functional Programming 7 (5): 549-554, September 1997.
 Zipper (data structure)
 Functional Programming
 "Roll Your Own Window Manager: Tracking Focus with a Zipper"

หมวดหมู่:แบบชนิดข้อมูลนามธรรม
หมวดหมู่:โครงสร้างข้อมูล