15

Haskellで使用されているのと同様のパターンに従って、Scalaで機能的なbinary-search-treeを実装するための演習を行っています。私は次のような構造を持っています：

trait TreeNode[A] {
    def isLeaf: Boolean
    def traverse: Seq[A]
    ...
}

case class Branch[A](value: A, left: TreeNode[A], right: TreeNode[A]) extends TreeNode[A] { 
   def isLeaf: Boolean = false
   def traverse: Seq[A] = ...
   ... 
}

case class Leaf[A]() extends TreeNode[A] { 
    def isLeaf: Boolean = true
    def traverse: Seq[A] = Seq[A]()
    ... 
}

を拡張するオブジェクトのみを受け入れるように、型制約を設定したいと思います。トレイトだけでなく、A （）のビューバウンドを定義する必要があるようです。ただし、ビューバウンドが受け入れられないため、トレイトでこれを行うことはできません。AOrdered[A <% Ordered[A]]BranchLeafTreeNodeTreeNode

私が理解しているように、<%-style view-boundsは定義の構文糖衣であるため、トレイトimplicit内で手動で境界を定義するように記述する方法が必要です。TreeNodeしかし、これをどのように行うべきかはわかりません。私は少し見回しましたが、ある種の暗黙の定義が必要であるということよりもはるかに進んでいません。

誰かが私を正しい方向に向けることができますか？私はこれに完全に間違った角度からアプローチしていますか？

4

3 に答える 3

24

問題は、ビューの境界とコンテキストの境界が、特定のタイプの暗黙的なパラメーターの単なる構文上の糖衣であるということです。ジェネリッククラスの型パラメーターに適用されると（ジェネリックメソッドに適用される場合とは対照的に）、これらの暗黙的要素はクラスのコンストラクターに追加されます。トレイトにはコンストラクターがないため（つまり、パラメーターのないコンストラクターが1つしかないため）、これらの暗黙的なパラメーターを渡す場所がなく、一般的なトレイトではコンテキスト境界とビュー境界が無効になります。最も簡単な解決策はTreeNode、抽象クラスに変換することです。

abstract class TreeNode[A <% Ordered[A]]

Ben Jamesのアドバイスによると、通常、anでバインドされたコンテキストを使用する方が、 （より一般的です）でOrderingバインドされたビューよりも優れていることに注意してください。Orderedただし、問題は同じです。特性では機能しません。

クラスに変換することが実用的でない場合TreeNode（たとえば、型階層のさまざまな場所で混合する必要がある場合）、TreeNode（型の）暗黙的な値を提供する抽象メソッドを定義し、Ordered[A]それを拡張するすべてのクラスに定義させることができますそれ。残念ながら、これはより冗長で明示的ですが、この場合、これ以上のことはできません。

trait TreeNode[A] {
  implicit protected def toOrdered: A => Ordered[A]
}

case class Branch[A<%Ordered[A]](value: A, left: TreeNode[A], right: TreeNode[A]) extends TreeNode[A] { 
   protected def toOrdered = implicitly[A => Ordered[A]]
}

case class Leaf[A<%Ordered[A]]() extends TreeNode[A] { 
    protected def toOrdered = implicitly[A => Ordered[A]]
}

より簡潔な定義のために、次のように同等に定義できることに注意してくださいLeaf。

case class Leaf[A](implicit protected val toOrdered: A => Ordered[A]) extends TreeNode[A]
于 2013-01-23T16:22:57.350 に答える
15

：にタイプの抽象メンバーを要求することにより、「証拠」を提供できますA。OrderedOrdered[A]trait

trait TreeNode[A] {
  implicit val evidence: Ordered[A]
}

次に、具体的なサブタイプでこれを提供することを余儀なくされます。これは、次のことを証明していAますOrdered。

case class Leaf[A](value: A)(implicit ev: Ordered[A]) extends TreeNode[A] {
  val evidence = ev
}

A代わりに、暗黙的な型に制約することもできOrdering[A]ます。これは継承関係ではありません。それはhaskell型クラスのようなものです。ただし、上記の手法に関する実装は同じです。

于 2013-01-23T16:10:27.807 に答える
1

@ben-jamesvalの答えは素晴らしいです。クラスでの冗長なsを避けるために少し改善したいと思います。

暗黙の値を保持するトレイトで定義されているのと同じように、暗黙のコンストラクターパラメーター名を定義するという考え方です。

アイデアはこの行を避けることです：

val evidence = ev

これが完全な例です（要点）

trait PrettyPrinted[A] extends (A => String)

object PrettyPrinted {
  def apply[A](f: A => String): PrettyPrinted[A] = f(_)
}

trait Printable[A] {
  implicit def printer: PrettyPrinted[A]
}

// implicit parameter name is important
case class Person(name: String, age: Int)
                 (implicit val printer: PrettyPrinted[Person])
  extends Printable[Person]

object Person {
  implicit val printer: PrettyPrinted[Person] =
    PrettyPrinted { p =>
      s"Person[name = ${p.name}, age = ${p.age}]"
    }
}

// works also with regular classes
class Car(val name: String)
         (implicit val printer: PrettyPrinted[Car])
  extends Printable[Car]

object Car {
  implicit val printer: PrettyPrinted[Car] =
    PrettyPrinted { c =>
      s"Car[name = ${c.name}]"
    }
}
于 2018-03-16T09:05:05.553 に答える