Haskell: elenco infinito quando l'intero viene inserito nell'implementazione dello stack

Question

Sto cercando di implementare uno Stack semplice ma sono confuso sul motivo per cui ottengo un elenco infinito quando inserisco un numero intero nello stack.

Tutte le altre funzioni funzionano come mi aspetto ma non capisco il problema push. Va storto quando provo ad assegnare uno stack vuoto a se stesso che ha spinto una variabile come la seguente:

λ > 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 non consente la mutazione. In un file sorgente, se si definisce una variabile ae poi si tenta di riassegnarla, come si fa qui con a = push 3 a, si otterrebbe un errore di compilazione. L'unico motivo per cui non lo fai è che stai lavorando in GHCi, il che ti consente di ridefinire le variabili: questa è puramente una comodità, quindi non devi continuare a pensare a nuovi nomi mentre sperimenti definizioni diverse.

E, cosa cruciale, nona = push 3 a è dare un nuovo valore a basato sul precedente, come sarebbe in un linguaggio imperativo. Invece, è una definizione in termini di se stessa .aa

Ecco perché ottieni un elenco infinito: la tua definizione viene elaborata come segue:

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

e così via. A causa della pigrizia di Haskell, non ci sono problemi con una definizione come questa: GHCi, quando chiedi l'elenco completo, come qui, calcola semplicemente un elemento alla volta, e quindi continua a stampare 3s finché non gli dici di smettere.

Per ottenere ciò che desideri, devi semplicemente digitare push 3 ao, se devi assegnargli un nome, scegli semplicemente un nome diverso da a. b = push 3 aseguito da bsi comporterà come previsto.

Answer 2

Ci sono (credo, quasi) non mutabili (grazie a @amalloy per correggere i miei terminologia) variabili in Haskell.

Se scrivi qualcosa del genere:

x = f x

Entra in un ciclo infinito: f (f (f ...

Quindi, non esiste alcun valore passato di ain cui 3possa essere spinto.

Pertanto, devi inserire push 3 aun altro valore (o direttamente nel ghci per quella materia).

Tuttavia, a volte un tale ciclo potrebbe tornare utile. Dai uno sguardo a Data.Function.fix:

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

Può essere usato per fare la stessa cosa che fai tu:

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

Tuttavia, il ciclo infinito non è sempre così. Guarda:

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

Questa funzione potrebbe sembrare fattoriale, tuttavia la chiamata ricorsiva nel ramo non di terminazione viene sostituita con una dummy ( rec). Vorremmo che questo manichino fosse sostituito factFunpiù e più volte per ottenere il fattoriale. fixfa questo:

GHCi> fix factFun 4
24

---

Nota: duplicherò qui il mio commento: se il lettore non lo sa fixancora, voglio invitarlo a un viaggio lungo e interessante. Suggerisco di iniziare con questo wikibook sulla semantica denotazionale .