Haskell: รายการที่ไม่มีที่สิ้นสุดเมื่อจำนวนเต็มถูกผลักไปที่การใช้งานแบบสแต็ก
ฉันกำลังพยายามใช้ 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)
คำตอบ
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
จะทำงานตามที่คุณคาดหวัง
มีตัวแปร(ฉันเดาเกือบ) ไม่เปลี่ยนแปลง (ขอบคุณ @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นี้เกี่ยวกับความหมายเชิงแทน