Haskellで抽象的なデータコンテナタイプをどのように宣言しますか？

StackOverflow https://stackoverflow.com/questions/3153789

質問

ウィリアムクックの「on Data Abstraction、Revisited」を読み、Ralf Laemmelの「The Expression Lemma」を読み直して、Haskellで以前の論文のアイデアを適用する方法を理解しようとしました。それで、私はあなたがタイプを指定せずにHaskellでどのようにしてHaskellで設定された組合機能を実装できるかを理解しようとしていますか？

役に立ちましたか？

解決

あなたが望んでいる「抽象データ型」のバージョンに応じて、複数の方法があります。

  • コンクリートが不透明なタイプ: ：クックの素敵な紙を読んでから少し経ちましたが、それを見返して、これは彼がADTとして話していることに最も近いと思います。 Haskellでこれを行う標準的な方法は、コンストラクターなしでタイプをエクスポートすることです。これがHaskellで意味すること：

    • 抽象化されたタイプの値に一致するパターンはありません

    • モジュールからエクスポートされた関数を使用する場合を除き、タイプの値を構築することはありません

    これがクックの論文とどのように関係しているか：

    • 表現の独立性： 外から、表現はアクセスできません。

    • 複数の表現の検査： ADTのモジュール内では、表現を自由に検査できます。

    • 一意の実装/モジュール： さまざまなモジュールによって異なる実装を提供できますが、通常の手段を除いてタイプは相互運用できません。使用できません Data.IntMap.null a Data.Map.Map Int a 空です。

    この手法は、特に何らかの不変性を維持する必要があるデータ型や、値を構築する能力を制限する必要があるデータ型で、Haskell標準ライブラリで広く使用されています。したがって、この場合、ペーパーからセットADTを実装する最良の方法は、次のコードです。

    import qualified Data.Set as S

    これはおそらく、より強力な抽象化の手段ではないでしょうが、より表現力のあるモジュールシステムを備えた言語である可能性があるほどです。

  • 実存的な定量化とインターフェイス: ：Haskellは実際にはありません exists そのようなキーワードですが、「実存」という用語は、特定の種類の多型タイプを説明するためにさまざまな状況で使用されます。それぞれの場合の一般的なアイデアは、値をその上で動作させる関数のコレクションを組み合わせることであり、結果は値のタイプが多型になるようにします。この関数の署名を考慮してください：

    foo :: (a, a -> Bool) -> Bool

    タイプの値を受け取りますが a, 、 なぜなら a 完全に多型ですが、その値でできることは、それに関数を適用することだけです。したがって、ある意味では、この関数内では、タプルの前半は「抽象データ型」であり、後半はその型で作業するための「インターフェイス」です。このアイデアを明示的にし、1つの関数の外側に適用できます。 実存データ型:

    data FooADT = forall a. FooADT a (a -> Bool)

foo :: FooADT -> Bool

    今、私たちはいつでもタイプの値を持っています FooADT, 、私たちが知っているのはそれだけです が存在します いくつかのタイプ a 適用できるように FooADT最初の2番目の議論。

    同じアイデアが、クラスの制約を備えた多型タイプにも当てはまります。唯一の違いは、タイプで動作する関数が、値に明示的にバンドルされるのではなく、タイプクラスによって暗黙的に提供されることです。

    さて、これはクックの紙の面で何を意味するのでしょうか？

    • 表現独立 まだ適用されます。

    • 完全な分離： 以前とは異なり、実存的に定量化されたタイプの知識は永遠に失われます。それ自体が提供するインターフェイスを除いて、表現を検査することはできません。

    • 任意の実装： 実装が必ずしも一意ではないだけでなく、それらを制限する方法はまったくありません！同じインターフェイスを提供できるものはすべて、実存的な内部にまとめて、他の値と区別できないものです。

    要するに、これはクックのオブジェクトの説明に非常に似ています。実存的なADTSの詳細については、論文 展開抽象データ型 始めるのに悪い場所ではありません。しかし、それが議論することは、基本的にクックがADTと呼んでいるものではないことに留意してください。

そして短い補遺：上記のすべてのトラブルに行って、実存的なタイプの抽象化を説明したので、私は FooADT タイプ：あなたがそれでできることは、関数を適用して Bool 結果、あります 基本的に違いはありません FooADT と Bool, 、前者がコードを難読化し、GHC拡張機能を必要とすることを除いて。私は強くお勧めします このブログ投稿を読む Haskellコードで実存的なタイプを使用する前に設定する前に。

他のヒント

比較関数を提供する必要があるか、式のインスタンスになるタイプを必要とすることができます。見る nub と nubBy この手法の例については：

nub :: (Eq a) => [a] -> [a]
nubBy :: (a -> a -> Bool) -> [a] -> [a]
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top