neizod's speculation

insufficient data for meaningful answer

Recursive Lambda ความงามบนความงาม...

Tuesday, August 21, 2012, 12:04 AM

พอถล่ำลึกลงไปใน functional programming ซักพักหนึ่ง จะเริ่มเกิดคำถามขึ้นมาว่า

“แล้วเราจะทำ recursion บน lambda ได้หรือเปล่า?”

ฟังดูเผินๆ ไม่น่าเป็นไปได้ เพราะ lambda ทำให้ฟังก์ชันไม่มีชื่อ แต่การ recursion ต้องอาศัยชื่อของฟังก์ชันนั้นๆ เพื่อเรียกมันขึ้นมาทำงานเสมอ สมมติเช่นฟังก์ชันง่ายๆ ที่จะทำการยกกำลังสองเลขที่ได้รับมาทันที

(lambda x: x**2)(5)

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

(lambda w, x: x**2)(999, 5)

แน่นอนว่ากรณีนี้เราไม่สนใจเลข 999 ที่ถูกนำไปเก็บไว้ยังตัวแปร w เลย …แล้วเราก็คงจะถึงทางตัน ถ้าไม่สังเกตว่าตัวแปร w นั้นหนะ รับค่าอะไรเข้ามาก็ได้ (เพราะไม่ได้ใช้) นี่รวมไปถึงเราอาจจะยัด lambda เข้าไปให้มันก็ได้

(lambda w, x: x**2)(lambda u: 42, 5)

นั่นหมายความว่า lambda ไม่จำเป็นต้องไร้ชื่อเสียทีเดียว แน่หละมันอาจจะไร้ชื่อใน scope หนึ่งๆ แต่กับ scope ที่ใหญ่ขึ้นกว่าตัวมันแล้ว เราสามารถตั้งชื่อให้มันได้ ถึงตอนนี้จะเปลี่ยนชื่อตัวแปรกันซักหน่อย พร้อมกับเอาฟังก์ชันสำหรับคำนวณจากด้านบนมาใส่แทน lambda u: 42 ไปซะ

(lambda g, y: y**2)(lambda x: x**2, 5)

จะเห็นว่าเลข 5 จะถูกเก็บไว้ในตัวแปร y และคำนวณ y**2 ตรงๆ โดยที่ lambda x: x**2 ไม่ได้แสดงบทบาทอะไร แต่เนื่องจากฟังก์ชัน lambda x: x**2 ถูก scope ด้านหน้าแปะป้ายชื่อให้ว่า g เป็นที่เรียบร้อยแล้ว ดังนั้น เราสามารถส่งผ่านเลข 5 ให้ไปทำงานกับ lambda x: x**2 ได้ดังนี้

(lambda g, y: g(y))(lambda x: x**2, 5)

แม้ว่าตอนนี้เราจะสามารถเรียกชื่อของ lambda x: x**2 ใน scope ที่ใหญ่กว่าตัวมันได้ แต่มันก็ไม่มีประโยชน์เลยเพราะการจะทำ recursion นั้นต้องสามารถเรียกชื่อตัวมันเองใน scope ที่มันอยู่ได้ ดังนั้น เราจะใช้ท่าเดิมคือส่งผ่านเจ้า lambda x: x**2 นี้ต่อไปเรื่อยๆ ไม่ให้มันหายไป โดย

(lambda g, y: g(g, y))(lambda f, x: x**2, 5)

เท่านี้ ใน scope ของ lambda f, x: x**2 ก็สามารถเรียกตัวเองได้แล้ว (ชื่อว่า f) ถึงตอนนี้ก็ได้เวลาเขียน recursion ให้มัน อาจเริ่มจากฟังก์ชันง่ายๆ อย่าง factorial ก็ได้

(lambda g, y: g(g, y))(lambda f, x: 1 if x == 0 else x * f(f, x-1), 5)

สังเกตว่าการเรียก recursion ภายใน lambda นี้ ต้องส่งผ่านชื่อฟังก์ชันตัวเองเป็นตัวแปรพ่วงลงไปด้วยเสมอนะ

จบแล้ว แค่นี้แหละ recursion บน lambda ไม่ยากอย่างที่คิดเลยใช่มั้ยครับ ;)