รายการอนันต์เพิ่มเติมในรูปแบบ
นี่เป็นเรื่องราวต่อจากเรื่องราวก่อนหน้าของฉันที่สามารถพบได้ "ที่นี่"
สตรีมรวม
ครั้งที่แล้ว เราสร้างสตรีมที่น่าสนใจสองสามรายการโดยใช้ stream-add ตอนนี้ฉันอยากจะแนะนำฟังก์ชันที่หลากหลายมากขึ้นซึ่งจะช่วยให้เราสร้างสตรีมที่น่าสนใจยิ่งขึ้นได้
ฟังก์ชันนี้แทบจะเหมือนกับ stream-add ทุกประการ ยกเว้นว่าเราสามารถส่งการดำเนินการใดๆ ไปให้ฟังก์ชันนั้นได้ ไม่ใช่แค่ + stream-add และ (stream-combine +) เทียบเท่ากัน
พลังใหม่
เราสามารถสร้างสตรีมใหม่ๆ ที่สนุกสนานได้ด้วยวิธีการรวมแบบใหม่นี้ เราสร้างจำนวนธรรมชาติโดยการบวกกระแสสองกระแสเข้าด้วยกัน ดังนั้นเราจึงสามารถสร้างเลขยกกำลังของสองโดยการคูณกระแสสองกระแส
เช่นเดียวกับจำนวนธรรมชาติ สมมติว่ากระแสแห่งกำลังของสอง powsOf2 มีอยู่จริง สตรีมนี้คือ '(1 2 4 8 16 32 ...) เมื่อเราสตรีมรวมกันคูณกับ '(2 2 2 2 2 2 ...) เราจะได้ '(2 4 6 8 16 32 64 ...) เหมือนเมื่อก่อน ((stream-combine *) twos powsOf2)) เป็นส่วนท้ายของรายการของเรา และเราแค่ต้องเริ่มต้นด้วย 1
กระแสอีกประการหนึ่งที่ตอนนี้เป็นเรื่องเล็กน้อยในการสร้างคือลำดับของกำลังสอง
และแฟกทอเรียล
โปรดสังเกตอีกครั้งว่าแฟคทอเรียล: '(1 2 6 24 120 720 …) คูณธรรมชาติ: '(1 2 3 4 5 6) เท่ากับ cdr ของแฟกทอเรียล: '(2 6 24 120 720 5040 …) เนื่องจากเรามี cdr ของแฟคทอเรียลอยู่แล้ว เราจึงต้องเริ่มต้นด้วยอันแรกอย่างชัดเจนแล้วรวมทั้งสองเข้าด้วยกัน
หากยังรู้สึกสับสนอยู่เล็กน้อย ฉันขอแนะนำให้คุณดำเนินการผ่านกระบวนการพื้นฐานในที่ทำงานดังที่ฉันแสดงไว้ในโพสต์ที่แล้ว
มุ่งหน้าสู่ไพรม์ส
หนึ่งในตัวอย่างที่คลาสสิกและสง่างามที่สุดของรายการอนันต์คือการสร้างรายการของจำนวนเฉพาะ เห็นได้ชัดว่าสิ่งนี้เป็นไปไม่ได้เนื่องจากเครื่องมือเดียวของเราคือ stream-combine ดังนั้นเรามาแนะนำฟังก์ชันสุดท้ายกัน
stream-filter รับภาคแสดงและสตรีม จากนั้นจะลงไปตามรายการและเก็บเฉพาะรายการที่ตรงตามภาคแสดงเท่านั้น หากรายการประเมินว่าเป็นเท็จ รายการนั้นจะถูกข้ามไป เนื่องจากทั้งหมดนี้ได้รับการประเมินอย่างเกียจคร้าน stream-filter จึงทำงานตามความต้องการ: ดำเนินการเฉพาะสิ่งที่จำเป็นสำหรับสิ่งที่เราขอเท่านั้น
การใช้งานที่เรียบง่าย
วิธีหนึ่ง (หลายวิธี) ในการสร้างเลขคี่คือการกรองเลขคู่ทั้งหมดออกจากเลขธรรมชาติ
ตะแกรงแห่ง Eratosthenes
Sieve of Eratosthenes เป็นอัลกอริธึมโบราณในการค้นหาจำนวนเฉพาะ โดยพื้นฐานแล้ว คุณจะต้องเลือกรายการจำนวนธรรมชาติที่ขึ้นต้นด้วย 2 (จำนวนเฉพาะตัวแรก) ผลคูณใดๆ ของสองตัวตามคำนิยามไม่ใช่จำนวนเฉพาะ ดังนั้นให้ลบออกจากรายการ ตอนนี้ไปยังจำนวนเฉพาะตัวถัดไปแล้วลบจำนวนทวีคูณทั้งหมดออกจากรายการ ไปเรื่อยๆ กระบวนการนี้จะลบตัวเลขทั้งหมดที่มีตัวประกอบอื่นที่ไม่ใช่ตัวเดียวออก (อ่านเพิ่มเติม) โดยปกติแล้วกระบวนการนี้จำเป็นต้องมีขอบเขตบน แต่เราพบวิธีที่จะเล่นกับอนันต์แล้ว การประเมินแบบขี้เกียจอีกครั้งหนึ่งจะช่วยประหยัดเวลาโดยการกรองเฉพาะเมื่อเราต้องการเท่านั้น
นายกรัฐมนตรีถึงอินฟินิตี้
ฟังก์ชั่นตะแกรงใช้อัลกอริทึมที่อธิบายไว้ข้างต้น โดยจะใช้องค์ประกอบแรกของสตรีมเป็นจำนวนเฉพาะ กรองปัจจัยทั้งหมดออก และทำซ้ำขั้นตอนสำหรับจำนวนเฉพาะถัดไป (เฉพาะ) การส่งผ่านกระแสของจำนวนธรรมชาติเริ่มต้นที่ 2 จะได้จำนวนเฉพาะ
เป็นเรื่องที่น่าทึ่งที่เราสามารถสร้างโครงสร้างข้อมูลที่ไม่มีที่สิ้นสุดได้อย่างมีประสิทธิภาพภายในพื้นที่หน่วยความจำที่มีจำกัด มันแสดงให้เห็นถึงพลังและความงดงามของการประเมินแบบขี้เกียจ สำหรับการใช้งานจริงของรายการเหล่านี้ ฉันจะไม่พูดถึงเรื่องนี้ แต่ฉันพบว่า "stack overflow thread" มีประเด็นที่น่าสนใจอยู่บ้าง บางภาษาเช่น Haskell มีรายการในตัวที่ไม่มีที่สิ้นสุด ดังนั้นแนวคิดนี้จึงห่างไกลจากแค่ทางทฤษฎี
เกี่ยวกับผู้เขียน
Eric Breyer เป็นนักศึกษาระดับปริญญาตรีด้านวิทยาการคอมพิวเตอร์ที่ Rice University คุณสามารถพบเขาได้ที่ "เว็บไซต์" ของเขา เช่นเดียวกับใน "GitHub" และ "LinkedIn"
