タイプクラスで2つの操作が通勤することを指定するにはどうすればよいですか？

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

質問

私は読み始めました CRDTSに関するこの論文, 、これは、データを変更する操作が通勤であることを確認することにより、変更可能なデータを同時に共有する方法です。これはHaskellの抽象化の良い候補になるように思われました。そのタイプで通勤するデータ型と操作を指定するCRDTのタイプクラスを提供し、ライブラリの作成に取り組み、同時プロセス間の更新を実際に共有します。

私が理解できないのは、タイプクラスの仕様に操作が通勤しなければならないという契約をどのように表現するかです。

簡単な例：

class Direction a where
  turnLeft :: a -> a
  turnRight :: a -> a

それを保証するものはありません turnLeft . turnRight と同じです turnRight . turnLeft. 。フォールバックは、Monad Lawsに相当するものを指定することであると思います。コメントを使用して、タイプシステムによって施行されていない制約を指定します。

役に立ちましたか？

解決

あなたが望むのは、プルーフの負担を含むタイプクラス、以下の擬似ハスケルのようなものです。

class Direction a where
    turnLeft  :: a -> a
    turnRight :: a -> a
    proofburden (forall a. turnLeft (turnRight a) === turnRight (turnLeft a))

ここでは、すべてのインスタンスが、コンパイラがチェックを入力するための関数と証明の両方を提供する必要があります。 Haskellには証拠の概念がないため、これは（Haskellのために）希望に満ちた考え方です。

Otoh、Coqは、Haskellに抽出できる、依存して型付けられた言語の証明アシスタントです。私は使用したことがありませんが Coqのタイプクラス 以前は、簡単な検索が実り多いもので、例：

Class EqDec (A : Type) := {
   eqb : A -> A -> bool ;
   eqb_leibniz : forall x y, eqb x y = true -> x = y }.

したがって、高度な言語のように見えます できる これを行いますが、標準的な開発者の学習曲線を下げる際にやるべきことは間違いありません。

他のヒント

さらに、Tommdの回答に加えて、AGDAを同じ効果に使用できます。タイプクラスはありませんが、レコードからほとんどの機能（動的ディスパッチを除いて）を取得します。

record Direction (a : Set) : Set₁ where
  field
    turnLeft  : a → a
    turnRight : a → a
    commLaw   : ∀ x → turnLeft (turnRight x) ≡ turnRight (turnLeft x)

私は投稿を編集し、なぜあなたがHaskellでこれを行えないのかという質問に答えると思いました。

Haskell（+拡張機能）では、上記のAGDAコードで使用される同等性を表すことができます。

{-# LANGUAGE GADTs, KindSignatures, TypeOperators #-}

data (:=:) a :: * -> * where
  Refl :: a :=: a

これは、2つのタイプが等しいという定理を表しています。例えば a に相当します b は a :=: b.

私たちが同等の場合、コンストラクターを使用できます Refl. 。これを使用して、定理（タイプ）の証明（値）で関数を実行できます。

-- symmetry
sym :: a :=: b -> b :=: a
sym Refl = Refl

-- transitivity
trans :: a :=: b -> b :=: c -> a :=: c
trans Refl Refl = Refl

これらはすべてタイプ修正されているため、真です。しかし、これ。

wrong :: a :=: b
wrong = Refl

明らかに間違っており、タイプチェックで実際に失敗します。

ただし、これらすべてを通じて、値とタイプの間の障壁は壊れていません。値、値レベルの関数、および証明は、コロンの片側にまだ生きています。タイプ、タイプレベルの関数、および定理は、他方に存在します。あなたの turnLeft と turnRight 値レベルの関数であるため、定理に関与することはできません。

Agda と coq 障壁が存在しないか、物事が交差することが許可されていない依存型の言語です。 Strathclyde Haskell Enhancement（彼女） Haskellコードのプリプロセッサであり、DTPのHaskellへの効果の一部をcheすることができます。これは、タイプの世界のバリューワールドからのデータを複製することで行います。バリューレベルの関数の複製をまだ処理しているとは思わないので、もしそうなら、私の予想は、これがそれを処理するには複雑すぎるかもしれません。

すでに述べているように、タイプシステムを使用してHaskellでこれを直接実施する方法はありません。しかし、単にコメントの制約を指定するだけでは十分に満足していない場合、中間点として、目的の代数特性にQuickCheckテストを提供できます。

これらの線に沿った何かは、すでに チェッカーパッケージ;インスピレーションを求めて相談したい場合があります。

私が理解できないのは、タイプクラスの仕様に操作が通勤しなければならないという契約をどのように表現するかです。

あなたがそれを理解できない理由は、それが不可能だということです。少なくともHaskellではなく、この種のプロパティをタイプでエンコードすることはできません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top