2016-03-07

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的定义如下：

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的实现如下：

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的实例，对于不同的类型a，show函数会选择对应的函数实现来进行调用，这就实现了上面所说的ad-hoc polymorphism(编译期):

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 中的例子：

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

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

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里的函数。上面的例子中，转换后的eq和ne函数会从这个字典里选择对应的函数。我们再来看一下转换后的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实现有差别)：

{-# 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来实现：

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参数：

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

本文标题:Scala | Haskell | Type Class总结

文章作者:sczyh30

发布时间:2016年03月07日

原始链接:http://www.sczyh30.com/posts/Functional-Programming/typeclass-scala-haskell/

许可协议: "知识共享-保持署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。