我是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)); }
Daniel C. So.. 5
问题是你有两种不同的类型: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
.然后你会得到其他不同的问题!:)
问题是你有两种不同的类型: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
.然后你会得到其他不同的问题!:)