のようinitsに、リストを生成する非常に決定論的なアルゴリズムがあるとしData.Listます。Haskellコンパイラが実際にすべての中間結果を生成することなく、このアルゴリズムで「インデックス作成」操作を最適に実行できる方法はありますか？
たとえば、inits [1..] !! 10000かなり遅いです。コンパイラはinits、再帰などを行わずに10000番目の要素で何が生成されるかをどういうわけか推測できますか？もちろん、これと同じ考えはリストを超えて一般化することができます。
編集：ながらinits [1..] !! 10000一定であり、私はいくつかのアルゴリズム上の任意の「インデックスのような」操作について疑問に思って。たとえば\i -> inits [1..] !! i、どのi？の結果に到達するために[または最小限の]再帰が実行されないように最適化できますか？
はいといいえ。あなたがの定義を見ればData.List.inits：
inits :: [a] -> [[a]]
inits xs = [] : case xs of
[] -> []
x : xs' -> map (x :) (inits xs')
再帰的に定義されていることがわかります。つまり、結果のリストの各要素は、リストの前の要素に基づいて作成されます。したがって、n番目の要素が必要な場合は、前のn-1個の要素をすべて作成する必要があります。
これで、新しい関数を定義できます
inits' xs = [] : [take n xs | (n, _) <- zip [1..] xs]
これは同じ動作をします。を取得しようとするinits' [1..] !! 10000と、リストの連続する要素が前の要素に依存しないため、非常に迅速に終了します。もちろん、単一の要素ではなく、実際にinitのリストを生成しようとした場合、これははるかに遅くなります。
コンパイラは、のような関数から再帰を最適化できるようにするために、多くの情報を知っている必要がありますinits。とは言うものの、関数が本当に「非常に決定論的」である場合、非再帰的な方法で関数を書き直すのは簡単なはずです。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加