6

と の 2 つの関数があるf :: [a] -> bとしg :: [a] -> cます。次の 2 つの質問があります。

  1. (f &&& g) xswhereを実行しxs :: [a]、 if bothfとgループが含まれる場合、コンパイラはこれら 2 つのループを 1 つに最適化できますか? (特定の Haskell コンパイラがこれを実装しているかどうかを尋ねているわけではないことに注意してください。そのようなことが可能かどうか知りたいです。)

  2. traverse型クラスの関数はTraverse、次の行に沿って何かを最適化するのに役立ちますか?

    traverse (someCombinator f g) xs
4

1 に答える 1

9

このコードを最適化することは理論的には可能ですが、入力リストの量が異なる可能性があるためf、非常に困難です。gそれらが同じ量を消費する場合、またはg常により多くのリストを消費する場合f（またはその逆）にのみ、最適化を実行することが可能になります。停止問題は、コンパイラが複雑なコードでそのような状態を検出するのを防ぎます。

たとえば、との両方fを内部でg使用する単純な場合にのみ、さらに内省することなく簡単な最適化を実行できます。foldr

traverse実装する合理的な方法がないため、この関数はここでは役に立ちません（深刻なハッキングなしに、の複数の呼び出しを1つsomeCombinatorに変換するにはどうすればよいですか？その後、とにかく開始したところに戻ります）。a[a]

唯一の実際のオプションは、フォルダを作成fしgてフォルダに入れることです。これにより、フォルダに署名f :: a -> b -> bとが含まれるようになります。g :: a -> c -> cつまり、との値をb段階c的に計算できます。次に、\ a -> f a *** g aを使用して、従来の（この場合は右の）折り畳みで使用できるフォルダーを取得できます。

于 2012-02-08T10:50:45.563 に答える