幺半群Monoid在列表求和中的应用：空列表特殊场景问题

我定义了以下Monoid接口与MyList类，想要实现一个接收元素为Monoid类型的列表、并能对其元素求和的类。但遇到空列表场景的问题：无法获取T类型的单位元zero()来初始化求和结果。

interface Monoid<T>{
    operator fun plus(other:T):T
    fun zero():T
}
class MyList<T:Monoid<T>>(val l:List<T>){
    fun sum():T{
        var result:T = ... // 这里应该怎么写？理想情况是类似T.Zero或T.zero()这样的静态调用
        for (el in l){
            result += el
        }
        return result
    }
}

尝试过的思路都有局限：

• Java静态特性行不通，因为静态方法无法抽象，接口静态方法需要预定义；
• 反射调用需要T的实例或无参构造器，不想限制T的构造器；
• 伴生对象无法感知泛型类型T，没法定义fun zero():T；
• 为每个MyList实例单独传单位元，或者强制T有无参构造器，不够优雅。

尝试过下面的代码也不可行，因为伴生对象无法知晓外围类的泛型信息：

interface Monoid<T>{
    operator fun plus(other:T):T
    fun zero():T
}
interface NeutralForMonoid<T>{
    fun zero():T
}
class MyList<T:Monoid<T>>(val l:List<T>){
    fun sum():T{
            var result:T = ... 
// 这里应该怎么写？理想情况是类似T.Zero或T.zero()这样的静态调用
        for (el in l){
            result += el
        }
        return result
    }
    companion object : NeutralForMonoid<T>{
            ...
    }
}

需要优雅的解决方案，也欢迎指正思路错误。

在函数式编程的类型类模式下，我们可以调整Monoid的设计，把单位元zero和二元操作plus从实例方法中分离出来，变成一个独立的类型类，这样就能通过传入Monoid<T>的实例来获取单位元，同时不限制T的结构。

方案一：类型类模式（推荐） #

重新定义Monoid为类型类，包含zero和combine（替代原来的plus）：

interface Monoid<T> {
    val zero: T
    fun combine(a: T, b: T): T
}

// 给Monoid扩展plus操作符，方便使用
operator fun <T> T.plus(other: T, monoid: Monoid<T>): T = monoid.combine(this, other)

class MyList<T>(val l: List<T>) {
    // sum方法接收对应的Monoid实例
    fun sum(monoid: Monoid<T>): T {
        var result = monoid.zero
        for (el in l) {
            result = monoid.combine(result, el)
        }
        return result
    }
}

使用示例 #

比如为Int实现Monoid：

val IntMonoid = object : Monoid<Int> {
    override val zero: Int = 0
    override fun combine(a: Int, b: Int): Int = a + b
}

val list = MyList(listOf(1,2,3))
println(list.sum(IntMonoid)) // 输出6
val emptyList = MyList(emptyList<Int>())
println(emptyList.sum(IntMonoid)) // 输出0

这种方式的优势：

• 完全不限制T的构造器或结构，任何类型都可以实现对应的Monoid；
• 同一个类型可以有多个Monoid实现（比如Int可以有加法和乘法两种单位元）；
• 逻辑清晰，符合函数式编程的类型类思想。

方案二：伴生对象实现Monoid + Reified泛型 #

如果希望保留类似T.zero()的调用形式，可以让T的伴生对象实现Monoid接口，然后通过reified泛型获取伴生对象：

interface Monoid<T> {
    operator fun plus(other: T): T
}

// 定义一个接口，让伴生对象实现它
interface MonoidCompanion<T> {
    fun zero(): T
}

// 扩展函数，通过reified T获取伴生对象的zero
inline fun <reified T : Monoid<T>> zero(): T {
    val companion = T::class.companionObjectInstance
    require(companion is MonoidCompanion<T>) { "T's companion must implement MonoidCompanion<T>" }
    return companion.zero()
}

class MyList<T : Monoid<T>>(val l: List<T>) {
    inline fun sum(): T {
        var result = zero<T>()
        for (el in l) {
            result += el
        }
        return result
    }
}

使用示例 #

实现一个IntMonoid类，伴生对象实现MonoidCompanion：

class IntMonoid(val value: Int) : Monoid<IntMonoid> {
    override operator fun plus(other: IntMonoid): IntMonoid = IntMonoid(value + other.value)

    companion object : MonoidCompanion<IntMonoid> {
        override fun zero(): IntMonoid = IntMonoid(0)
    }
}

val list = MyList(listOf(IntMonoid(1), IntMonoid(2), IntMonoid(3)))
println(list.sum().value) // 输出6
val emptyList = MyList(emptyList<IntMonoid>())
println(emptyList.sum().value) // 输出0

这种方式的优势：

• 调用形式接近你想要的T.zero()；
• 不需要在sum方法中额外传参数；

局限性：

• 必须要求T的伴生对象实现MonoidCompanion，有一定限制；
• 同一个类型只能有一个伴生对象，所以同一类型只能有一种Monoid实现。

内容的提问来源于stack exchange，提问作者Paul Ivanov