Functional Programming #4 : List Processing

เกริ่นนำ

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

ว่าแต่ว่า List คืออะไร

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

หัวเรื่องแทรก : ชนิดตัวแปร Range

ในงานที่ต้องจัดการ List ขนาดใหญ่  เช่นหนึ่งพันล้านตัว บางกรณีก็จำเป็นต้องสร้างเป็น List ถ้ามีการเปลี่ยนแปลงภายใน List แต่มีไม่น้อยที่เก็บค่าไล่ลำดับขึ้นไปเช่นตั้งแต่ 1 ไปถึงพันล้านเป็นต้นและคงค่านี้ไปตลอด การที่จะเก็บค่าใน List ในลักษณะนี้ จะเป็นการสิ้นเปลืองมาก บางภาษาจึงมีการคิดค้นชนิดตัวแปร Range ขึ้นมาเช่น

ซึ่งการเก็บมันจะเก็บเพียงสามค่าเท่านั้น คือค่าเริ่มต้นค่าสิ้นสุดและค่า step กรณีที่ไม่ได้ระบุจึงมีค่า step อย่างเช่นตัวอย่างข้างบน จะกำหนด step เป็น 1 และสิ่งที่ภาษาจะต้องทำก็คือการทำให้ List กับ Range นั้นสมมูลกันที่ไดใช้ List ได้ก็มักจะใช้ Range ได้ยกตัวอย่างเช่น

ข้างบนเป็นแบบ List ข้างล่างเป็น Range สามารถมอง List กับ Range นั้นเป็นเรื่องเดียวกันได้ ซึ่งภาษาหลายภาษาเช่น Python ใช้วิธีนี้ แต่สำหรับภาษาที่เราใช้กันเป็นหลักคือ Haskell ไม่มีความจำเป็นใด ๆ ที่ต้องสร้างชนิดตัวแปร Range ขึ้นมาเพราะธรรมชาติของภาษาเป็นแบบ Laziness อยู่แล้วมันจะสร้างขนาดของ List เท่าที่จำเป็นต้องใช้ เนื้อหาในหัวเรื่องนี้จึงเป็นเพียงเรื่องแทรกด้วยประการฉะนี้

การสร้าง List

การสร้าง List ใน Haskell นั้น มีลูกเล่นไม่น้อยเริ่มจากง่ายที่สุด ถ้าต้องการสร้าง List มีค่า 1 ถึง 10 เราสามารถเขียนได้ว่า

ซึ่งแน่นอนถ้าสร้าง 1 ถึงล้านโดยใช้รูปแบบข้างบนคงเฉาแย่ เรามีทางเลือกครับ

ง่ายขึ้นเยอะครับ แล้วถ้าต้องการเลขคู่ที่อยู่ระหว่าง 1 ถึง 100 เราสามารถใช้

จะสร้างแบบไม่รู้จบก็ไม่มีใครว่า

จะใช้ตัวแปรก็ดี ตั้งแต่ n ลดลงทีละ 2 จนถึง 0

List Comprehension

List Comprehension เป็นกระบวนการสร้างสมาชิกใน List แบบสามารถใส่เงื่อนไขได้ ซึ่งรูปแบบของไวยากรณ์นั้นได้มาจากทฤษฏีเซตของคณิตศาสตร์ ลองดูตัวอย่างง่าย ๆ นี้ครับ

การทำความเข้าใจทำดังนี้ครับแบ่ง | ออกเป็นซ้ายขวา ทางซ้ายเป็นการคำนวณและสร้าง List ใหม่โดยบอกว่าเอาค่า x ทีละตัวไปคูณ 2 ส่วนด้านขวานั้นเป็นการสร้างตัวแประและเงื่อนไขในกรณีนี้กำหนดให้ x เป็น List 1 ถึง 50 หรือจะใช้วิธีข้างล่างก็ได้ผลไม่ต่างกัน

even เป็นฟังก์ชันที่รับพารามิเตอร์ตัวเดียวเป็นตัวเลข ถ้าค่าที่ส่งเข้าไปเป็น True มิฉะนั้นจะได้ False ซึ่งตรงข้ามกับฟังก์ชัน odd  การใช้ , แทนความหมาย “และ” ใน List Comprehension ใช้ “หรือ” ไม่ได้ คราวนี้เรามาสร้างคู่ลำดับดูครับ

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

