Haskell: Danh sách vô hạn khi số nguyên được đẩy để triển khai ngăn xếp

Question

Tôi đang cố gắng triển khai một Ngăn xếp đơn giản nhưng tôi bối rối không hiểu tại sao tôi nhận được danh sách vô hạn khi tôi đẩy một số nguyên vào ngăn xếp.

Tất cả các chức năng khác hoạt động như tôi mong đợi nhưng tôi không hiểu vấn đề với push. Đã xảy ra sự cố khi tôi cố gắng gán một ngăn xếp trống cho chính nó đã đẩy một biến như sau:

λ > 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)

Answer 1

Haskell không cho phép đột biến. Trong tệp nguồn, nếu bạn xác định một biến avà sau đó cố gắng gán lại biến đó, như cách bạn làm ở đây a = push 3 a, bạn sẽ gặp lỗi biên dịch. Lý do duy nhất mà bạn không làm là bạn đang làm việc trong GHCi, công cụ này cho phép bạn xác định lại các biến - đây hoàn toàn là một sự tiện lợi để bạn không phải tiếp tục nghĩ ra những cái tên mới trong khi thử nghiệm các định nghĩa khác nhau.

Và, điều quan trọng a = push 3 alà không đưa ra một giá trị mới adựa trên giá trị trước đó, vì nó sẽ có trong một ngôn ngữ mệnh lệnh. Thay vào đó, nó là một định nghĩa a về bản thân nó .

Đó là lý do tại sao bạn nhận được một danh sách vô hạn - định nghĩa của bạn được xử lý như sau:

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

và như thế. Vì sự lười biếng của Haskell, không có vấn đề gì với một định nghĩa như thế này - GHCi, khi bạn yêu cầu danh sách đầy đủ, như ở đây, chỉ cần tính toán từng phần tử một và do đó tiếp tục in 3 giây cho đến khi bạn yêu cầu nó dừng lại.

Để có được những gì bạn muốn, bạn chỉ cần nhập push 3 ahoặc nếu bạn cần đặt tên cho nó, chỉ cần chọn một tên khác a. b = push 3 atiếp theo bsẽ hoạt động như bạn mong đợi.

Answer 2

Không có (tôi đoán, gần như) không có biến có thể thay đổi (nhờ @amalloy đã sửa chữa thuật ngữ của tôi) trong haskell.

Nếu bạn viết một cái gì đó như thế này:

x = f x

Nó đi vào một vòng lặp vô hạn: f (f (f ...

Vì vậy, không có giá trị quá khứa nào 3có thể được đẩy lên.

Do đó, bạn phải đặt push 3 amột số giá trị khác (hoặc trực tiếp vào ghci cho vấn đề đó).

Tuy nhiên, một vòng lặp như vậy đôi khi có thể hữu ích. Hãy xem Data.Function.fix:

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

Nó có thể được sử dụng để làm điều tương tự như bạn làm:

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

Tuy nhiên, vòng lặp vô hạn không phải luôn luôn như vậy. Hãy xem:

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

Hàm này có thể trông giống như giai thừa, nhưng lệnh gọi đệ quy trong nhánh không kết thúc được thay thế bằng một giả ( rec). Chúng tôi muốn có hình nộm này được thay đi thay factFunlại nhiều lần để lấy giai thừa. fixthực hiện điều này:

GHCi> fix factFun 4
24

---

Lưu ý: Tôi sẽ nhân bản nhận xét của tôi ở đây: nếu người đọc chưa biết fix, tôi muốn mời họ đi một chuyến đi dài và thú vị. Tôi đề nghị họ bắt đầu với wikibook này về ngữ nghĩa biểu thị .