5

質問

要素への高速アクセスと変更を可能にするデータ型を作成したいと考えています。単純な C++ 実装と同じくらい高速に実行される構造体と関数を Haskell で作成することは可能ですか?

問題の詳細

私はHaskellでコンパイラを書いています。データ型で表されるASTを取得しました。次の 1 つを考えてみましょう。

import Prelude hiding (id)

-- this is a sample data type, the real one has got a lot of constructors
data AST = A { id :: Int, x :: AST, y :: AST, z :: AST }
         | B { id :: Int }
         | C { id :: Int, x :: AST, y :: AST }
         | D { id :: Int, u :: AST, v :: AST, w :: AST}

各 AST ノードには一意の識別子があります。Haskell で次の機能を実装したいと思います。

  • 選択された ID の時間計算量getByIdの AST ノードを返すfunction 。O(1)
  • 構造に「フォーカス」を作成し、フォーカスされた要素を互いに独立して変更できます。したがって、いくつかのサブツリーに焦点を当て、そのような焦点のそれぞれをO(1)時間の複雑さで変更できるようにしたいと考えています。

Zippersについて考えていましたが、3 つの問題があります。

  1. それらは (私が知る限り) 二分木などの単純なデータ型で使用され、「左」または「右」ブランチを選択すると言えます。上記のような複雑なデータ型でそれらを使用する簡単な方法はありますか?
  2. 時間の複雑さで関数getByIdを実装することはできないと思いますよね?O(1)
  3. Zippers を使用していくつかの独立したフォーカスを作成することは不可能だと思います。独立したフォーカスとは、フォーカスを意味します。これにより、他のフォーカスを再計算する必要なく、データ型のさまざまな部分を変更できます ( O(1))。

C++ の考え方

C++ では、AST ノードへのポインタの配列を作成できますnodePtrs。にアクセスするだけで、関数nodeByIdは で実行されます。C++ 構造は変更可能であるため、.O(1)*(nodePtrs[id])O(1)

4

1 に答える 1

2

ジッパーは実際には常に入手可能だと思いますが、差別化について聞いたことがありますか?

についてgetByIdは、それが良い考えかどうかはわかりません。getById :: Int -> IO ASTおそらく、配列などでルックアップを使用するようなHaskell関数が必要です。しかし、後で値を変更できるようにしたいので (少なくとも概念的には)、getById新しく変更された AST 値を返しますか、それとも格納された最初の AST 値を返しますか? これはすべて問題になります。Haskell バージョンの ID を削除できるかどうかを確認することをお勧めします。

あなたの焦点は実行可能に聞こえると思います。ZASTそれが AST のジッパーのデータ型だと言えます。次に、おそらく次のようなものを持つことができます。

makeFocus :: ZAST -> Focus ZAST

type Focus =
  (ZAST -> ZAST) -> -- The modifier of the "below part"
  ZAST ->           -- The new "above part", you have to provide it again as it might have changed
  ZAST              -- The Result

しかし、C++ の方法ほど便利ではありません。

結論として、一歩下がって、実際にやろうとしていること (AST の最適化、アセンブリの発行など) が不変のデータ構造で効率的に実行できるかどうかを確認する必要があると思います。Haskell で変更可能な C++ データ構造の同じ仕様を達成しようとすることに心を留めるよりも。

于 2013-11-25T10:28:49.490 に答える