パターンの前にチルダを追加すると、機能が低下するのはなぜですか？

Question

私はHaskellのコードの一部で定義された2つの機能を有している：私は（:set +sを使用して）GHCiの中からそれらの両方をテストするとき、私は発見

lengthwtilde [] = 0 
lengthwtilde ~(_:xs) = 1 + lengthwtilde xs 

lengthwotilde [] = 0 
lengthwotilde (_:xs) = 1 + lengthwotilde xs 

その lengthwtilde（パターンマッチの前にチルダを有するもの）は、 lengthwotildeよりも約3秒遅くなります。

*Main> lengthwtilde [1..10000000] 
10000000 
(19.40 secs, 1731107132 bytes) 
*Main> lengthwotilde [1..10000000] 
10000000 
(16.45 secs, 1531241716 bytes) 

なぜですか？

Answer 1

パターンマッチの前に~を追加すると、は一致しません。です。これは、パターンに余分な怠惰を追加するものだと考えることができます。そうすれば、評価に絶対に必要なものでなければ一致することはありません。ここでは簡単な例です：

Prelude> (\ (_:_) -> "non-empty") [] 
"*** Exception: <interactive>:2:2-23: Non-exhaustive patterns in lambda 

Prelude> (\ ~(_:_) -> "oops") [] 
"oops" 

は反論できないパターンマッチでは、何の束縛変数が評価されていないので、パターンマッチは、空のリストに失敗していても、エラーはありません。それはあなたの長さの機能を遅く怠惰のこの余分なラッピングです

\ xs -> let (_:_) = xs in "oops" 

：基本的に、反駁できないパターンマッチはに機能を変換します。あなたが同じを適用するとしましょう結合lengthwtildeに変換を使用すると、

lengthwtilde [] = 0 
lengthwtilde xs' = let (_:xs) = xs' in 1 + lengthwtilde xs 

を取得し、これが評価され、どのように考えてみてください。トップレベルでは1+lengthwtilde xsとなります。しかし、xsはlet-bound変数なので評価されていません。したがって、次のステップでは、最初にxsが評価されて、それがlengthwtildeの2番目のケースと一致すると判断され、プロセスが繰り返されます。

これはlengthwotildeとは対照的です。この関数では、関数の2番目の大文字と小文字をマッチングすると、引数も同様に評価されます。最終的な結果は同じですが、他のサンクを強制的に放置するよりも早く解凍できる方が効率的です。

技術的lengthwtildeはもう少し複雑です：それは、我々はにいるどの枝を決定方法を説明しますので、引数がすでにある再帰呼び出しに渡されたときしかし、それは再包まれ得る、第二分岐でを評価しました。

生産されたコアを見ることができると便利です。

Foo.lengthwotilde = 
    \ (@ t_afD) 
    (@ a_afE) 
    ($dNum_afF :: GHC.Num.Num a_afE) 
    (eta_B1 :: [t_afD]) -> 
    letrec { 
     lengthwotilde1_af2 [Occ=LoopBreaker] :: [t_afD] -> a_afE 
     [LclId, Arity=1] 
     lengthwotilde1_af2 = 
     \ (ds_dgd :: [t_afD]) -> 
      case ds_dgd of _ { 
      [] -> GHC.Num.fromInteger @ a_afE $dNum_afF (__integer 0); 
      : ds1_dge xs_af1 -> 
       GHC.Num.+ 
       @ a_afE 
       $dNum_afF 
       (GHC.Num.fromInteger @ a_afE $dNum_afF (__integer 1)) 
       (lengthwotilde1_af2 xs_af1) 
      }; } in 
    lengthwotilde1_af2 eta_B1 

メモ機能lengthwotilde1_af2は直ちに（これは、入力リストである）引数ds_dgdにcaseを行い、その後、いくつかに（サンクを形成し、ケース内部再帰：ここghc -O0から製造lengthwotildeの出力は、（です拡張）：最終的 1 +（1 +（1 +（1 +の評価を必要と

1 + len [2..] 
1 + (1 + len [3..]) 
1 + (1 + (1 + len [4..]) 

..最終的にはあなたが初めてだ追加の同じチェーンではなく、いくつかの余分となり

len [1..] 
1 + (len (if null [1..] then error else [2..])) 
1 + (len [2..]) 
1 + (1 + len (if null [2..] then error else [3..])) 

：）））

ここlengthwtilde

Foo.lengthwtilde = 
    \ (@ t_afW) 
    (@ a_afX) 
    ($dNum_afY :: GHC.Num.Num a_afX) 
    (eta_B1 :: [t_afW]) -> 
    letrec { 
     lengthwtilde1_afM [Occ=LoopBreaker] :: [t_afW] -> a_afX 
     [LclId, Arity=1] 
     lengthwtilde1_afM = 
     \ (ds_dgh :: [t_afW]) -> 
      case ds_dgh of wild_X9 { 
      [] -> GHC.Num.fromInteger @ a_afX $dNum_afY (__integer 0); 
      : ipv_sgv ipv1_sgw -> 
       GHC.Num.+ 
       @ a_afX 
       $dNum_afY 
       (GHC.Num.fromInteger @ a_afX $dNum_afY (__integer 1)) 
       (lengthwtilde1_afM 
        (case wild_X9 of _ { 
         [] -> 
         (Control.Exception.Base.irrefutPatError 
          @() "foo.hs:(3,1)-(4,42)|(_ : xs)") 
         `cast` (UnsafeCo() [t_afW] ::() ~# [t_afW]); 
         : ds1_dgk xs_aeH -> xs_aeH 
        })) 
      }; } in 
    lengthwtilde1_afM eta_B1 

これの評価が異なるサンクを形成してです反駁できないパターンの失敗を処理するロジック。

コンパイル済みコードを任意の最適化で実行していた場合、ghcはすでに評価されており、この時点で(:)コンストラクタを使用することが判明しているため、そして、コードをghc -O2でコンパイルして実行すると、両方の関数が同じ時間内に実行されます。いずれの方法もサンクのチェーンになるので、どちらもかなり悪いです。 lengthの標準的な定義は、良いfoldl'の定義と同じようにはるかに優れています。