Scala：如何定义通用的 flatMap 和 map 方法

Question

问题：如何在特征或抽象 class 上定义一个通用的 flatMap 方法，然后可以在扩展该 trait/class 的对象上实现？

我已经使用 Scala 一段时间了，并且一直在阅读一些关于函数式编程的书籍，作为练习，我一直在尝试将 Haskell 中的一些基本类型实现为 Scala特质。我目前正在尝试制作一个定义 flatMap 方法的 Monad 特征，然后可以由另一个 class 实现——例如，自定义版本的 List——我已经运行到一个一大堆类型问题。

起初我尝试了以下方法：

trait Monad[ T[ _ ], +A ] {

  this : T[ A ] =>  // Won't compile unless the object extending this is of type 
                    // corresponding to the above type parameters
    def flatMap[ B ]( fn : A => T[ B ] ) : T[ B ]
    def map[ B ]( fn : A => B ) : T[ B ]
}

abstract class FpList[ +T ] extends Monad[ FpList, T ] {
  def tail : FpList[ T ]
  def head : T

  override def flatMap[ B ]( fn : T => FpList[ B ] ) : FpList[ B ] = this match {
    case FpNil => FpNil
    case FpList( FpNil, v ) => fn( v )
    case FpList( next, v ) => flatMap( next ) ++ fn( v )
  }

  override def map[ B ]( fn : T => B ) : FpList[ B ] = flatMap( v => FpNil :: fn( v ) )
}

以上对我的 FpList class 很好地工作，但不适用于任何不支持的类型采取 F[X] 的形式。我在尝试实现 Writer monad 时发现了这一点：

case class FpWriter[ T, C <: Monoid[ _ ] ]( value : T, context : C ) extends Monad[ FpWriter, T ] {
 ...
}

这里的问题是，由于FpWriter有两个类型参数，它不能作为类型参数传递给Monad[...]。如果我将 Monad 的定义更改为 trait Monad[ T[ _, _ ], +A ] 它不再接受 FpList 作为类型参数...

为了提出更通用的解决方案，我得出以下结论：

trait Monad[ T, +U <: T, +A ] {
  this : U =>
    def flatMap[ V <: T ]( fn : A => V ) : V
    def map[ B, C <: T ]( fn : A => B ) : C
}

abstract class FpList[ +T ] extends Monad[ FpList[ Any ], FpList[ T ], T ] {
  def tail : FpList[ T ]
  def head : T

  override def flatMap[ V <: FpList[ Any ] ]( fn : A => V ) : V = this match {
        case FpNil => FpNil.asInstanceOf[ V ]
        case FpList( FpNil, v : A ) => fn( v ).asInstanceOf[ V ]
        case FpList( next : FpList[ A ], v : A ) => 
          (flatMap( next )( fn ).asInstanceOf[ V ] ++ fn( v ).asInstanceOf[V]).asInstanceOf[ V ]
    }

  // Runtime error
  override def map[ B, C <: T ]( fn : A => B ) : C = flatMap( v => FpNil :: fn( v ) )
}

这解决了 flatMap 的问题！但是现在 map 被破坏了，因为编译器不知道 return 类型 C。在 flatMap 的情况下，传递给 flatMap 的函数 fn 的签名定义了 return 类型 V。在 map 的情况下， none 由参数 [=19] 标识的类型=] 定义 return C 类型。有没有办法向编译器阐明B和C之间的关系？

其他一些相关 questions/answers 向我指出了使用定义 B 和 C 之间关系的隐式参数的方向，但我不明白该怎么做。有什么想法吗？

更新

所以我通过以下方式尝试了 SimY4 的建议：

单子：

trait MonadStatic [ T[ _ ] ] extends ApplicativeStatic[ T ] {

    def flatMap[ A, B ]( a : T[ A ] )( fn : A => T[ B ] ) : T[ B ]

    override def map[ A, B ]( ele : T[ A ] )( fn : A => B ) : T[ B ] = flatMap( ele )( a => unit( fn( a ) ) )