ประยุกต์แก้โจทย์ปัญหาสามเหลี่ยมปิธากอรัส

มายืดเส้นยืดสายดูนะครับ ลองนำ List Comprehension มาลองแก้โจทย์ทางคณิตศาสตร์เล่น ๆ ดู เอาง่าย ๆ เอาเรื่องสามเหลี่ยมมุมฉากปิธากอรัสก็แล้วกัน เป็นที่ทราบกันว่าสามเหลี่ยมมุมฉากนั้นความยาวด้านสั้นทั้งสอง เมื่อนำมายกกำลังสองแล้วบวกเข้าด้วยกันจะได้เท่ากับความยาวด้านที่ยาวที่สุดยกกำลังสอง เข้าใจยากใช้ไหมครับ แต่ถ้าเขียนเป็นสมการจะร้องอ๋อทันที นั่นคือ a^2 + b^2 = c^2 นั่นเอง ถ้ากำหนด a, b อยู่ระหว่าง 1 ถึง 10 เป็นจำนวนเต็ม ถามว่าจะมีสามเหลี่ยมปิธากอรัสขนาดใดบ้าง ที่อยู่ในพิกัดนี้ แน่นอนครับเราเรียนรู้มาตั้งแต่เด็กแล้วว่า มีคำตอบอยู่อย่างน้อยหนึ่งคำตอบคือ (3, 4, 5) แล้วค่าอื่นหละ ยังมีอีกหรือไม่ ลงมือทำกันเลยดีกว่า ขั้นแรกเราต้องกำหนดการขอบเขตการวิ่งเสียก่อน  a <- [1..10], b <-[1..10], c<-[1..200]    ค่า c มีค่าวิ่งสูงสุดถึง 200 เนื่องจาก 10^2 + 10^2 = 200 นั่นเอง  กำหนดให้ a <= b มิฉะนั้นจะได้ค่าซ้ำ (3, 4, 5) กับ (4, 3, 5) และที่ขาดไม่ได้คือ a^2 + b^2 == c^2    เครื่องหมายเปรียบเทียบใช้ == เมื่อรวมทั้งหมดแล้วจะได้

ทดลองดูเอาเองนะครับว่ามีค่าอื่นนอกจาก (3, 4, 5) หรือไม่ลองเทียบกับการเขียนแบบ Imperative ดูครับว่ายากง่ายแตกต่างกันอย่างไร

โจทย์การบ้าน

มีคนแชร์รูปนี้ใน facebook ครับเพิ่งเห็นเมื่อเดือนที่แล้วลองแก้ดูครับ โดยใช้ List Comprehension นะครับไม่ใช่เทคนิคอื่น

Animals weight problem

Animals weight problem

พื้นฐานการใช้งาน List

หลังจากที่มีพื้นฐานการสร้าง List แล้ว สิ่งที่ควรรู้ต่อไปคือการเพิ่มลดสมาชิกใน List เพื่อจะได้ใช้ประยุกต์ต่อไป ซึ่งเราจะสนใจแค่พื้นฐานบางตัวเท่านั้น เริ่มจากการนำเอา List สอง List มาต่อกันโดยใช้ ++ ซึ่งอ่านว่า concat

แต่ถ้าเราต้องการเดิมสมาชิกตัวเดียวเข้าข้างหน้า  List เราสามารถใช้ : ที่อ่านว่า cons ได้ครับ

ซึ่ง cons ทำงานเร็วกว่า concat มาก ซื่ง cons จะมีบทบาทมากต่อไปในเรื่องของ Pattern Matching ซึ่งภาษาในจักรวาล FP นิยมใช้กันมาก แต่ในเบื้องต้นนี้เรามาลองดูการตัดต่อส่วนของ List  โดยใช้ฟังก์ชันพื้นฐานสี่ตัว ดังนี้

และการตรวจสอบว่า ค่าที่เราระบุนั้นเป็นสมาชิกของ List หรือไม่ ใช้ elem ซึ่งได้คำตอบเป็น True/False ครับ

