ดูเหมือนว่า ความจริงกับความฝัน มีเส้นหนาๆกั้นอยู่ — tk

หลังจาก /me ผจญภัยในการสร้างเครื่องมือมาแล้วกว่าครึ่ง เรากลับมาพบกับความจริงที่ว่า psudo-code ที่เราร่างไว้นี้ มันไม่น่าจะสามารถสร้างเป็น function ที่ใช้เฉพาะ functions ได้จริงๆ

เพราะว่าอะไร?

สิ่งหนึ่งที่เป็นปัญหาสำคัญที่สุดในตอนนี้ คือ คำสั่ง for เนื่องจากการใช้ for ในแบบนี้ แอบมีสิ่งที่เราไม่พึงปราถนาเกิดขึ้น และมันก็คือ ตัวแปร และ assignment semantics เพราะเราจำเป็นต้องมีตัวแปร i เป็น counter ในการนับจำนวนรอบ

นอกจากนี้แล้ว psudo-code นี้ก็ดูแปลกประหลาดเกินไปสำหรับการสร้างเป็น function with functions

/me จึงจำใจสร้างมันขึ้นมาใหม่ โดยการใช้เครื่องมือตัวใหม่ ไฉไลกว่าเดิม

List

List เป็น data structure ที่ทำให้ /me สามารถสร้างข้อมูลที่มีความสัมพันธ์ต่อๆกัน นอกจาก List แล้วยังต้องมี function ที่จำเป็นในการเข้าถึง List ไม่ว่าจะเป็น isEmpty(), first(),range(), map(), reduce() ซึ่งเจ้า function เหล่านี้เป็นกุณแจที่สามารถช่วยให้เราสร้าง loop ขึ้นมาได้อีกด้วย

ด้วยความรู้พวกนี้ เราสามารถเขียน psudo-code v2 ขึ้นมาใหม่ดังนี้

แน่นอนว่าโค้ดนี้ สามารถเอาไปรันได้จริงๆ ใน native javascript
และเมื่อเปลี่ยน psudo-code ใหม่ ทำให้เราจำเป็นต้องสร้างฟังก์ชั่นอีก 2 ตัว คือ range() และ reduce() และทั้งคู่ต่างเป็น function ที่มาคู่กับการใช้ List

กลับมาที่หัวข้อ “List” อีกครั้ง

วิธีที่ง่ายที่สุดที่ /me สามารถสร้าง List ขึ้นมาได้นั้น คือ การใช้ Pairs หรือ คู่ลำดับ ซึ่งเจ้าคู่ลำดับนี้นอกจากสามารถใช้ในการสร้าง List แล้ว ยังสามารถนำไปใช้ในการสร้าง Tree หรือ data type ประเภทอื่นๆอีกมากมาย (โดยเฉพาะคนที่คุ้นเคยกับการใช้ cons ใน Lips)

ซึ่งโครงสร้างแบบนี้สามารถแทนได้ด้วยฟังก์ชั่นดังนี้

จิตนาการว่า Pair คือ คู่ลำดับ <x, y>

โดยที่ PAIR เป็นฟังก์ชั่นรับ 2 ซึ่งตัวแปรแรกเป็น ของที่อยู่ทางซ้าย และ ของที่อยู่ทางขวา แล้ว return เป็นฟังก์ชั่นที่รอดำเนินการอะไรสักอย่างกับของทั้ง 2 ชิ้น

โดยที่ LEFT, RIGHT คือ ฟังก์ชั่นรับคู่ลำดับแล้วดำเนินการ เลือกของชิ้นแรก(ทางซ้าย) และ เลือกของชิ้นที่ 2 (ทางขวา) ตามลำดับ ดังนั้นเราจะสามารถเข้าถึงค่าของ PAIR ได้โดยการใช้ฟังก์ชั่นทั้ง 2 นี้

สำหรับการสร้าง List ด้วย pair นั้น เราสามารถสร้างได้หลากหลายรูปแบบ และรูปแบบที่ง่ายที่สุด ก็คือ “linked list” โดยการสร้างแต่ละ PAIR เก็บ value และอีกด้านชี้ไปยัง PAIR คู่ถัดๆไป ตามรูป

//ตัวอย่าง linked list และแถมตัวอย่างสำหรับคนที่อยากจะสร้าง tree

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

โครงสร้างหนึ่งที่สามารถนำมาใช้แทน linked list จาก PAIR เรียกว่า “Two pairs as a list node” โดย เราจะใช้ PAIR 2 ชั้น สำหรับ ทุกๆ node ดังนี้

