โครงสร้างข้อมูลเชิงฟังก์ชันล้วนๆ

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

โครงสร้างข้อมูลแบบถาวรมีคุณสมบัติในการเก็บรักษาเวอร์ชันก่อนหน้าของตัวเองโดยไม่เปลี่ยนแปลง ในทางกลับกัน โครงสร้างที่ไม่ถาวร เช่นอาร์เรย์ยอมรับการอัปเดตแบบทำลายล้าง [ ^{1 ] นั่น}คือ การอัปเดตที่ไม่สามารถย้อนกลับได้ เมื่อโปรแกรมเขียนค่าลงในดัชนีใดดัชนีหนึ่งของอาร์เรย์แล้ว จะไม่สามารถเรียกค่าก่อนหน้ากลับมาได้อีก

ตามหลักการแล้วโครงสร้างข้อมูลเชิงฟังก์ชันบริสุทธิ์คือโครงสร้างข้อมูลที่สามารถนำไปใช้ในภาษาเชิงฟังก์ชันบริสุทธิ์ได้เช่นHaskellในทางปฏิบัติ หมายความว่าโครงสร้างข้อมูลจะต้องสร้างขึ้นโดยใช้เฉพาะโครงสร้างข้อมูลแบบคงอยู่ เช่น ทูเพิลประเภทผลรวมประเภทผลคูณและประเภทพื้นฐาน เช่น จำนวนเต็ม อักขระ และสตริง โครงสร้างข้อมูลดังกล่าวจะต้องคงอยู่ อย่างไรก็ตาม โครงสร้างข้อมูลแบบคงอยู่ไม่ได้เป็นเชิงฟังก์ชันบริสุทธิ์เสมอไป^{[ 1 ] : 16} ตัวอย่างเช่นอาร์เรย์แบบคงอยู่เป็นโครงสร้างข้อมูลแบบคงอยู่และถูกนำไปใช้โดยใช้อาร์เรย์ ดังนั้นจึงไม่ใช่เชิงฟังก์ชันบริสุทธิ์

ในหนังสือPurely functional data structuresโอคาซากิเปรียบเทียบการอัปเดตแบบทำลายล้างกับมีดของเชฟฝีมือเยี่ยม^{[ 1 ] :} การอัปเดตแบบทำลายล้างไม่สามารถย้อนกลับได้ ดังนั้นจึงไม่ควรใช้เว้นแต่จะแน่ใจว่าไม่ต้องการค่าก่อนหน้าอีกต่อไป อย่างไรก็ตาม การอัปเดตแบบทำลายล้างยังสามารถให้ประสิทธิภาพที่ไม่สามารถหาได้จากเทคนิคอื่น ตัวอย่างเช่น โครงสร้างข้อมูลที่ใช้อาร์เรย์และการอัปเดตแบบทำลายล้างอาจถูกแทนที่ด้วยโครงสร้างข้อมูลที่คล้ายกัน โดยที่อาร์เรย์ถูกแทนที่ด้วยแผนที่รายการเข้าถึงแบบสุ่ม หรือต้นไม้สมดุลซึ่งยอมรับการใช้งานฟังก์ชันบริสุทธิ์ แต่ต้นทุนการเข้าถึงอาจเพิ่มขึ้นจากเวลาคงที่ไปเป็นเวลาลอการิทึม

โครงสร้างข้อมูลไม่สามารถเป็นฟังก์ชันโดยเนื้อแท้ได้เสมอไป ตัวอย่างเช่น สแต็กสามารถนำไปใช้เป็นรายการเชื่อมโยงเดี่ยวได้การนำไปใช้นี้เป็นฟังก์ชันอย่างแท้จริงตราบใดที่การดำเนินการบนสแต็กเพียงอย่างเดียวจะส่งคืนสแต็กใหม่โดยไม่เปลี่ยนแปลงสแต็กเดิม อย่างไรก็ตาม หากภาษาไม่ใช่ฟังก์ชันอย่างแท้จริง ระบบรันไทม์อาจไม่สามารถรับประกันความไม่เปลี่ยนแปลงได้ เรื่องนี้แสดงให้เห็นโดย Okasaki ^{[ 1 ] : 9–11} ซึ่งเขาแสดงให้เห็นว่าการต่อรายการเชื่อมโยงเดี่ยวสองรายการยังคงสามารถทำได้โดยใช้การตั้งค่าแบบเชิงคำสั่ง

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

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

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

ต่อไปนี้คือรายชื่อโครงสร้างข้อมูลนามธรรมที่มีการใช้งานในรูปแบบฟังก์ชันล้วนๆ:

• โครงสร้างข้อมูลแบบ Stack (เข้าก่อนออกทีหลัง) ถูกนำมาใช้ในรูปแบบของSinglely Linked List
• คิวที่ถูกนำมาใช้ในรูปแบบคิวแบบเรียลไทม์
• คิวสองด้านที่นำมาใช้ในรูปแบบคิวสองด้านแบบเรียลไทม์
• เซต (หลายเซต)ขององค์ประกอบที่เรียงลำดับและแผนที่ที่จัดทำดัชนีโดยคีย์ที่เรียงลำดับ ซึ่งนำไปใช้ในรูปแบบต้นไม้แดง-ดำหรือโดยทั่วไปแล้วในรูปแบบต้นไม้ค้นหา
• คิวลำดับความสำคัญซึ่งใช้งานในรูปแบบของคิว Brodal
• รายการควบคุมการเข้าถึงแบบสุ่ม ซึ่งใช้งานในรูปแบบรายการควบคุมการเข้าถึงแบบสุ่มแบบไบนารีที่ไม่สมมาตร
• แฮชคอนซิง
• ซิป (โครงสร้างข้อมูล)

ในหนังสือPurely Functional Data Structures ของเขา นักวิทยาศาสตร์คอมพิวเตอร์คริส โอคาซากิได้อธิบายถึงเทคนิคที่ใช้ในการออกแบบและใช้งานโครงสร้างข้อมูลเชิงฟังก์ชันล้วนๆ ซึ่งตัวอย่างย่อยๆ บางส่วนได้สรุปไว้ด้านล่างนี้

การประเมินแบบขี้เกียจมีความน่าสนใจเป็นพิเศษในภาษาฟังก์ชันบริสุทธิ์^{[ 1 ] : 31} เนื่องจากลำดับของการประเมินจะไม่เปลี่ยนแปลงผลลัพธ์ของฟังก์ชัน ดังนั้น การประเมินแบบขี้เกียจจึงกลายเป็นส่วนสำคัญของการสร้างโครงสร้างข้อมูลฟังก์ชันบริสุทธิ์โดยธรรมชาติ ช่วยให้การคำนวณเกิดขึ้นได้ก็ต่อเมื่อต้องการผลลัพธ์จริงๆ เท่านั้น ดังนั้น รหัสของโครงสร้างข้อมูลฟังก์ชันบริสุทธิ์จึงสามารถพิจารณาข้อมูลที่จะถูกใช้งานจริงและข้อมูลที่จะถูกละเลยได้โดยไม่สูญเสียประสิทธิภาพ การคำนวณที่จำเป็นมีเพียงสำหรับข้อมูลประเภทแรกเท่านั้น นั่นคือสิ่งที่จะดำเนินการจริง

หนึ่งในเครื่องมือสำคัญในการสร้างโครงสร้างข้อมูลที่มีประสิทธิภาพและทำงานได้อย่างบริสุทธิ์คือ memoization ^{[ 1 ] : 31} เมื่อการคำนวณเสร็จสิ้น ผลลัพธ์จะถูกบันทึกไว้และไม่จำเป็นต้องดำเนินการซ้ำอีกครั้ง ซึ่งมีความสำคัญอย่างยิ่งในการใช้งานแบบ lazy; การประเมินเพิ่มเติมอาจต้องการผลลัพธ์เดียวกัน แต่เป็นไปไม่ได้ที่จะรู้ว่าการประเมินใดจะต้องการผลลัพธ์นั้นก่อน

โครงสร้างข้อมูลบางอย่าง แม้แต่โครงสร้างที่ไม่ใช่ฟังก์ชันล้วนๆ เช่นอาร์เรย์ไดนามิกก็ยอมรับการดำเนินการที่มีประสิทธิภาพส่วนใหญ่ (เช่น เวลาคงที่สำหรับอาร์เรย์ไดนามิก) และไม่ค่อยมีประสิทธิภาพ (เช่น เวลาเชิงเส้นสำหรับอาร์เรย์ไดนามิก) จากนั้นสามารถใช้ การถัวเฉลี่ยเพื่อพิสูจน์ว่าเวลาการทำงานเฉลี่ยของการดำเนินการนั้นมีประสิทธิภาพ^{[ 1 ] : 39} กล่าวคือ การดำเนินการที่ไม่มีประสิทธิภาพเพียงเล็กน้อยนั้นหายากพอ และไม่เปลี่ยนแปลงวิวัฒนาการเชิงอะซิมโทติกของความซับซ้อนของเวลาเมื่อพิจารณาลำดับของการดำเนินการ

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

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

คิวแบบเฉลี่ย^{[ 1 ] : 65 [ 1 ] : 73} ประกอบด้วยรายการเชื่อมโยงเดี่ยวสองรายการ ได้แก่ รายการด้านหน้าและรายการด้านหลังที่กลับด้าน องค์ประกอบจะถูกเพิ่มเข้าไปในรายการด้านหลังและถูกลบออกจากรายการด้านหน้า ยิ่งไปกว่านั้น เมื่อใดก็ตามที่คิวด้านหน้าว่างเปล่า คิวด้านหลังจะถูกกลับด้านและกลายเป็นด้านหน้า ในขณะที่คิวด้านหลังจะว่างเปล่า ความซับซ้อนของเวลาเฉลี่ยของการดำเนินการแต่ละครั้งมีค่าคงที่ แต่ละเซลล์ของรายการจะถูกเพิ่ม กลับด้าน และลบออกอย่างมากที่สุดหนึ่งครั้ง เพื่อหลีกเลี่ยงการดำเนินการที่ไม่มีประสิทธิภาพซึ่งรายการด้านหลังถูกกลับด้าน คิวแบบเรียลไทม์จะเพิ่มข้อจำกัดว่ารายการด้านหลังมีความยาวเท่ากับรายการด้านหน้าเท่านั้น เพื่อให้แน่ใจว่ารายการด้านหน้ายังคงยาวกว่ารายการด้านหลัง รายการด้านหลังจะถูกกลับด้านและเพิ่มเข้าไปในรายการด้านหน้า เนื่องจากการดำเนินการนี้ไม่มีประสิทธิภาพ จึงไม่ได้ดำเนินการทันที แต่จะกระจายออกไปในการดำเนินการถัดไป ดังนั้น แต่ละเซลล์จะถูกคำนวณก่อนที่จะจำเป็น และรายการด้านหน้าใหม่จะถูกคำนวณทั้งหมดก่อนที่จะต้องเรียกใช้การดำเนินการที่ไม่มีประสิทธิภาพใหม่

• โครงสร้างข้อมูลถาวร

• วิทยานิพนธ์เรื่อง โครงสร้างข้อมูลเชิงฟังก์ชันล้วนๆโดย คริส โอคาซากิ (ไฟล์ PDF)
• ทำให้โครงสร้างข้อมูลคงอยู่โดย James R. Driscoll, Neil Sarnak, Daniel D. Sleator, Robert E. Tarjan (PDF)
• รายการถาวรเต็มรูปแบบพร้อมการเชื่อมโยงแบบ Catenationโดย James R. Driscoll, Daniel D. Sleator, Robert E. Tarjan (PDF)
• โครงสร้างข้อมูลถาวรจากหลักสูตรอัลกอริทึมขั้นสูงของ MIT OpenCourseWare
• มีอะไรใหม่ในโครงสร้างข้อมูลเชิงฟังก์ชันล้วนๆ นับตั้งแต่สมัย Okasaki?บนเว็บไซต์Theoretical Computer Science Stack Exchange