ในภาษา Haskell มี “ผงชูรส” ในการวางตำแหน่งของฟังก์ชัน สำหรับฟังก์ชันใด ๆ ที่มีพารามิเตอร์สองตัว เราสามารถเลือกได้ว่าเวลาใช้งาน จะเอาชื่อฟังก์ชันอยู่ซ้ายหรือตรงกลางก็ได้ ถ้าซ้ายจะเป็นแบบที่คุณเคยข้างบน เรียกว่า Prefix Notation  แต่ถ้าตรงกลาง ที่เรียกว่า Infix Notation นั้น เพื่อเป็นการบอกให้ Haskell รู้ เราจำเป็นต้อง ใช้เครื่องหมาย ` คร่อมหน้าหลัง ซึ่งคือตัวสัญลักษณ์เป็นตัวเดียวกันกับตัวเปลี่ยนภาษาสำหรับ Windows อาจจะพิมพ์ยากหน่อย ซึ่งผลลัพธ์จะได้เป็น

ฟังก์ชันสนับสนุน

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

ฟังก์ชัน length

ฟังก์ชันนี้เป็นฟังก์ชันพื้นฐานใช้ในการนับจำนวนสมาชิก ใน list เช่น

เราสามารถสร้าง length เองได้โดยการเขียนดังนี้ครับ

สังเกตได้ว่า ผมใช้ ‘ หลัง length ไม่มีอะไรพิเศษครับ’ ดังที่เคยกล่าวไว้ในบทก่อน เพื่อไม่ให้ชนกับฟังก์ชัน length ที่มีอยู่แล้วนั่นเอง สังเกตนะครับ การทำงานของฟังก์ชันนี้ก็เป็นแบบเรียกตัวเองอย่างง่ายครับ ถ้า List ว่าง ก็ส่งค่า 0 กลับออกมา มิฉะนั้นต้องมีอย่างน้อยหนึ่งตัว ก็เลยเอา 1 มาบวกกับที่เหลือ ทำงานเรียกตัวเอง ก็จะได้คำตอบ

ส่วนวิธีที่กระชับกว่าวิธีแรก เราอาศัยความสามารถของ FP ที่เรียกว่า Pattern Matching อย่างที่โปรยหัวเอาไว้ข้างบน ลองดูตัวอย่างข้างล่างครับ

ตัวอย่างนี้จะเห็นว่าผมใช้ pattern (x:xs)  มาเป็นส่วนพารามิเตอร์ แทนชื่อฟังก์ชัน  เมื่อส่งพารามิเตอร์มา มันจะพยายามลอง Match ดูว่าเป็น สมาชิก : List ได้หรือไม่ ถ้าได้ ก็จะเข้าเงื่อนไข พร้อมตั้งชื่อให้ว่า x : xs  ในตัวอย่างนี้ สมมุติว่าเราใช้งาน

x จะมีค่า 4 และ xs จะมีค่า [3, 2, 8] โดยอัตโนมัติ แต่ถ้า

x จะมีค่า 7  และ xs จะมีค่า []  ซึ่งการใช้ Pattern Matching นั้นจะทำให้การเขียนง่ายขึ้น สั้นลง และทำงานเร็วขึ้นด้วยครับ มีจุดที่น่าสนใจอยู่ครับ ตัวแปร x นั้น ในฟังก์ชันนี้เราไม่ได้ใช้งานเลย เราสามารถ ใช้ _ แทนตัวแปร หมายความว่าเราไม่สนใจ ทำให้เรานิยามฟังก์ชัน length’ ใหม่ ได้ดังนี้

ฟังก์ชัน sum

อันนี้เป็นโจทย์การบ้านในบทที่สอง จำได้ไหมครับ ซึ่งเมื่อผสานกับ List ทำให้แก้โจทย์ปัญหาได้อย่างง่ายมาก เมื่อเทียบกับ Imperative ไม่มีการวนรอบ ไม่ใช้ตัวแปรมาสะสมค่า ให้มันพลาดการใช้ loop นี้โอกาสพลาดเยอะครับมันมักจะเกิดปัญหา “off by one error” หรือเรียกว่าขาดหนึ่งเกินหนึ่งนั่นเอง การสร้างฟังก์ชันนี้ ล้อเหมือน length ดังนี้

 ฟังก์ชัน product

เหมือนกับ sum ครับแต่เปลี่ยนจากการบวกเป็นการคูณ ซึ่งถ้าการคูณนั้นเป็นค่าเรียงกันตั้งแต่ 1 มันก็คือ factorial นั่นเอง

เขียนแค่นี้ครับ factorial ที่เราเรียนกันมายาวนานในบทก่อน ๆ  ถ้าเราต้องการสร้าง product  เอง โครงฟังก์ชันเหมือนกับ sum แค่เปลี่ยนจาก + เป็น * และค่าเริ่มต้นจาก 0 เป็น 1 เท่านั้น ดังนี้ครับ

ฟังก์ชัน take

ฟังก์ชันนี้เป็นการสร้าง List ใหม่  ที่มีสมาชิก n ค่าแรกของ List เดิม ซึ่ง n คือค่าพารามิเตอร์ตัวแรกนั่นเอง เราสามารถสร้างฟังก์ชัน take ได้ดังนี้

 ฟังก์ชัน takeWhile

ฟังก์ชัน takeWhile เป็นฟังก์ชันมีระดับ ที่รับพารามิเตอร์สองตัว ตัวแรกเป็นฟังก์ชันที่รับพารามิเตอร์หนึ่งตัว และส่งค่าออกมาเป็น True/False ส่วนพารามิเตอร์ตัวที่สองของ takeWhile แน่นอนครับเป็น List

takeWhile เหมือนกับ take ต่างกันตรงที่เงื่อนไขในการหยุดสร้างสมาชิก ถ้าเป็น take คือจำนวนตัว n แต่ สำหรับ takeWhile แล้ว จะส่งค่าที่ละค่าใน List เข้ามาในฟังก์ชัน ถ้าทำให้เงื่อนไขเป็นจริง ก็จะเก็บค่าลงใน List ใหม่ สะสม แต่เมื่อใดก็ตามค่าสมาชิกใดที่ทำให้เงื่อนไขเป็นเท็จ จะหยุดทำงานทันที  ในกรณีข้างบน เครื่องหมาย /= คือการเปรียบเทียบไม่เท่ากับนั่นเอง การทำงานของฟังก์ชันจะสะสมตราบใดที่ค่าสมาชิกใน List ไม่ใช่ 5 ซึ่งก็ไล่ไปตั้งแต่ 10, 2, 4  และค่าใน List ตัวที่ 4 เป็น 5 ทำให้เงื่อนไขเป็นเท็จ จึงหลุด เราสามารถสร้างฟังก์ชันนี้ได้ ดังนี้ครับ

การสร้างฟังก์ชันนี้มีที่น่าสนใจคือ การใช้งาน คำสั่ง case ซึ่งเหมือนกับ case หรือ switch ในภาษาทั่วไป แต่สังเกตว่า เมื่อตรงตามเงื่อนไขแล้ว เราใช้เครื่องหมาย -> เป็นการระบุการในการทำงานครับ

ฟังก์ชัน Zip

ฟังก์ชัน zip จะนำเอา List สอง List มาสร้างเป็นคู่ลำดับโดยใช้ Tuple   รวมกันกลายเป็น List เดียวกัน  โดยที่ตัวแรกจับกับตัวแรก ตัวที่สองจับกับตัวที่สอง ไปเรื่อย ๆ เหมือนกับซิปที่เรารูดนั่นเอง  เช่น

ซึ่งถ้าขนาดของ List ยาวไม่เท่ากัน มันจะ zip เท่าที่ได้ List ฝั่งที่ยาวเกิน ก็จะถูกตัดทิ้งไป เราสามารถเขียนเป็นฟังก์ชันได้ดังนี้

 ฟังก์ชัน find

ฟังก์ชัน find นั้นมี prototype เหมือน takeWhile การทำงานก็จะป้อนค่าสมาชิกใน List ที่ละตัวเข้าสู่ฟังก์ชันที่เป็นพารามิเตอร์ตัวแรก ถ้าค่าสมาชิกใดทำให้ฟังก์ชันส่งค่ากลับมาว่าเป็นจริง ฟังก์ชันจะหยุดทำงานทันที และส่งค่าสมาชิกตัวนั้นออกมา เช่น

ฟังก์ชัน find สามารถสร้างได้โดย

ในกรณีนี้ ถ้าไม่พบจะส่งค่ากลับออกมาเป็น -1 ซึ่งไม่ค่อยดีนักเพราะ -1 สามารถเป็นสมาชิกใน List ได้ ฟังก์ชันจริงของ Haskell จะส่งค่ากลับออกมาเป็น Nothing ถ้าหาไม่พบ ซึ่งจะทำได้ต้องเรียนรู้เรื่องระบบชนิดตัวแปรของ Haskell เพิ่มเติม ซึ่งเราไม่ได้สนใจขนาดนั้น เราสนใจเฉพาะแนวคิด FP จึงข้อข้ามไปครับ ถือว่าห้ามใส่ -1 ใน List ก็แล้วกัน

ฟังก์ชันนี้พิเศษหน่อย ถ้าต้องการใช้ใน Haskell มันไม่ได้อยู่ใน Module หลักที่ชื่อว่า Prelude ครับ ที่จะโหลดมาให้ตั้งแต่แรกเมื่อรันโปรแกรม ซึ่งฟังก์ชันที่ผ่านมาอยู่ใน Prelude ทั้งสิ้น ส่วน find นั้น ถ้าต้องการใช้ ต้อง Import Module ที่ชื่อว่า Data.List โดยเขียนบรรทัดข้างล่างเป็นบรรทัดแรกในโปรแกรม แล้วจะใช้งานได้ครับ

 การประยุกต์

เมื่อเราเรียนรู้ทั้ง List Comprehension และ ฟังก์ชันต่าง ๆ มาแล้ว คราวนี้ถึงเวลาแล้วที่จะนำมันมายำรวมกันให้กลายเป็นงาน เอาแบบง่าย ๆ ครับ

การประยุกต์โจทย์ Fibonacci

อนุกรมฟิโบนัซซีนั้นนิยามเอาไว้ว่า เป็นอนุกรม (ชุดตัวเลข) ที่มีสองค่าแรกเป็น 1 ส่วนค่าต่อไปนั้นได้มาจากสองค่าก่อนหน้าบวกกัน ดังนั้นอนุกรมฟิโบนัสซี 10 ค่าแรกจึงมีดังนั้น   1, 1, 2, 3, 5, 8, 13, 21, 34, 55   อนุกรมนี้คิดค้นโดยฟิโบนัซซีชาวปิซ่า คิดค้นอนุกรมนี้มาเกือบๆ 900 ปีมาแล้ว โดยสมมุติการจับคู่ผสมพันธุ์ของกระต่าย  โดยที่หารู้ไม่ว่าในเวลาต่อมานักวิทยาศาสตร์พบชุดตัวเลขนี้การสร้างสิ่งต่าง ๆ ในธรรมชาติ ตั้งแต่ดอกไม้บนเขาสูง ไปจนถึงหอยยักษ์ใต้ทะเลลึก ว่ากันว่าพระเจ้าใช้ชุดตัวเลขนี้ในการสร้างสรรพสิ่ง พูดมากก็จะเกินเนื้อหาของเรา หยุดแค่นี้ดีกว่าครับ ตอนนี้เราสนใจเพียงแค่ว่า  จะสร้างอนุกรมนี้แบบ FP ขึ้นมาได้อย่างไร ผมคงไม่อธิบาย ฝากเอาไว้ให้วิเคราะห์เล่นๆ ดูครับ

สั้นพอใหม่ครับ fib นี้มีขนาดไม่จำกัด แต่อย่างที่ทราบกันมันใช้แนวคิด Laziness มันจึงไม่ได้ทำงานทันที มิฉะนั้นมันจะทำงานไม่หยุดจนตายไปข้างหนึ่ง เราสามารถใช้ take มากำหนดปริมาณงานที่ต้องทำ ดังนี้

สรุป

ด้วยความร่วมมือกันของ List Comprehensive ซึ่งเป็นการ สร้าง List แบบ on-the-fly ผนวกฟังก์ชันที่เสริมการทำงานของ List กลายเป็นเครื่องมืออันทรงพลังที่สามารถนำมาประยุกต์ใช้ในการแก้โจทย์ปัญหาต่าง ๆ ได้ เราได้เห็นถึงการสร้างฟังก์ชันเสริม จะเห็นได้ว่าก็อาศัยการเรียกตัวเองในบทก่อน ๆ นั้น ในบทสุดท้าย จะคุยกันเรื่องของ Filter-Map-Reduce และการนำไปประยุกต์ใช้กับโจทย์ที่ยากขึ้นระดับหนึ่งครับ

[Total: 3    Average: 4.3/5]

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *