Haskell: бесконечный список, когда целое число помещается в реализацию стека
Я пытаюсь реализовать простой стек, но меня смущает, почему я получаю бесконечный список, когда помещаю целое число в стек.
Все остальные функции работают так, как я ожидал, но я не понимаю, в чем проблема 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
будет вести себя так, как вы ожидаете.
В haskell нет (я думаю, почти) изменяемых (спасибо @amalloy за исправление моей терминологии) переменных.
Если вы напишете что-то вроде этого:
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)
Эта функция может выглядеть как факториал, но рекурсивный вызов в незавершенной ветви заменяется на dummy ( rec
). Мы хотели бы, чтобы этот манекен заменялся factFun
снова и снова, чтобы получить факториал. fix
Является ли это:
GHCi> fix factFun 4
24
Примечание: продублирую здесь свой комментарий: если читатель еще не знает fix
, хочу пригласить его в долгую и интересную поездку. Я предлагаю им начать с этой викиучебника по денотационной семантике .