Haskell : 정수가 스택 구현에 푸시 될 때 무한 목록

Question

간단한 스택을 구현하려고하는데 정수를 스택에 푸시 할 때 무한 목록이 나타나는 이유가 혼란 스럽습니다.

다른 모든 기능은 예상대로 작동하지만 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)

Answer 1

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예상대로 작동합니다.

Answer 2

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)

이 함수는 팩토리얼처럼 보일 수 있지만 비 종료 분기의 재귀 호출은 더미 ( rec) 로 대체됩니다 . factFun팩토리얼을 얻기 위해이 더미를 계속해서 바꾸고 싶습니다 . fix이렇게 :

GHCi> fix factFun 4
24

---

참고 : 여기에 내 의견을 복제하겠습니다. 독자가 fix아직 모르는 경우 길고 흥미로운 여행에 초대하고 싶습니다. 표시 의미론에 관한 이 위키 북으로 시작하는 것이 좋습니다 .