Scala | Haskell | Type Class总结

Type class in Haskell

Type class是Haskell中最重要的概念之一,它可以看做是 对一系列具有某种性质的type的抽象 (比如Eq, Functor, Monad之类的)。每个type class都定义了一组函数。一个type如果要成为某个type class,就必须成为其实例(instance)并实现type class定义的函数。表面上看起来type class和OOP中的接口(interface)的作用类似,但是type class有着更多的优点,我们将在后面比较type class与interface的特点。

在Haskell中,我们通过class关键字来定义type class。比如Monad的定义如下:

1
2
3
4
5
6
7
class Applicative m => Monad m where
(>>=) :: forall a b. m a -> (a -> m b) -> m b
(>>) :: forall a b. m a -> m b -> m b
return :: a -> m a
fail :: String -> m a

其中Applicative m => Monad m代表类型m(更严谨地说应该是type constructor,因为(m :: * -> *))同样是Applicative的实例。

我们可以通过instance关键字来实现type class的实例。比如Maybe Monad的实现如下:

1
2
3
4
5
6
7
8
9
10
data Maybe a = Nothing | Just a
deriving (Eq, Ord)
instance Monad Maybe where
(Just x) >>= k = k x
Nothing >>= _ = Nothing
(>>) = (*>)
fail _ = Nothing

Haskell引入type class是为了解决 Ad-hoc polymorphism 的问题。所谓的Ad-hoc polymorphism可以用一句话概括:

In programming languages, ad-hoc polymorphism is a kind of polymorphism in which polymorphic functions can be applied to arguments of different types, because a polymorphic function can denote a number of distinct and potentially heterogeneous implementations depending on the type of argument(s) to which it is applied.

即函数根据不同的参数类型选择不同版本的函数进行调用。Ad-hoc polymorphism在OOP里一般通过函数重载或运算符重载实现,而在Haskell中ad-hoc polymorphism就通过type class实现。比如show函数:

1
show :: Show a => a -> String

类型a必须是Show的实例,对于不同的类型ashow函数会选择对应的函数实现来进行调用,这就实现了上面所说的ad-hoc polymorphism(编译期):

1
2
3
4
5
6
Prelude> show [1.7, 6.4]
"[1.7,6.4]"
Prelude> show 2
"2"
Prelude> show $ Just 4
"Just 4"

Type class在Haskell中其实是一种语法糖,因此下面我们就来看一下GHC是如何desugar它的。

GHC处理type class的方式

我们来看一下GHC处理type class的方式。由于对于某个type,作用域内最多只能有一种某个type class的实例,因此type class可以被GHC处理成一种 “dictionary-passing style”。这里参考一下 A History of Haskell 中的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
instance Eq Int where
i1 == i2 = eqInt i1 i2
i1 /= i2 = not (i1 == i2)
instance (Eq a) => Eq [a] where
[] == [] = True
(x:xs) == (y:ys) = (x == y) && (xs == ys)
xs /= ys = not (xs == ys)
member :: Eq a => a -> [a] -> Bool
member x [] = False
member x (y:ys) | x == y = True
| otherwise = member x ys

它可以被转化成为以下形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
data Eq a = MkEq (a -> a -> Bool) (a -> a -> Bool)
eq (MkEq e _) = e
ne (MkEq _ n) = n
dEqInt :: Eq Int
dEqInt = MkEq eqInt (\x y -> not (eqInt x y))
dEqList :: Eq a -> Eq [a]
dEqList d = MkEq el (\x y -> not (el x y))
where
el [] [] = True
el (x:xs) (y:ys) = eq d x y && el xs ys
el _ _ = False
member :: Eq a -> a -> [a] -> Bool
member d x [] = False
member d x (y:ys) | eq d x y = True
| otherwise = member d x ys

我们看到,type class的定义部分被转换成了一个data type,它定义了对应type class的字典(dictionary),里面记录了type class里的函数。上面的例子中,转换后的eqne函数会从这个字典里选择对应的函数。我们再来看一下转换后的member函数。它会接受对应的字典参数,并通过eq函数从字典中提取出对应的判断函数。最后就是对应的instance实现部分了。instance部分被转换成了一个选择函数,返回一个完整的字典。比如dEqList函数会接受一个Eq a类型的字典,返回一个Eq [a]类型的字典。

简单总结一下转换过程:

  • class -> data type (dictionary)
  • instance -> selector function

