10

この奇妙な動作に遭遇したとき、ポリモーフィズムと共有に関する別の質問に答えようとしていました。

GHCi では、多相定数を明示的に定義すると、共有が行われません。これは理解できます。

> let fib :: Num a => [a]; fib = 1 : 1 : zipWith (+) fib (tail fib)
> fib !! 30
1346269
(5.63 secs, 604992600 bytes)

一方、型シグネチャを省略してモノモーフィズムの制限を無効にすることで同じことを達成しようとすると、定数が突然共有されます!

> :set -XNoMonomorphismRestriction
> let fib = 1 : 1 : zipWith (+) fib (tail fib)
> :t fib
fib :: Num a => [a]
> fib !! 50
20365011074
(0.00 secs, 2110136 bytes)

どうして？！

うーん...最適化してコンパイルすると、モノモーフィズムの制限が無効になっていても高速です。

4

2 に答える 2

11

明示的な型アノテーションを与えることにより、GHCがコードについて特定の仮定をするのを防ぎます。例を示します（この質問から抜粋）：

foo (x:y:_) = x == y
foo [_]     = foo []
foo []      = False

GHCiによると、この関数のタイプは、ご想像のとおりEq a => [a] -> Boolです。ただし、この署名を使用して宣言するfooと、「あいまいな型変数」エラーが発生します。

この関数が型シグネチャなしでのみ機能する理由は、GHCでの型チェックの機能によるものです。型シグネチャを省略すると、一部の固定型に対してfooモノタイプであると見なされます。バインディンググループの入力が終了したら、タイプを一般化します。それはあなたが得るところです。[a] -> Boolaforall a. ...

一方、ポリモーフィック型シグネチャを宣言する場合、それfooがポリモーフィックであり（したがって、[]の型は最初の引数の型と一致する必要はありません）、ブームであると明示的に述べると、あいまいな型変数が得られます。

さて、これを知って、コアを比較してみましょう：

fib = 0:1:zipWith (+) fib (tail fib)
-----
fib :: forall a. Num a => [a]
[GblId, Arity=1]
fib =
  \ (@ a) ($dNum :: Num a) ->
    letrec {
      fib1 [Occ=LoopBreaker] :: [a]
      [LclId]
      fib1 =
        break<3>()
        : @ a
          (fromInteger @ a $dNum (__integer 0))
          (break<2>()
           : @ a
             (fromInteger @ a $dNum (__integer 1))
             (break<1>()
              zipWith
                @ a @ a @ a (+ @ a $dNum) fib1 (break<0>() tail @ a fib1))); } in
    fib1

そして2番目のもののために：

fib :: Num a => [a]
fib = 0:1:zipWith (+) fib (tail fib)
-----
Rec {
fib [Occ=LoopBreaker] :: forall a. Num a => [a]
[GblId, Arity=1]
fib =
  \ (@ a) ($dNum :: Num a) ->
    break<3>()
    : @ a
      (fromInteger @ a $dNum (__integer 0))
      (break<2>()
       : @ a
         (fromInteger @ a $dNum (__integer 1))
         (break<1>()
          zipWith
            @ a
            @ a
            @ a
            (+ @ a $dNum)
            (fib @ a $dNum)
            (break<0>() tail @ a (fib @ a $dNum))))
end Rec }

上記のように、明示的な型アノテーションを使用するとfoo、GHCはfib潜在的に多形的に再帰的な値として処理する必要があります。にいくつかの異なる辞書を渡すことができます。異なるとは異なることを意味するため、この時点でリストの大部分を破棄する必要があります。もちろん、最適化を使用してコンパイルすると、GHCは、「再帰呼び出し」中に辞書が変更されないことに気付き、それを最適化します。NumfibzipWith (+) fib ...Num(+)Num

fib上記のコアでは、GHCが実際にNum（という名前の）辞書$dNumを何度も提供していることがわかります。

fibバインディンググループ全体の一般化が完了する前は、型アノテーションがないと単形であると想定されていたため、サブfibパーツには全体とまったく同じ型が与えられましたfib。これのおかげで、fib次のようになります：

{-# LANGUAGE ScopedTypeVariables #-}
fib :: forall a. Num a => [a]
fib = fib'
  where
    fib' :: [a]
    fib' = 0:1:zipWith (+) fib' (tail fib')

また、タイプは固定されているため、最初に指定された1つの辞書だけを使用できます。

于 2012-06-21T22:34:24.460 に答える
4

ここではfib、どちらの場合も同じ型の引数を使用しており、ghcはこれを確認して共有を実行するのに十分賢いです。

さて、異なる型の引数で呼び出すことができる関数を使用し、デフォルトで一方が他方とは大きく異なる場合、単相性の制限がないことに悩まされます。

単相制限のない2つのx = 2 + 2コンテキストでこの用語を多形的に使用することを検討してください。一方のコンテキストでは、を使用し、show (div x 2)もう一方のコンテキストでは、を使用します。デフォルトではに設定されているため、2つの異なるタイプに適用される多相項を使用しているため、計算結果は共有されません。単相制限をオンにすると、積分と分数の両方のデフォルトを1回試行し、失敗します。show (x / 2)IntegralShowIntegerFractionalShowDouble

最近、一般化しないなどして、これらすべてを起動させるのは難しいことです。

于 2012-06-21T22:21:52.773 に答える