37

数か月前にコンビナトリアル検索を行うために作成したコードを再検討しましたが、以前は型クラスで達成していたことを実行するための代替のより簡単な方法があることに気付きました。

具体的には、私は以前、探索問題の型の型クラスを持っていました。これには、型の状態、型sのアクション(状態に対する操作)a、初期状態、(アクション、状態)ペアのリストを取得する方法、および状態が解決策であるかどうかをテストする方法:

class Problem p s a where
    initial   :: p s a -> s
    successor :: p s a -> s -> [(a,s)]
    goaltest  :: p s a -> s -> Bool

MultiParameterTypeClass拡張機能が必要であり、このクラスのインスタンスを作成する場合は通常、FlexibleInstancesと、場合によってはTypeSynonymInstancesが必要になるため、これはやや不十分です。また、関数のシグネチャが乱雑になります。

pathToSolution :: Problem p => p s a -> [(a,s)]

私は今日、クラスを完全に取り除き、代わりに次の行に沿って型を使用できることに気づきました

data Problem s a {
    initial   :: s,
    successor :: s -> [(a,s)],
    goaltest  :: s -> Bool
}

これには拡張機能は必要ありません。関数のシグネチャは見栄えが良くなります。

pathToSolution :: Problem s a -> [(a,s)]

そして、最も重要なことは、型クラスの代わりにこの抽象化を使用するようにコードをリファクタリングした後、以前よりも15〜20%少ない行が残っていることを発見しました。

最大の利点は、型クラスを使用して抽象化を作成したコードでした-以前は、古いデータ構造を複雑な方法でラップする新しいデータ構造を作成し、それらをProblemクラスのインスタンスに作成する必要がありました(より多くの言語拡張が必要でした)-たくさん比較的単純なことを行うためのコード行の数。リファクタリング後、私はちょうど私が望んでいたことを正確に実行するいくつかの関数を持っていました。

私は今、コードの残りの部分を調べて、型クラスを型に置き換えて、より多くの勝利を収めることができるインスタンスを見つけようとしています。

私の質問は、このリファクタリングはどのような状況で機能しないのでしょうか?実際には、データ型ではなく型クラスを使用する方が良い場合があります。また、これらの状況を事前に認識して、コストのかかるリファクタリングを行う必要がないようにするにはどうすればよいでしょうか。

4

3 に答える 3

22

タイプとクラスの両方が同じプログラムに存在する状況を考えてみましょう。タイプはクラスのインスタンスにすることができますが、それはかなり些細なことです。さらに興味深いのは、関数を記述できることですfromProblemClass :: (CProblem p s a) => p s a -> TProblem s a

fromProblemClass実行したリファクタリングは、インスタンスとして使用されるものを作成するすべての場所を手動でインライン化し、代わりにインスタンスをCProblem受け入れるすべての関数を受け入れるようにすることとほぼ同じです。CProblemTProblem

このリファクタリングの興味深い部分はの定義TProblemと実装だけなので、fromProblemClass他のクラスにも同様の型と関数を記述できる場合は、同様にリファクタリングしてクラスを完全に削除できます。

これはいつ機能しますか?

の実装について考えてくださいfromProblemClassp基本的に、クラスの各関数をインスタンスタイプの値に部分的に適用し、その過程でパラメーター(タイプが置き換えるもの)への参照を削除します。

型クラスのリファクタリングが簡単な状況は、同様のパターンに従います。

これはいつ逆効果ですか?

関数Showのみが定義された、の簡略化されたバージョンを想像してみてください。showこれにより、同じリファクタリング、適用show、および各インスタンスの置換が可能になりますString。明らかに、ここで何かが失われました。つまり、元のタイプを操作してString、さまざまな時点でそれらをに変換する機能です。の価値はShow、さまざまな無関係なタイプで定義されていることです。

経験則として、クラスのインスタンスであるタイプに固有の多くの異なる関数があり、これらがクラス関数と同じコードで使用されることが多い場合は、変換を遅らせると便利です。型を個別に処理するコードとクラスを使用するコードの間に明確な境界線がある場合は、変換関数の方が適切であり、型クラスは構文上の利便性が低くなります。型がクラス関数を介してほぼ排他的に使用される場合、型クラスはおそらく完全に不要です。

これはいつ不可能ですか?

ちなみに、ここでのリファクタリングは、オブジェクト指向言語のクラスとインターフェースの違いに似ています。同様に、このリファクタリングが不可能な型クラスは、多くのオブジェクト指向言語で直接表現できないものです。

さらに重要なのは、この方法で簡単に翻訳できないものの例です。

  • 関数の結果タイプや非関数値など、共変位置にのみ表示されるクラスのタイプパラメーター。ここでの注目すべき犯罪者はmemptyのためでMonoidあり、returnのためMonadです。

  • 関数の型にクラスの型パラメーターが複数回現れることで、これが本当に不可能になることはないかもしれませんが、問題は非常に複雑になります。ここでの注目すべき違反者には、、、EqおよびOrd基本的にすべての数値クラスが含まれます。

  • より高い種類の自明ではない使用、その詳細はどのように特定するかはわかりませんが、ここ(>>=)Monadは注目すべき犯罪者です。一方、pクラスのパラメータは問題ではありません。

  • マルチパラメータ型クラスの重要な使用。これは、ピン留めする方法も不明であり、実際には非常に複雑になり、オブジェクト指向言語での多重ディスパッチに匹敵します。ここでも、クラスに問題はありません。

上記のことを考えると、このリファクタリングは多くの標準型クラスでは不可能あり、いくつかの例外では逆効果になることに注意してください。これは偶然ではありません。:]

