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、それが命令型言語になりますよう、前回の1に基づきます。代わりに、それa 自体の観点からの定義です。

これが、無限のリストを取得する理由です。定義は次のように処理されます。

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

等々。Haskellの怠惰のため、このような定義に問題はありません-GHCiは、ここにあるように完全なリストを要求すると、一度に1つの要素を計算するだけなので、停止するように指示するまで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)

この関数は階乗のように見えるかもしれませんが、非終了ブランチでの再帰呼び出しはダミー(rec)に置き換えられます。factFun階乗を取得するために、このダミーを何度も何度も置き換えてもらいたいと思います。fixこれを行います:

GHCi> fix factFun 4
24

注:ここで私のコメントを複製します。読者がまだ知らない場合はfix、長くて興味深い旅行に招待したいと思います。私は彼らが表示的意味論に関するこのウィキブックスから始めることを提案します。