Haskell: Daftar tak terbatas saat integer didorong ke implementasi stack

Question

Saya mencoba menerapkan Stack sederhana tetapi saya bingung mengapa saya mendapatkan daftar tak terbatas ketika saya mendorong integer ke tumpukan.

Semua fungsi lainnya berfungsi seperti yang saya harapkan, tetapi saya tidak memahami masalahnya push. Terjadi kesalahan saat saya mencoba menetapkan tumpukan kosong ke dirinya sendiri yang telah mendorong variabel seperti berikut:

λ > 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 tidak mengizinkan mutasi. Dalam file sumber, jika Anda mendefinisikan variabel adan kemudian mencoba untuk menetapkannya kembali, seperti yang Anda lakukan di sini a = push 3 a, Anda akan mendapatkan kesalahan kompilasi. Satu-satunya alasan Anda tidak melakukannya adalah karena Anda bekerja di GHCi, yang memungkinkan Anda untuk mendefinisikan ulang variabel - ini murni untuk kenyamanan sehingga Anda tidak perlu terus memikirkan nama baru saat bereksperimen dengan definisi yang berbeda.

Dan, yang terpenting, a = push 3 aadalah tidak memberikan nilai baru untuk adidasarkan pada sebelumnya, karena akan menjadi dalam bahasa imperatif. Sebaliknya, itu adalah definisi dari a istilah itu sendiri .

Itulah mengapa Anda mendapatkan daftar tak terbatas - definisi Anda diproses sebagai berikut:

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

dan seterusnya. Karena kemalasan Haskell, tidak ada masalah dengan definisi seperti ini - GHCi akan, ketika Anda meminta daftar lengkap, seperti di sini, cukup menghitung satu elemen pada satu waktu, dan oleh karena itu terus mencetak 3 hingga Anda menyuruhnya berhenti.

Untuk mendapatkan apa yang Anda inginkan, Anda hanya perlu mengetik push 3 a, atau jika Anda perlu memberinya nama, cukup pilih nama lain dari a. b = push 3 adiikuti oleh bakan berperilaku seperti yang Anda harapkan.

Answer 2

Ada (saya kira, hampir) tidak ada variabel yang bisa berubah (terima kasih kepada @amalloy untuk mengoreksi terminologi saya) variabel di haskell.

Jika Anda menulis sesuatu seperti ini:

x = f x

Ini memasuki loop tak terbatas: f (f (f ...

Jadi, tidak ada nilai lampaua yang 3boleh didorong.

Oleh karena itu, Anda harus memasukkan push 3 anilai lain (atau langsung ke dalam ghci dalam hal ini).

Namun, loop seperti itu terkadang berguna. Lihat di Data.Function.fix:

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

Ini dapat digunakan untuk melakukan hal yang sama seperti yang Anda lakukan:

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

Namun, infinite loop tidak selalu terjadi. Lihatlah:

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

Fungsi ini mungkin terlihat seperti faktorial, namun panggilan rekursif di cabang non-terminating diganti dengan dummy ( rec). Kami ingin boneka ini diganti factFunberulang-ulang untuk mendapatkan faktorialnya. fixMelakukan hal ini:

GHCi> fix factFun 4
24

---

Catatan: Saya akan menduplikasi komentar saya di sini: jika pembaca belum mengetahuinya fix, saya ingin mengajak mereka dalam perjalanan yang panjang dan menarik. Saya sarankan mereka memulai dengan wikibook ini tentang semantik denotasi .