Haskell: бесконечный список, когда целое число помещается в реализацию стека

Aug 17 2020

Я пытаюсь реализовать простой стек, но меня смущает, почему я получаю бесконечный список, когда помещаю целое число в стек.

Все остальные функции работают так, как я ожидал, но я не понимаю, в чем проблема 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)

Ответы

8 RobinZigmond Aug 17 2020 at 16:52

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будет вести себя так, как вы ожидаете.

4 ZhiltsoffIgor Aug 17 2020 at 16:49

В 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, хочу пригласить его в долгую и интересную поездку. Я предлагаю им начать с этой викиучебника по денотационной семантике .