โดย
* first เป็น flag บอกสถาณะ isEmpty ของ list
* second.first เป็น head (ของที่อยู่ทางซ้าย)
* second.second เป็น tail (ของที่อยู่ทางขวา)

โดยเริ่มต้น แทน NULL หรือ EMPTY ด้วย

ฟังก์ชั่นพื้นฐานที่เหลือในการสร้าง linked list ดังนี้

โดยแต่ละฟังก์ชั่นสามารถเข้าใจได้ไม่ยาก เมื่อพิจารณาจากโครงสร้าง list ดังนี้

เพื่อความสะดวก /me จะสร้าง to_array สำหรับดึงทุกๆ items ออกมาจาก list และแปลงเป็น native array

หลังจากมี List แล้วก็กลับมาที่เป้าหมายของเรา : RANGE()

RANGE

นึกๆดูแล้วมันง่ายมากสำหรับที่จะสร้างฟังก์ชั่นนี้โดยวิธีแบบ native

แต่ด้วยปัญหาเดิมๆ เราไม่สามารถใช้วิธีนี้ได้ เพราะว่า มันอาศัยการประกาศตัวแปร และแน่นอนว่ามันขัดกับปรัชญาหลักของบทความนี้ ดังนั้น อีกหนึ่งตัวเลือก คือ การสร้าง range โดยใช้ recursion

และด้วยความชำนาญในการสร้าง recursive functions ที่ศึกษามาแล้วใน EP.6 จะได้ว่า

กลับไปที่โค้ด isPrime(n) อีกครั้ง

Reduce/Fold

ปราการสุดท้าย อีก 1 ฟังก์ชั่น ที่กำลังรอการ implement ก็คือ reduce หรือบางครั้ง เราเรียกมันว่า fold ซึ่งเป็นฟังก์ชั่นทำหน้าที่ merge แต่ละ item ใน list เขาด้วยกันเป็น 1 value เช่น

โดยความแตกต่างเพียงอย่างเดียวระหว่าง recuce และ fold ก็คือ

* เราต้องกำหนด initial value ให้สำหรับ fold(lst)
* แต่เราไม่ต้องกำหนด initial value ให้ reduce(lst) โดยจะมี initial = lst[0] อัตโนมัติ

หรืออาจจะพูดได้ว่า fold เป็น general case ของ reduce เลยก็ว่าได้
*** จริงๆแล้วใน recude ใน javascipt สามารถเป็นได้ทั้ง fold และ reduce

สามารถ implement fold ได้โดยใช้ recursive ได้ดังนี้

ทั้งนี้ ยังมีอีกวิธีในการสร้าง fold เรียกว่า Fold left

ไม่ว่าจะเป็น Fold left หรือ Fold right ทั้งคู่ต่างมีความสามารถเท่าเทียมกัน (ในที่นี้จะเลือกใช้ Fold right) และสามารถเปลี่ยนให้อยู่ในรูปฟังก์ชั่นได้ดังนี้

จากนั้นก็ยังสามารถใช้ FOLD ไปสร้าง MAP ที่ทำหน้าที่ใช้การเปลี่ยนทุกๆ items ใน list ตามฟังก์ชั่น f ได้ดังนี้

เมื่อได้เครื่องมือทุกอย่างพร้อมแล้ว ลุยกันต่อใน isPrime(n) โดยการแทนทุกๆฟังก์ชั่นลงใน psudo-code จะได้ว่า

ลองทดสอบอีกครั้ง กับ ทุกๆตัวเลขในช่วง 2-100

เห้ยยยยย มันคืออะไรอะ? มันใช่ prime numbers รึปล่าวนะ? ใช่จริงๆด้วย

ฮูเร้ๆๆๆ เสร็จแล้วววววววววว our isPrime(n)

และบทต่อไป กับการปรับ output อีกเล็กๆน้อยๆ ให้อยู่ในรูป string แบบเกร๋ๆ

PS. อ่านตอนก่อนหน้าได้ที่
EP1: Introduction
EP2: Numbers
EP3: Arithmetic operators
EP4: Booleans
EP5: Predicates & Comparison Operators
EP6: Recursion
EP7: List

ต้นฉบับ Programming with Nothing

แต่สามารถ ดูโค้ดส่วนต่างๆได้ที่ Github จะทยอย push ตามบล๊อคที่ทยอยเขียน

Tell your friend about thisShare on Facebook
Facebook
0Tweet about this on Twitter
Twitter