ซิปเปอร์

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

```c
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)))
```

ดังนั้น เราสามารถที่จะระบุตำแหน่งของเครื่องหมายลบในต้นไม้ทวิภาคนี้ได้เป็น

```c
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)](http://en.wikipedia.org/wiki/Zipper_(data_structure))
* Functional Programming
* "Roll Your Own Window Manager: Tracking Focus with a Zipper"

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