在Scala中指定或实现具有变体类型的类型类

Question

我是Scala的新手,需要一些帮助才能解决编译错误:

[error] .../traversals  /traversals.scala:120: type mismatch;
[error]  found   : Traversable[Tree]
[error]  required: Traversable[Node]
[error] Note: Tree >: Node, but trait Traversable is invariant in type T.
[error] You may wish to define T as -T instead. (SLS 4.5)
[error]             println ("Sorted " + sorted (tree2) (monadApp,inOrder));
[error]                                                           ^
[error] one error found

我很抱歉MWE那么长,但是我把一些类型的类从Haskell转换为Scala并且在我想写一些使用它们的例子时卡住了.我并不完全理解这个问题,但似乎我的Traversable特性不允许T用某个子类型或具体实例inOrder或sorted使用该实例的函数替换它.由于编译器建议我尝试添加一些-在前面小号T的Traversable特点,将Tree在前面的inOrder定义或T前面sorted,但它并没有帮助.

 trait Applicative[M[_]] {
    def pure[a] (x: a) : M[a]
    def comp[a,b] (fx: M[a => b]) (mx: M[a]) : M[b]
    def fmap[a,b] (fx: a => b) (mx: M[a]) : M[b]
        = comp (pure (fx)) (mx)
  }

  trait Functor[F[_]] {
    def fmap[a,b] (f: a => b) (m: F[a]) : F[b]   
  }

  trait Traversable[T[_]] extends Functor[T] {
    def dist[a,M[_]] (t: T[M[a]]) (implicit app : Applicative[M]) : M[T[a]]
    def traverse[a,b,M[_]] (f: a => M[b]) (t : T[a]) (implicit app : Applicative[M]) : M[T[b]] = 
    dist (fmap(f) (t)) (app)
  }

  sealed abstract class Tree[a]
  case class Empty[a] () extends Tree[a]
  case class Node[a]  (x : a, l : Tree[a], r: Tree[a]) extends Tree[a]

  class TreeFunctor extends Functor[Tree] {
    def fmap[a,b] (f: a => b) (t: Tree[a]) =
    t match {
        case Empty () => Empty ()
        case Node (x, l, r) => Node (f (x), fmap (f) (l), fmap (f) (r))
    }
  }

  trait Monoid[A] {
    def mempty : A
    def mappend (x: A) (y: A) : A
  }

  object BoolAnd extends Monoid[Boolean] {
    def mempty = true
    def mappend (x: Boolean) (y: Boolean) = x && y    
  }

  case class K[b,a] (value: b) 

  class MonoidApplicative[m] (implicit monoid : Monoid[m]) extends Applicative[({type ?[?] = K[m,?]})#?] {
    def pure[a] (x : a) = K (monoid.mempty)
    def comp[a,b] (f : K[m,a => b]) (x : K[m,a]) = K (monoid.mappend (f.value) (x.value))
  }

  case class State[s,a] (func: s => (a,s)) 

  trait Monad[M[_]] {
    def ret[a] (x : a) : M[a]
    def bind[a,b] (mx : M[a]) (fx : a => M[b]) : M[b]
  }

  class StateMonad[S] extends Monad[({type ?[?] = State[S,?]})#?] {
    def ret[a] (x : a) = State ((s: S) => (x, s))
    def bind[a,b] (mx : State[S,a]) (fx : a => State[S,b]) 
      = State ((s : S) => (((tuple : (a,S)) => (fx (tuple._1)).func (tuple._2)) (mx.func (s))))
  }

  class MonadApp[M[_]] (implicit m : Monad[M]) extends Applicative[M] {
    def pure[a] (x : a) = m.ret (x)
    def comp[a,b] (fx : M[a => b]) (mx : M[a]) : M[b] 
      = m.bind[a => b,b] (fx) ((f : a => b) => m.bind[a,b] (mx) ((x:a) => m.ret (f (x))))
  }

  case class Comp[M[_],N[_],a] (unComp : M[N[a]])

  class CompApp[M[_], N[_]]  (implicit mapp : Applicative[M], napp: Applicative[N])  extends Applicative[({type ?[?] = Comp[M,N,?]})#?] {
    def pure[a] (x : a) = Comp (mapp.pure ( napp.pure ( x) ))
    def comp[a,b] (mf : Comp[M,N,a => b]) (mx : Comp[M,N,a]) = Comp (mapp.comp (mapp.comp (mapp.pure (napp.comp[a,b]_)) (mf.unComp)) (mx.unComp) ) 
  }

  object Main {  
    implicit def inOrder : Traversable[Tree] = new Traversable[Tree]{
        def dist[a,M[+_]] (t: Tree[M[a]]) (implicit app : Applicative[M]) 
        = t match {
            case Empty () => app.pure (Empty ())
            case Node (x, l, r) => app.comp (app.comp (app.comp(app.pure ((l : Tree[a]) => ((x: a) => ((r: Tree[a]) => Node (x,l,r))))) (dist (l) (app))) (x)) (dist (r) (app))
        }
    }   
    val emptyTree = Empty[Int]()
    val tree2 = Node(5, Node (2, Empty (), Empty ()), Node (9 , Empty (), Empty ()))
    implicit def stateMonad[a] = new StateMonad[a] ()
    implicit def monadApp = new MonadApp[({type ?[?] = State[Int,?]})#?] () {}
    implicit def andMonoidApp  = new MonoidApplicative[Boolean] () (BoolAnd);
    implicit def stateMonoidComp = new CompApp[({type ?[?] = State[Int,?]})#?, ({type ?[?] = K[Boolean,?]})#? ] () (monadApp, andMonoidApp)
    def pairSort (x : Int) : State[Int,Boolean] 
        = State ((y : Int) => (y <= x, x))
    def sorted[T[_]] (t : T[Int]) (implicit as : Applicative[({type ?[?] = State[Int,?]})#?], tr : Traversable[T]) : Boolean
        = (
           (tr.traverse[Int,Boolean,({type ?[?] = Comp[({type ?[?] = State[Int,?]})#?, ({type ?[?] = K[Boolean,?]})#? , ?]})#?] 
            ((i : Int) => 
               Comp[({type ?[?] = State[Int,?]})#?, ({type ?[?] = K[Boolean,?]})#? , Boolean] 
                 (as.fmap[Boolean, K[Boolean,Boolean]] ((x: Boolean) => K[Boolean, Boolean] (x)) (pairSort (i)))
            )
            (t) 
            //(CompApp[({type ?[?] = State[Int,?]})#?, ({type ?[?] = K[Boolean,?]})#? ])
            (stateMonoidComp)
           ).unComp.func (-10000) 
          )._1.value
    def main (args: Array[String]) 
        =   println ("Sorted " + sorted (tree2) (monadApp,inOrder));

  }

Answer 1

问题是你有两种不同的类型:Traversable[Node]和Traversable[Tree].这来自Haskell的ADT翻译.而在Haskell Node和Empty都Tree在斯卡拉他们亚型的 Tree,这会导致概念方差来发挥作用:给定A的亚型B,是T[A]的子类型T[B]？

如果我们看一个函数的类型X => Y,我们会看到它被声明Function1[-X, +Y],也就是说,它是逆变的X和协变的Y.这意味着获取Tree和返回Node的函数是获取Node和返回的函数的子类型Tree.例如:

def f[T](n: Node[T])(func: Node[T] => Tree[T]): Tree = func(n)
def zeroRoot(tree: Tree[Int]): Node[Int] = Node(0, tree, Empty())
f(Node(1, Empty(), Empty())(zeroRoot)

该函数zeroRoot有效,因为我们正在传递它Node并且它期望一个Tree(这是可以的),然后我们返回了一个Node,然后返回一个Tree(也可以).

顺便说一句,Tree应该是共同变体.

现在,反方差的另一个例子是排序类.虽然Scala由于某些技术性而不变,但正确的顺序应该是对立的.毕竟,如果你知道如何订购Tree,那么你可以订购一个Node,所以Ordering[Tree]它将是一个子类型Ordering[Node],因为第一个可以传递到第二个预期的地方.

我并没有真正密切关注代码,但有意义的是,用作排序的东西应该是反变量的.另一方面,似乎不可能产生Traversable逆变,因为Functor类型签名需要不变性.

通过Tree显式传递类型Sort或tree2明确声明为a 来解决此问题Tree.然后你会得到其他不同的问题!:)