22

このコードをインタープリターに入力すると、メモリが急速に消費されます。

last [1..10^7] `seq` ()

これが O(1) 以上のスペースを必要とする理由がわかりません。私がそうするだけなら（Showは弱い頭の正規形を強制するので、同じはずなので、seqは冗長ですか？）：

last [1..10^7]

...うまくいきます。

通訳者以外ではこの状況を再現できません。

何が起きてる？

ここにいくつかのテストケースがあります: http://hpaste.org/69234

注意事項:

  • インタープリターで実行することにより、wtf.hs をコンパイルせずに読み込みwtf<n>、ghci と入力します。
  • コンパイルすることで、私はghc --make wtf.hs && ./wtf.
  • lastsum厳密なアキュムレータまたはリスト内の最大要素を見つける関数に置き換えることができますが、スペースリークは引き続き発生します
  • $!の代わりに使用した場合、この動作は見られませんでしseqた。
  • ()これはCAFの問題かもしれないと思ったので、ダミーパラメータを追加してみました。何も変わりません。
  • まったく使用しない と でEnum動作を再現できるため、おそらく関数 on では問題ありません。wtf5Enum
  • Num、Int、またはで問題ない可能性があります。これらがなくてもおよびIntegerで動作を再現できるからです。wtf14wtf16

Peano 算術で問題を再現して、式からリストと整数を取り出しようとしました (10^9 の最後で をフェッチします) が、 を実装しようとすると、理解できない他の共有/スペース リークの問題に遭遇しました*。

4

2 に答える 2

15

enumFromTofor Integerのインスタンスを確認する必要があり、最後は次のとおりです。

last []                 =  errorEmptyList "last"
last (x:xs)             =  last' x xs
  where last' y []     = y
        last' _ (y:ys) = last' y ys

GHC.Enum で次のように定義されています。

enumFrom x             = enumDeltaInteger  x 1
enumFromThen x y       = enumDeltaInteger  x (y-x)
enumFromTo x lim       = enumDeltaToInteger x 1 lim

どこ

enumDeltaInteger :: Integer -> Integer -> [Integer]
enumDeltaInteger x d = x `seq` (x : enumDeltaInteger (x+d) d)
-- strict accumulator, so
--     head (drop 1000000 [1 .. ]
-- works

と

enumDeltaToInteger :: Integer -> Integer -> Integer -> [Integer]
enumDeltaToInteger x delta lim
  | delta >= 0 = up_list x delta lim
  | otherwise  = dn_list x delta lim

up_list :: Integer -> Integer -> Integer -> [Integer]
up_list x0 delta lim = go (x0 :: Integer)
                where
                    go x | x > lim   = []
                         | otherwise = x : go (x+delta)

last予想どおり、完全に怠惰です。

Integer Enum クラスの場合、 に対して (明示的に) 厳密なアキュムレータがありenumFromます。境界のあるケース (例: [1..n]) では、 を呼び出しenumDeltaToIntegerてから を呼び出しますup_list。これはワーカーを使用してリストを制限に達するまで展開します。

ただし、ヘルパーup_listでは厳密です( との比較を参照してください)。xgolim

GHCi で実行すると、これは最適化されず、 を返す前に enumFromTo への単純な呼び出しが生成され()ます。

let
  it_ax6 :: ()      
  it_ax6 =
    case last
           @ GHC.Integer.Type.Integer
           (GHC.Enum.enumFromTo
              @ GHC.Integer.Type.Integer
              GHC.Num.$fEnumInteger
              (GHC.Integer.smallInteger 1)
              (GHC.Real.^
                 @ GHC.Integer.Type.Integer
                 @ GHC.Integer.Type.Integer
                 GHC.Num.$fNumInteger
                 GHC.Real.$fIntegralInteger
                 (GHC.Integer.smallInteger 10)
                 (GHC.Integer.smallInteger 7)))
    of _ -> GHC.Unit.()
in
  GHC.Base.thenIO
    @ ()
    @ [()]
    (System.IO.print @ () GHC.Show.$fShow() it_ax6)
    (GHC.Base.returnIO
       @ [()] (GHC.Types.: @ () it_ax6 (GHC.Types.[] @ ())))

seqでは、通常のケースではなく、ケースのリストを保持するのはなぜですか? enumFromTo通常のケースは、 forIntegerと forの遅延に依存して、一定の空間で適切に実行されlastます。その場合の GHCi コアは次のようになります。

let {
  it_aKj :: GHC.Integer.Type.Integer
  [LclId,
   Unf=Unf{Src=<vanilla>, TopLvl=False, Arity=0, Value=False,
           ConLike=False, Cheap=False, Expandable=False,
           Guidance=IF_ARGS [] 170 0}]
  it_aKj =
    GHC.List.last
      @ GHC.Integer.Type.Integer
      (GHC.Enum.enumFromTo
         @ GHC.Integer.Type.Integer
         GHC.Num.$fEnumInteger
         (GHC.Integer.smallInteger 1)
         (GHC.Real.^
            @ GHC.Integer.Type.Integer
            @ GHC.Integer.Type.Integer
            GHC.Num.$fNumInteger
            GHC.Real.$fIntegralInteger
            (GHC.Integer.smallInteger 10)
            (GHC.Integer.smallInteger 7))) } in
GHC.Base.thenIO
  @ ()
  @ [()]
  (System.IO.print
     @ GHC.Integer.Type.Integer GHC.Num.$fShowInteger it_aKj)
  (GHC.Base.returnIO
     @ [()]
     (GHC.Types.:
        @ ()
        (it_aKj
         `cast` (UnsafeCo GHC.Integer.Type.Integer ()
                 :: GHC.Integer.Type.Integer ~ ()))
        (GHC.Types.[] @ ())))

したがって、これらはほとんど同じですが、違いは次のとおりです。

  • seqバージョンでは、last (enumFromTo ..)内で強制されますcase。
  • 通常版では怠け者letです。
  • バージョンでseqは、値が計算されてから破棄さ()れ、結果が生成されます -- 何も結果を見ません
  • 通常の場合、検査されて表示されます。

奇妙なのは、魔法が何もないということです:

let x = case last (enumFromTo 1 n) of _ -> ()

これにより、値が保持されます。

ご覧のとおり、 の実装はup_listそのアキュムレータで厳密です (これは と比較さlimれ、リストは遅延展開されるためlast、定数空間でそれを消費できるはずです)。式を手で書くと、これが確認されます。

ghci 実行のヒープ プロファイルを実行すると、保持されているリスト全体が表示されます。

ここに画像の説明を入力

これは、少なくともサンクの連鎖ではなく、リスト全体が厳密に構築され、破棄されるまで保持されていることを示しています。

last謎は次のとおりです。ghcではなく、ghciでリスト引数を保持しているのは何ですか?

私は現在、ghci の内部 (または微妙な) 詳細を疑っています -- これは ghci チケットの価値があると思います。

于 2012-05-29T12:56:14.490 に答える
1

@nm が正しいと思います。リスト内の値を強制するものは何もないため、1+1+1+1+... サンクは最終的にスペースを殺します。

簡単なテストを作成します。

于 2012-05-29T11:28:27.133 に答える