このリファクタリングを適用することで何を諦めますか?

元のタイプを区別する機能を放棄します。これは明白に聞こえますが、潜在的に重要です。元のクラスインスタンスタイプのどれを使用するかを本当に制御する必要がある場合、このリファクタリングを適用すると、ある程度のタイプの安全性が失われます。これは、ジャンプすることによってのみ回復できます。実行時に不変条件を確保するために他の場所で使用されるのと同じ種類のフープ。

逆に、さまざまなインスタンスタイプを交換可能にする必要がある状況がある場合(これの典型的な症状であると述べた複雑なラッピング)、元のタイプを破棄することで大きなメリットが得られます。これはほとんどの場合、元のデータ自体を実際にはあまり気にせず、他のデータをどのように操作できるかを気にする場合です。したがって、関数のレコードを直接使用することは、間接参照の追加レイヤーよりも自然です。

上記のように、これはOOPとそれが最も適している問題のタイプに密接に関連しているだけでなく、MLスタイルの言語で典型的なものからの表現問題の「反対側」を表しています。

于 2012-09-05T19:09:17.760 に答える
5

あなたのリファクタリングは、Luke Palmerによるこのブログエントリ「HaskellAntipattern:ExistentialTypeclass」と密接に関連しています。

リファクタリングが常に機能することを証明できると思います。なんで?直感的には、ある型Fooに十分な情報が含まれているため、クラスのインスタンスにすることができるため、必要な情報を正確に含むに 関連情報を「投影」Problemする関数をいつでも作成できます。Foo -> ProblemFooProblem

もう少し正式に、リファクタリングが常に機能するという証拠をスケッチできます。まず、ステージを設定するために、次のコードはProblemクラスインスタンスの具象CanonicalProblem型への変換を定義します。

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

class Problem p s a where
    initial   :: p s a -> s
    successor :: p s a -> s -> [(a,s)]
    goaltest  :: p s a -> s -> Bool

data CanonicalProblem s a = CanonicalProblem {
    initial'   :: s,
    successor' :: s -> [(a,s)],
    goaltest'  :: s -> Bool
}

instance Problem CanonicalProblem s a where
    initial = initial'
    successor = successor'
    goaltest = goaltest'

canonicalize :: Problem p s a => p s a -> CanonicalProblem s a
canonicalize p = CanonicalProblem {
    initial' = initial p,
    successor' = successor p,
    goaltest' = goaltest p
}

ここで、次のことを証明したいと思います。

  1. Fooのような任意のタイプの場合、任意のに適用した場合と同じ結果を生成する関数instance Problem Foo s aを記述できます。canonicalizeFoo :: Foo s a -> CanonicalProblem s acanonicalizeFoo s a
  2. Problemクラスを使用する関数を、代わりに使用する同等の関数に書き換えることができますCanonicalProblem。たとえば、を持っている場合は、と同等のをsolve :: Problem p s a => p s a -> r書くことができますcanonicalSolve :: CanonicalProblem s a -> rsolve . canonicalize

証明をスケッチします。(1)の場合、次のインスタンスを持つタイプがあるFooとします。Problem

instance Problem Foo s a where
    initial = initialFoo
    successor = successorFoo
    goaltest = goaltestFoo

次にx :: Foo s a、置換によって次のことを簡単に証明できます。

-- definition of canonicalize
canonicalize :: Problem p s a => p s a -> CanonicalProblem s a
canonicalize x = CanonicalProblem {
                     initial' = initial x,
                     successor' = successor x,
                     goaltest' = goaltest x
                 }

-- specialize to the Problem instance for Foo s a
canonicalize :: Foo s a -> CanonicalProblem s a
canonicalize x = CanonicalProblem {
                     initial' = initialFoo x,
                     successor' = successorFoo x,
                     goaltest' = goaltestFoo x
                 }

後者は、目的の関数を定義するために直接使用できますcanonicalizeFoo

(2)の場合、任意の関数(または制約solve :: Problem p s a => p s a -> rを含む同様のタイプ)、および次のような任意のタイプの場合:ProblemFooinstance Problem Foo s a

  • メソッドの定義canonicalSolve :: CanonicalProblem s a -> r'を取得し、すべてのオカレンスをインスタンス定義solveに置き換えて定義します。ProblemCanonicalProblem
  • x :: Foo s a任意のについて、solve xがと同等であることを証明しcanonicalSolve (canonicalize x)ます。

(2)の具体的な証明には、具体的な定義solveまたは関連する関数が必要です。一般的な証明は、次の2つの方法のいずれかになります。

  • Problem p s a制約のあるすべてのタイプの誘導。
  • すべてのProblem関数が関数の小さなサブセットに関して記述できることを証明し、このサブセットにCanonicalProblem同等のものがあること、およびそれらを一緒に使用するさまざまな方法が同等性を維持することを証明します。
于 2012-09-05T19:53:31.330 に答える
1

OOPバックグラウンドの場合。タイプクラスはJavaのインターフェースと考えることができます。これらは通常、異なるデータ型に同じインターフェイスを提供する場合に使用されます。通常、それぞれにデータ型固有の実装が含まれます。

あなたの場合、型クラスを使用する必要はありません、それはあなたのコードを過度に複雑にするだけです。より多くの情報を得るために、あなたはより良い理解のためにいつでもhaskellwikiを参照することができます。 http://www.haskell.org/haskellwiki/OOP_vs_type_classes

一般的な経験則は次のとおりです。型クラスが必要かどうか疑わしい場合は、おそらくそれらは必要ありません。

于 2012-09-05T18:06:54.100 に答える