リストのすべてのプレフィックスを生成する最も効率的な純粋に機能的なアルゴリズムは何ですか？

Question

prefixes ls = zipWith take [1 .. length ls] (repeat ls) 

これより優れた方法はありますか？直感的には、reverseまたはappendをn回適用する必要があるため、純粋に関数型言語でO（n²）以下のアルゴリズムを得ることはできないようです。しかし、私はこれをどのように証明するのか分かりません。

Answer 1

あなたは正しいと思います。すべての尾が異なるため、リストの背骨を共有することはできません。したがって、プレフィックスのリストが完全に評価された場合、Θ（n ）のスペースが必要です。生成には、Ω（n ）時間かかる場合があります。

あなたが書いた関数の（よりレイジーなバージョン）は、Data.Listにinitsとして利用可能であることに注意してください。

あなたはきちんとした最適化ができます。この方程式は、

map (foldl f z) . inits = scanl f z 

と、scanlが線形時間で実行されます。ですから、各接頭辞にしたいことを左折としてフレーズできれば、接頭辞のリストを作成するという二次的な複雑さを避けることができます。

Answer 2

これは表現に依存しませんか？リストを連続したストレージと開始インデックスと終了インデックス（バイト列に似ています）として表現すると、ストレージを共有でき、インデックスのリストを構築するために一度トラバースするだけで済みます。アルゴリズムは変更されず、表現だけが変更されます。この特定のユースケースでは、snocリスト（バイナリリストではなく、リストの始めから終わりに入れ子になっています）を使ってサブリストを共有することもできます。