Haskell: รายการที่ไม่มีที่สิ้นสุดเมื่อจำนวนเต็มถูกผลักไปที่การใช้งานแบบสแต็ก

Aug 17 2020

ฉันกำลังพยายามใช้ Stack แบบธรรมดา แต่ฉันสับสนว่าทำไมฉันถึงได้รับรายการอนันต์เมื่อฉันดันจำนวนเต็มไปที่สแต็ก

ทุกฟังก์ชั่นอื่น ๆ ทำงานตามที่ผมคาดว่าพวกเขา pushแต่ผมไม่เข้าใจปัญหาที่เกิดขึ้นกับ มันผิดพลาดเมื่อฉันพยายามกำหนดสแต็กว่างให้กับตัวเองที่ดันตัวแปรดังต่อไปนี้:

λ > a = makeStack
λ > push 3 a
[3]
λ > a
[]
λ > a = push 3 a
λ > a
[3,3,3,3,3,3,3,3,3,3^CInterrupted.
type Stack a = [a]

makeStack :: Stack a 
makeStack = []

push :: a -> Stack a -> Stack a
push a as = (a:as)

คำตอบ

8 RobinZigmond Aug 17 2020 at 16:52

Haskell ไม่อนุญาตให้มีการกลายพันธุ์ ในซอร์สไฟล์หากคุณกำหนดตัวแปรaแล้วพยายามกำหนดใหม่ดังที่คุณทำที่นี่a = push 3 aคุณจะได้รับข้อผิดพลาดในการคอมไพล์ เหตุผลเดียวที่คุณไม่ทำคือคุณกำลังทำงานใน GHCi ซึ่งช่วยให้คุณกำหนดตัวแปรใหม่ได้ - นี่เป็นความสะดวกอย่างแท้จริงดังนั้นคุณจึงไม่ต้องคิดชื่อใหม่ในขณะที่ทดลองกับคำจำกัดความที่แตกต่างกัน

และที่สำคัญa = push 3 aคือไม่ได้ให้คุณค่าใหม่aโดยอิงจากค่าก่อนหน้าเนื่องจากเป็นภาษาที่จำเป็น แต่มันเป็นความหมายของในแง่ของตัวเองa

นั่นเป็นเหตุผลที่คุณได้รับรายการที่ไม่มีที่สิ้นสุด - คำจำกัดความของคุณได้รับการประมวลผลดังนี้:

a = push 3 a
   = 3:a
   = 3:(push 3 a)
   = 3:(3:a)

และอื่น ๆ เนื่องจากความเกียจคร้านของ Haskell จึงไม่มีปัญหากับคำจำกัดความเช่นนี้ - GHCi จะเมื่อคุณขอรายการทั้งหมดดังที่นี่เพียงคำนวณทีละองค์ประกอบและพิมพ์ 3 วินาทีต่อไปจนกว่าคุณจะบอกให้หยุด

เพื่อให้ได้สิ่งที่ต้องการคุณต้องพิมพ์push 3 aหรือถ้าคุณต้องการกำหนดชื่อเพียงแค่เลือกชื่อaอื่น b = push 3 aตามด้วยbจะทำงานตามที่คุณคาดหวัง

4 ZhiltsoffIgor Aug 17 2020 at 16:49

มีตัวแปร(ฉันเดาเกือบ) ไม่เปลี่ยนแปลง (ขอบคุณ @amalloy สำหรับการแก้ไขคำศัพท์ของฉัน) ตัวแปรใน haskell

หากคุณเขียนสิ่งนี้:

x = f x

มันเข้าสู่วงรอบที่ไม่มีที่สิ้นสุด: f (f (f ...

ดังนั้นจึงไม่มีค่าในอดีตaที่3อาจถูกผลักดัน

ดังนั้นคุณต้องใส่push 3 aค่าอื่น ๆ (หรือโดยตรงใน ghci สำหรับเรื่องนั้น)

การวนรอบดังกล่าวอาจมีประโยชน์ในบางครั้ง ดูที่Data.Function.fix:

fix :: (a -> a) -> a
fix f = let x = f x in x

สามารถใช้ทำสิ่งเดียวกันกับที่คุณทำ:

GHCi> fix (push 3)
[3,3,3,3,^CInterrupted.

กระนั้นการวนซ้ำที่ไม่มีที่สิ้นสุดก็ไม่ได้เป็นเช่นนั้นเสมอไป ลองดูสิ:

factFun rec n = if n == 0 then 1 else n * rec (n - 1)

ฟังก์ชันนี้อาจดูเหมือนแฟกทอเรียล แต่การเรียกซ้ำในสาขาที่ไม่สิ้นสุดจะถูกแทนที่ด้วยดัมมี่ ( rec) เราอยากให้หุ่นนี้แทนที่ด้วยfactFunซ้ำแล้วซ้ำเล่าเพื่อให้ได้แฟกทอเรียล fixทำสิ่งนี้:

GHCi> fix factFun 4
24

หมายเหตุ: ฉันจะทำซ้ำความคิดเห็นของฉันที่นี่: หากผู้อ่านยังไม่ทราบfixฉันต้องการเชิญพวกเขาไปเที่ยวที่ยาวและน่าสนใจ ฉันขอแนะนำให้พวกเขาเริ่มต้นด้วยwikibookนี้เกี่ยวกับความหมายเชิงแทน