Scala 函数式编程

2017/11/19 Scala

函数式编程

这篇文章要讲的是代数数据类型 (algebraic datatype)、范畴理论 (categorytheory)和单子 (monad)。

代数数据类型

抽象数据类型 (abstract data type)和代数数据类型 (algebraic data type)都常常以 ADT 的形式进行缩写,前者在面向对象编程中很常见,它包括我们熟悉的 Seq ,Seq 是所有序列容器的抽象。相对地,代数数据类型来源于函数式编程,你可能不太熟悉,但它同样重要。 代数数据类型这一术语的产生是由于我们将要讨论的很多种数据类型符合代数特性,也就是数学特性。这一点非常重要,因为如果能够证明类型的属性,我们就有信心认为它们是没有 bug 的,并且可以通过组合安全地构建起更复杂的数据结构和算法。

加法类型与乘法类型

Scala 类型分为加法类型 (sum type)与乘法类型 (product type)。大部分你已知的类型都是乘法类型。定义了一个case class的时候,会有多少个唯一的实例呢?

case class Person(name:Name,age:Age)

你可以拥有的Person实例的个数等于Name实例的个数乘以 Age 的实例个数。比方说,Name 封装了非空字符串,并禁止非字母字符。这样, 仍然会有无限多个有效值,但我们假设个数为 N 。同样,Age 仅限于整数值,比方说介于 0 到 130 之间。但为什么不分别使用 String 和 Int 来举例呢?因为我们一直在强调,只要有可能,类型就应该表明允许的合法状态,并防止无效状态的出现。 由于我们可以用任意的 Name 值与任意的 Age 值组合起来创建 Pearson 值,所以 Person 可能的实例个数为 131*N 。正因为如此,这样的类 型被称为乘法类型。我们接触的大部分类型都属于这个范畴。 Unit 的单个实例有个神秘的名字——() 。如果我们将它看做一个零元素的元组的话,这个古怪的名字其实是有道理的。而 一个包含单个整数值的元组,即 (Int) 或 Tuple1[Int] 可以拥有 232 个值,每个值对应一个整数值。一个没有元素的元组只能有一个实例, 因为它不能携带任何状态。 试想,如果我们拥有包含两个元素的元组(Int, String),然后向元组追加Unit,构造一个新的元组,看看会发生什么:

type unitTimesTuple2 = (Int, String, Unit)

这个类型具有多少个可能的实例?与类型(Int, String)拥有的实例个数相同。从乘法的角度看,这就像我们对实例个数乘以1。所以,这就 是 Unit 这个名字的来源,就像 1 是乘法的“单位”,0 是加法的单位一样。 加法类型的一个例子是枚举类型,如:

object Breed extends Enumeration {
    type Breed=Value
    val doberman =Value("Doberman Pinscher")
    val yorkie =Value("Yorkshire Terrier")
    val scottie=Value("Scottish Terrier")
    val dane=Value("Great Dane")
    val portie=Value("Portuguese Water Dog")
}

实现加法类型的另一个方法是使用对象的封闭继承(sealed hierarchy of object),如

sealed trait Breed {val name:String}
case object doberman extends Breed { val name = "Doberman Pinscher" }
case object yorkie extends Breed { val name = "Yorkshire Terrier" }
case object scottie extends Breed { val name = "Scottish Terrier" }
case object dane extends Breed { val name = "Great Dane" }
case object portie extends Breed { val name = "Portuguese Water Dog" }

当只需要带索引的『标志位』时,使用枚举或者对用户友好的字符串,如果需要更多的状态信息,使用对象的封装继承。

代数数据类型的属性

在数学中,代数通过三个方面定义。

  1. 一系列对象:不要与 OO 语境中的对象混淆。这里说的对象可以是数字或任何东西。
  2. 一系列操作:表示元素如何组合在一起创建新元素。
  3. 一系列规则:定义了操作与对象之间的关系。例如:对于数组,存在以下规则:(x + (y + z )) == ((x + y ) + z )(即结合律)。

范畴理论

在 Scala 社区中最具争议的辩论是多大程度上接受范畴理论。范畴理论是数学的一个分支,我认为这是函数式设计模式的来源。目前范畴理论在高级函数式编程中占有中心位置。它被率先用在 Haskell 中解决各种设计问题,并突破函数式思想的常规。 Scalaz(发音为 Scala Zed)是实现了范畴的主要 Scala 库,也是学习和实验的一个好载体。

范畴

我们从范畴的一般定义开始,其定义包括三个“实体”(类似代数的定义)。

  1. 一个包含一系列对象的类别。这与 OOP 对应的术语不同,但含义类似。

  2. 一组态射(morphism),也称为箭头(arrow)。态射是函数概念的一种推广,写为f:A->B(即Scala中的f: A => B)。对于每个态射f ,其中一个对象为域(domain),另一个为值域(codomain)。用对象这个词感觉有些奇怪,但在有些范畴中,每个对象本身就是一系列值或其他 范畴的集合。

  3. 一个称为态射组合的二元操作 ,其特性是,对于 f:A->B与 g:B->C,其组合为 g f:A->C。 态射组合满足两个公理。

  4. 每个对象 x 有且仅有一个单位态射。也就是说,当域和值域相同时, IDx 与单位态射的组合有以下属性:

  5. 结合律:对于 f:A->B,g:B->C,h:C->D,存在

Functor范畴

Functor 抽象了映射(map)操作。在范畴理论的一般特性和公理之外,Functor 还有两个属性。

  1. Functor F 能保持单位值。也就是说,域中的单位值映射到值域中,仍然是单位。
  2. Functor F 能保持组合

    Monad范畴

    如果说 Functor 是对 map 的抽象,那么有没有与 flatMap 相对应的抽象呢?的确有,就是 Monad。在范畴理论中 Functor 比 Monad 更重要;但在软件应用中,Funtor 的重要性则远比不上 Monad。 从本质上说,Monad 之所以重要,是因为它为我们提供了一个对某个值包装上下文信息的规范方法。当这个值发生变化时,Monad 可以传递给上 下文并引起相关变化。这样,就可以将值和上下文之间的耦合降到最低。而 Monad 可以通知读者上下文的存在。 这种“模式”在 Scala 中很常用,该模式率先在 Haskell 中使用,之后启发了 Scala。我们在 7.4 节接触过一些例子,包括 Option 、Either 、Try和 scalaz.Validation 。 它们都满足 Monad 特性,因为它们都支持 flatMap 及构造(case 类的 apply 方法,而不是 unit )。它们允许操作序列,并可以用不同的方式对失败进行处理,通常是返回父类型的子类实例。 Monad的推广是Arrow。Monad将一个值提升为上下文,也就是说,传递给flatMap的函数的类型为A => M[B],而Arrow将函数提升为上 下文,即(A => B)=> C [A => B]。Arrow的组合可以表示一系列的处理步骤,也就是先执行A => B,再执行B => C等。这种用法 的引用是透明的,在实际的上下文环境之外。与此相反,传递给 flatMap 的函数明确知道它的上下文,这一点体现在返回值中!

小结

这一节我没有看太明白,计算机果然是数学的。先做摘录,日后补上对这一节的理解。

Show Disqus Comments

Search

    Table of Contents