ซิปเปอร์

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

ซิปเปอร์ (อังกฤษ: Zipper) เป็นโครงสร้างข้อมูลชนิดหนึ่งหรืออาจเรียกว่าเป็นวิธีการที่สามารถใช้แสดงข้อมูลที่เราสนใจอยู่พร้อมกับรายการของข้อมูลอื่น ๆ ที่อยู่ภายในโครงสร้างข้อมูลเดียวกัน กล่าวคือ ในการเข้าถึงข้อมูลใด ๆ ภายในโครงสร้างข้อมูลนี้จะต้องระบุทั้งข้อมูลที่เราสนใจและที่อยู่ของข้อมูลซึ่งก็คือรายการของข้อมูลที่อยู่ในวิถีจากข้อมูลนั้นไปยังรากหรือตอนต้นของรายการและจากข้อมูลนั้นไปยังใบหรือปลายสุดของรายการ อีกทั้งเมื่อเราเข้าถึงข้อมูลที่เราสนใจได้แล้วเรายังเปลี่ยนจุดสนใจไปยังข้อมูลที่อยู่รอบ ๆ ข้อมูลที่เราสนใจได้ด้วยหรืออาจใช้คำสั่งอย่างอื่น เช่น เพิ่ม เปลี่ยน หรือลบข้อมูล โดยคำสั่งส่วนใหญ่มีประสิทธิภาพการทำงานเป็น 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"