Type class pattern in Scala: Implicit Objects

Scala中并没有直接通过关键字支持type class(毕竟还混合了OOP)。Scala中type class成为了一种pattern,可以通过trait加上implicit来实现。

比如要对一组“可加的元素”(即我们熟悉的幺半群Monoid)进行求和(concat)操作,在Haskell里可以这么写(和默认的Monoid实现有差别):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
{-# LANGUAGE FlexibleInstances #-}
class Monoid a where
mempty :: a
mappend :: a -> a -> a
instance Monoid Integer where
mempty = 0
mappend a b = a + b
instance Monoid String where
mempty = ""
mappend a b = a ++ b
mconcat :: Monoid a => [a] -> a
mconcat xs = foldl mappend mempty xs

而在Scala中,我们可以通过Implicit Object来实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
trait Monoid[A] {
def mempty: A
def mappend(a: A, b: A): A
}
implicit object IntMonoid extends Monoid[Int] {
override def mempty = 0
override def mappend(a: Int, b: Int) = a + b
}
implicit object StringMonoid extends Monoid[String] {
override def mempty = ""
override def mappend(a: String, b: String) = a + b
}
def mconcat[A](xs: List[A])(implicit monoid: Monoid[A]): A = {
xs.foldLeft(monoid.mempty)(monoid.mappend)
}

首先我们定义了一个Monoid trait代表幺半群(性质:封闭、可结合、有幺元),这个trait就对应Haskell中type class的定义。接着我们分别为Int类型和String类型实现了对应的Monoid实例,注意对应的Monoid实例都是implicit object。最后我们要实现一个mconcat对一组具有幺半群性质的类型的值进行”求和”计算,这里我们将Monoid实例作为了implicit参数传递进了mconcat方法中,这样根据Scala的类型系统以及implicit匹配过程,当xs的类型是List[Int]的时候,IntMonoid会作为implicit参数传入mconcat方法;而当xs的类型是List[String]的时候,StringMonoid会作为implicit参数传入mconcat方法;如果没有匹配的implicit参数就会编译失败,从而确保了类型安全。是不是很奇妙呢?当然我们也可以用Scala的context bound语法糖省略掉implicit参数:

1
2
3
4
def mconcat[A : Monoid](xs: List[A]): A = {
val monoid = implicitly[Monoid[A]]
xs.foldLeft(monoid.mempty)(monoid.mappend)
}

Type class与接口的对比及优点

从上面的代码,我们可以看出,type class和trait/interface作用类似,都是对某一系列类型抽象出特定的行为。那么type class与trait/interface相比有什么优点呢?想象一下,如果用interface的话,每个sub-class都要在其body内实现对应的函数。这样如果要给现有的类实现这个interface的话,就必须要修改原类,在原类中增加对应的实现,这显然不符合Open Closed Principle(对扩展开放,对修改关闭)。所以OOP中提出了诸如 适配器模式 这样的设计模式用于扩展已有的类,但写各种adapter增加了代码的冗杂程度。

而对于type class pattern来说,实现type class实例的代码并不写在类型定义中,而是在外部实现一个对应type class的实例。这样,我们要给现有的类型实现一个type class的话就不需要更改原有类型的定义了,只需要实现对应的type class实例就可以了。这其实就是 抽象与实现分离,即类型定义与约束实现是分离的,某个类型并不清楚自己属于某个type class。与接口的方式相比,type class符合Open Closed Principle。

上面我们提到过,编译器会根据一定的机制在 编译期 自动寻找需要的type class实例,其中Haskell底层是通过转换成字典的形式让编译器寻找type class实例,而Scala中则是通过传入implicit参数的方式让编译器寻找type class实例,这保证了类型安全。

相比Haskell而言,Scala中的type class pattern更加灵活(托implicit的福),比如:

  • 结合context bound语法糖,Scala中可以方便的组合多个type class,如A : Eq : Ord
  • Type class可以有默认实现(default implicit parameter)
  • Scala中type class实例是具名的(implicit object),因此同一种类型可以有不同的type class实例,并且可以通过控制作用域(通过import)来选择不同的实例

当然type class还有更多的高级玩法,以后实践的多了再慢慢总结。。。


References

文章目录
  1. 1. Type class in Haskell
  2. 2. GHC处理type class的方式
  3. 3. Type class pattern in Scala: Implicit Objects
  4. 4. Type class与接口的对比及优点
  5. 5. References