Haskell: Yığın uygulamasına tamsayı itildiğinde sonsuz liste

Aug 17 2020

Basit bir Yığın uygulamaya çalışıyorum ama yığına bir tamsayı ittiğimde neden sonsuz bir liste aldığım konusunda kafam karıştı.

Diğer tüm işlevler beklediğim gibi çalışıyor ama problemi anlamıyorum push. Aşağıdaki gibi bir değişkeni iten boş bir yığın atamaya çalıştığımda ters gidiyor:

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

Yanıtlar

8 RobinZigmond Aug 17 2020 at 16:52

Haskell mutasyona izin vermez. Bir kaynak dosyada, bir değişkeni tanımlar ave sonra yeniden atamaya çalışırsanız, burada yaptığınız gibi a = push 3 a, bir derleme hatası alırsınız. Yapmamanızın tek nedeni, değişkenleri yeniden tanımlamanıza izin veren GHCi'de çalışıyor olmanızdır - bu tamamen bir kolaylıktır, bu nedenle farklı tanımlarla deney yaparken yeni isimler düşünmeye devam etmek zorunda kalmazsınız.

Ve en önemlisi, a = push 3 abir değil yeni bir değer veren abir zorunluluk dilde olacağı gibi, öncekini temel. Bunun yerine, bir tanımıdır a kendisi açısından .

Bu yüzden sonsuz bir liste elde edersiniz - tanımınız şu şekilde işlenir:

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

ve bunun gibi. Haskell'in tembelliği nedeniyle, böyle bir tanımla ilgili bir sorun yok - GHCi, tam listeyi sorduğunuzda, burada olduğu gibi, her seferinde bir öğeyi hesaplayacak ve bu nedenle siz durmasını söyleyene kadar 3s yazdırmaya devam edecektir.

İstediğinizi elde etmek için ya sadece yazmanız push 3 aya da ona bir isim vermeniz gerekiyorsa, sadece farklı bir isim seçmeniz yeterlidir a. b = push 3 aardından bbeklediğiniz gibi davranacaktır.

4 ZhiltsoffIgor Aug 17 2020 at 16:49

Haskell'de ( sanırım, neredeyse) hiç değişken (terminolojimi düzeltmek için @amalloy sayesinde) değişken yok.

Böyle bir şey yazarsan:

x = f x

Sonsuz bir döngüye girer: f (f (f ...

Yani, orada geçmiş değeri aolan 3itilebilir.

Bu nedenle, push 3 abaşka bir değer (veya bu konuda doğrudan ghci'ye) koymalısınız.

Böyle bir döngü bazen işe yarayabilir. Şuna bir göz atın Data.Function.fix:

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

Sizin yaptığınızla aynı şeyi yapmak için kullanılabilir:

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

Yine de sonsuz döngü her zaman böyle değildir. Bir göz at:

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

Bu işlev faktöriyel gibi görünebilir, ancak sonlanmayan daldaki özyinelemeli çağrı bir dummy ( rec) ile değiştirilir . Biz ile değiştirilir bu mankeni istiyorum factFunfaktöryel almak için tekrar ve tekrar ve tekrar. fixbunu yapar:

GHCi> fix factFun 4
24

Not: Yorumumu burada tekrarlayacağım: okuyucu henüz bilmiyorsa, fixonları uzun ve ilginç bir yolculuğa davet etmek istiyorum. Bu wikibook ile gösterimsel anlambilim üzerine başlamalarını öneririm .