    def sub[ X, Y ]( a : T[ X ], b : T[ Y ] ) : T[ Y ] = flatMap( a )( ( _ : X ) => b )

}

trait Monad [ T[ _ ], +A ] extends MonadStatic[ T ] with Applicative[ T, A ] {
    this : T[ A ] =>
        def flatMap[ A, B ]( fn : A => T[ B ] ) : T[ B ] = flatMap( this )( fn )
}

幺半群：

trait MonoidStatic [ T[ _ ] ] {
    def empty : T[ Nothing ]
    def emptyM : Monoid[ T, Nothing ] = empty.asInstanceOf[ Monoid[ T, Nothing ] ]
    def combine[ B  ]( a : T[ B ], b : T[ B ] ) : T[ B ]
    def combine[ B ]( a : Monoid[ T, B ], b : Monoid[ T, B ] ) : Monoid[ T, B ] = combine( a.native, b.native ).asInstanceOf[ Monoid[ T, B ] ]

    def concat[ B ]( eles : FpList[ T[ B ] ] ) : T[ B ] = eles match {
        case FpNil => empty.asInstanceOf[ T[ B ] ]
        case FpList( FpNil, head : T[ B ] ) => head
        case FpList( fpList : FpList[ T[ B ] ], head : T[ B ] ) => combine( concat( fpList ), head )
    }
}

trait Monoid[ T[ _ ], +A ] extends MonoidStatic[ T ] {

    this : T[ A ] =>
        def combine[ B >: A ]( a : T[ B ] ) : T[ B ] = combine( this.asInstanceOf[ T[ B ] ], a )
        def combine[ B >: A ]( a : Monoid[ T, B ] ) : T[ B ] = combine( a.native )
        def combineM[ B >: A ]( a : Monoid[ T, B ] ) : Monoid[ T,  B ] = combine( this.monoid, a )
        def native[ B >: A ] : T[ B ] = this.asInstanceOf[ T[ B ] ]
        def monoid[ B >: A ] : Monoid[ T, B ] = this.asInstanceOf[ Monoid[ T, B ] ]

}

现在是 FpWriter：

case class FpWriter[ T, A[ _ ], B ]( value : T, context : Monoid[ A, B ] ) extends Monad[ ({ type U[ X ] = FpWriter[ X, A, B ] })#U, T ] {
    override def flatMap[ R, S ]( a : FpWriter[ R, A, B ] )
                                ( fn : R => FpWriter[ S, A, B ] ) : FpWriter[ S, A, B ] = a match {
        case FpWriter( v : R, c : Monoid[ A, B ] ) =>
            val FpWriter( newV, newC : Monoid[ A, B ] ) = fn( v )
            FpWriter( newV, c.combineM( newC ) )
    }

    override def unit[ C ]( ele : C ) : FpWriter[ C, A, B ] = FpWriter( ele, context.emptyM )

    override def get[ C ]( ele : FpWriter[ C, A, B ] ) : Option[ C ] = Some( ele.value )
}

这会导致编译错误：“涉及 FpWriter 的非法循环引用”

问题似乎是我无法在 FpWriter 本身的签名中的 lambda 中使用 FpWriter。然而，看起来其他人已经尝试了这个的某些版本并且它有效。知道问题出在哪里吗？

更新

@SimY4 指出，在评论中我从 FpWriter 签名的扩展子句中遗漏了 Monad。当我按照他们建议的方式重写函数时，编译没有问题。这是我能够提出的不需要隐式转换的最佳解决方案。

Answer 1

您需要向 scala 编译器解释如何将您的 T[_, _] 转换为 T[_]。在 scala 中，一种方法是使用 lambda 类型：

case class FpWriter[T, C <: Monoid[_]]( value : T, context : C ) extends Monad[({ type L[A] = FpWriter[A, C] })#L, T] {
  ...
}

Scala：如何定义通用的 flatMap 和 map 方法

Scala: How to define generic flatMap and map methods

generics

monads

functional-programming

scala

flatmap

更新