พอดีไปเจอโค้ดของ David Turner ที่นิยามการสร้างลิสต์จำนวนเฉพาะด้วยเทคนิคการร่อนตะแกรง ซึ่งโค้ดต้นฉบับนั้นเขียนในภาษา SASL (ภาษาโปรแกรมเชิงฟังก์ชันยุคเดียวกับ ML) แต่สามารถสรุปเทียบออกมาเป็น Haskell ได้ภายในสองบรรทัดเพียงเท่านี้

sieve (p:xs) = p : sieve [x | x <- xs, mod x p /= 0]
primes = sieve [2..]

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

จุดที่น่าสนใจก็คือบรรทัดที่สองนั้นเรียกใช้ sieve บนลิสต์จำนวนเต็มตัวที่เหลือง่ายๆ สั้นๆ แล้วก็ตัดจบเลย … เห็นแล้วมันคันไม้คันมือยิ่งนัก อยากจับยุบบรรทัดนี้โยนทิ้งไปซะเพื่อให้เรานิยามลิสต์จำนวนเฉพาะได้ภายในบรรทัดเดียวเสียหนิ 55555

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

y = \f -> (\x -> f (x x)) (\x -> f (x x))
primes = y (\sieve -> \(p:xs) -> p : sieve [x | x <- xs, mod x p /= 0]) [2..]

… แต่ Haskell ไม่ยอมรันโค้ดนี้ให้ เพราะด้วยระบบไทป์แบบ Hindley–Milner เราจะโดนฟ้องกลับมาว่าการนิยาม y แบบนี้ก่อให้เกิดไทป์แบบอนันต์¹ 🤦

ทางแก้ทางแรก (ที่ง่ายสุด?) ก็คือบอกตัวภาษาว่าอย่าเรื่องมากกับโค้ดของฉันตรงนี้นะ 5555555TT55

import Unsafe.Coerce (unsafeCoerce)

y = \f -> (\x -> f (unsafeCoerce x x)) (\x -> f (unsafeCoerce x x))

ถ้าไม่นับการ import ก็อาจถือว่าโค้ดสำคัญๆ นั้นสามารถเขียนให้อยู่ในรูปบรรทัดเดียวได้อยู่แหละ เนอะ

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

fix f = f (fix f)

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

primes = 2 : [x | x <- [3..], all ((/=0).(mod x)) (takeWhile ((<=x).(^2)) primes)]

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

อีกประเด็นในการนิยามเช่นนี้ซึ่งเป็นหัวใจที่ทำให้มันแตกต่างการวิธีก่อนอย่างมีนัยสำคัญ คือส่วนที่หยิบจำนวนเฉพาะตัวที่เล็กกว่า $x$ มาเพื่อทดสอบว่า $x$ นั้นเป็นจำนวนเฉพาะหรือไม่ เราต้องลดการทดสอบลงไปเหลือแค่ใช้จำนวนเฉพาะที่มีค่าไม่เกิน $\sqrt{x}$ เท่านั้น² ไม่เช่นนั้นแล้วเราจะไม่มีทางทดสอบ $x$ ได้เสร็จเลยเพราะ Haskell ไม่รู้ว่า primes เป็นลิสต์แบบที่มีค่าเพิ่มขึ้นเท่านั้น จึงทำให้ takeWhile เฝ้ารอตัวเลขจำนวนเฉพาะตัวถัดไปในลิสต์เพื่อที่จะได้เอามาสร้างเป็นเลขตัวถัดไปในลิสต์ จึงเกิดเป็นเดดล็อกที่กลับตัวก็ไม่ได้ให้เดินต่อไปก็ไปไม่ถึงนั่นเอง

อ้างอิง

• Turner, David A. SASL language manual. University of Warwick, Department of Computer Science, 1975.
• Gist: Deriving the Y Combinator in Haskell
• Stack Overflow: Y Combinator in Haskell
• Math StackExchange: Why in Sieve of Erastothenes of $N$ number you need to check and cross out numbers up to $\sqrt{N}$? How it’s proved?

neizod

author