函数式思维: Groovy 中的函数式特性,第 1 部分

隐藏在 Groovy 中的宝藏

随着时间的推移,语言和运行时为我们处理了越来越多琐碎的细节。函数式语言在这方面体现了它的趋势,而且现代的动态语言也采用了许多函数式特性,让开发者的工作变得更轻松。这期文章将介绍 Groovy 中的一些函数式特性,并将展示如何用递归隐藏状态和构建惰性列表。

Neal Ford, 软件架构师, ThoughtWorks Inc.

Neal FordNeal Ford 是一家全球性 IT 咨询公司 ThoughtWorks 的软件架构师和 Meme Wrangler。他的工作还包括设计和开发应用程序、教材、杂志文章、课件和视频/DVD 演示,而且他是各种技术书籍的作者或编辑,包括最近的新书 The Productive Programmer。他主要的工作重心是设计和构建大型企业应用程序。他还是全球开发人员会议上的国际知名演说家。请访问他的 Web 站点



2011 年 12 月 27 日

关于本系列

本系列的目标是重新调整您对函数思维的认识,帮助您以全新的方式看待常见问题,并提升您的日常编码能力。本文探讨了函数编程概念,可将它们用于 Java™ 语言中进行函数编程的框架,在 JVM 上运行的函数编程语言,以及语言设计的未来方向。本系列面向那些了解 Java 及其抽象工作原理,但对函数语言不甚了解的开发人员。

自述:我再也不想使用非垃圾收集式的语言来工作了。我使用 C++ 这样的语言已经很多年了,我可不想失去现代语言的便利。这就是软件开发这些年来的发展过程。我们构建不同的抽象层来处理(和隐藏)琐碎的细节。随着计算机能力不断提升,我们让语言和运行时承担越来越多的工作。就在最近十年前,开发人员纷纷弃用解释性的语言,因为开发出的生产应用程序速度太慢,而现在这已经很普遍了。函数式语言的很多功能在十年前慢得让人难以忍受,但现在却发展得很好,因为它能为开发人员节约时间和精力。

我在本系列文章中介绍的很多功能将展示函数式语言和框架是如何处理琐碎细节的。然而,您无需深入某一种函数式语言就能获得函数式结构的收益。在本期和下一期文章,我将介绍一些已经嵌入到 Groovy 的函数式编程方法。

Groovy 的函数式列表(list)

Groovy 已经显著增强了Java 集合(collection)库,其中包括增加了函数化结构。Groovy 为您做的第一件事就是提供了看待列表(list)的不同角度,乍看似乎不值得一提,但却能带来一些令人关注的好处。

换个角度看列表

如果您的背景主要是 C 或类似 C 的语言(也包括 Java),您可能把列表概念化为索引化的集合。有了这种看法,使得集合的遍历变得很容易,即使有时候并未显式使用索引,如清单 1 中的 Groovy 代码所示:

清单 1. 使用(隐藏的)索引进行列表遍历
def perfectNumbers = [6, 28, 496, 8128]

def iterateList(listOfNums) {
  listOfNums.each { n ->
    println "${n}"
  }
}

iterateList(perfectNumbers)

Groovy 还包含了一个 eachWithIndex() 迭代器,它可以把索引作为参数提供给代码块,适用于需要显式访问的情况。尽管我没有在 清单 1iteraterList() 方法中使用索引,但我仍然将它当成插槽式的有序集合,如图 1 所示:

图 1. 看作是索引式插槽的列表
索引式插槽的列表的图解

许多函数式语言都以略微不同的方式来看待列表,幸运的是,Groovy 也是从这一角度看待列表的。其没有将列表看成是一个索引式的插槽,而是将它看成列表中的头一个元素(头部)和列表其余元素(尾部)的组合,如图 2 所示:

图 2. 将列表看成头部加尾部
将列表看成头部加尾部的图解

将列表看成头部加尾部,那么就可以使用递归遍历列表,如清单 2 所示:

清单 2. 使用递归进行遍历列表
def recurseList(listOfNums) {
  if (listOfNums.size == 0) return;
    println "${listOfNums.head()}"
    recurseList(listOfNums.tail())
}

recurseList(perfectNumbers)

清单 2recurseList() 方法中,我首先检查作为参数传递的列表中是否含有元素。如果没有元素,那么完成函数调用并返回。如果有元素,首先打印出列表中第一个元素,可通过 Groovy 的 head() 函数完成的,然后对列表其余元素递归调用 recurseList() 方法。

递归有着内置于平台的技术局限制(参见 参考资料),因此它也不是万能的。但对于含少量项的列表来说是安全的。我更感兴趣的是对代码结构的影响,期待着某一天这些限制能减少或消失。正是因为有了这些限制,递归版本带来的好处看上去不是很明显。为了说明这一点,请考虑一下过滤列表的问题。在清单 3 中,我展示了一个过滤方法的例子,它接受一个列表和一个判断(布尔测试),确定此元素是否在列表中:

清单 3. 使用 Groovy 进行命令式过滤
def filter(list, p) {
  def new_list = []
  list.each { i -> 
    if (p(i))
      new_list << i
  }
  new_list
}

modBy2 = { n -> n % 2 == 0}

l = filter(1..20, modBy2)

清单 3 中的代码很简单:我为想要保存的元素创建了一个变量,遍历整个列表,使用包含判断的方法检查每一个元素,然后返回已过滤项的列表。当我调用 filter() 时,我提供了一段指定过滤条件的代码块。

考虑 清单 3 中的过滤器方法的迭代实现,如清单 4 所示:

清单 4. 使用 Groovy 进行迭代过滤
def filter(list, p) {
  if (list.size() == 0) return list
  if (p(list.head()))
    [] + list.head() + filter(list.tail(), p)
  else 
    filter(list.tail(), p)
}

l = filter(1..20, {n-> n % 2 == 0})

清单 4filter() 方法中,我首先检查传递的列表的大小,如果没有元素,就立即返回。否则,将列表头部与过滤谓词进行对比,如果符合条件,将它添加到列表中(使用一个初始为空的列表来确保返回的都是正确的类型);否则,以递归方式过滤尾部。

清单 3清单 4 中的不同之处反映出一个重要的问题:谁关心状态?在命令式版本中,是。我必须创建名为 new_list 的新变量, 必须往里面添加内容, 必须在完成之后返回。在递归版本中,由语言本身来管理返回值,当递归对每个方法调用返回时,在栈上创建。请注意,清单 4filter() 方法中每一条退出路径都是一个返回调用,它会在栈上构建一个中间值。

尽管这还比不上垃圾收集带来的改善,但却说明了编程语言的一个重要趋势:去除活动的部分。如果根本就不允许我接触列表的中间结果,那么我在交互的过程中就不会引入 bug。

您可以把列表的观点转换用在其他方面的探索中,如列表的大小和范围。

Groovy 中的惰性列表

函数式语言中一项常见功能就是惰性列表:只在需要时才生成内容的列表。惰性列表可以让您将代价高昂的资源初始化进程推迟至确实需要时才进行。他们还允许创建无穷序列:没有上限的列表。如果您不需要提前设定列表有多大,那么可以在实际需要时再进行设置。

首先,我将在清单 5 中展示一个在 Groovy 中使用惰性列表的示例,然后向您演示实现的方法:

清单 5. 在 Groovy 中使用惰性列表
def prepend(val, closure) { new LazyList(val, closure) }

def integers(n) { prepend(n, { integers(n + 1) }) }

@Test
public void lazy_list_acts_like_a_list() {
  def naturalNumbers = integers(1)
  assertEquals('1 2 3 4 5 6 7 8 9 10', 
      naturalNumbers.getHead(10).join(' '))
  def evenNumbers = naturalNumbers.filter { it % 2 == 0 }
  assertEquals('2 4 6 8 10 12 14 16 18 20', 
      evenNumbers.getHead(10).join(' '))
}

清单 5 中的第一个方法 prepend() 创建了一个新的 LazyList,允许您追加值。第二个方法 integers() 通过使用 prepend() 方法返回整数的列表。我发送到 prepend() 方法的两个参数是列表的初始值和包含生成下一个值代码的代码块。integers() 方法像是一个工厂,使用前面的值和计算后续值的方法返回整数的惰性列表。

为了从列表中获取值,我调用了 getHead() 方法,该方法从列表顶部返回值的参数数量。在 清单 5 中:naturalNumbers 是所有整数的惰性序列。为了获取其中的数,我调用了 getHead() 方法,指定想要的整数的数量。如断言所示,我获取了头十个自然数的列表。通过使用 filter() 方法,我获得偶数的惰性列表,然后调用 getHead() 方法获取前 10 个偶数。

LazyList 的实现如清单 6 所示:

清单 6. LazyList 实现
class LazyList {
  private head, tail

  LazyList(head, tail) {
    this.head = head;
    this.tail = tail
  }

  def LazyList getTail() { tail ? tail() : null }

  def List getHead(n) {
    def valuesFromHead = [];
    def current = this
    n.times {
      valuesFromHead << current.head
      current = current.tail
    }
    valuesFromHead
  }

  def LazyList filter(Closure p) {
    if (p(head))
      p.owner.prepend(head, { getTail().filter(p) })
    else
      getTail().filter(p)
  }
}

惰性列表包含了一个头部和一个尾部,这在构造函数中指定的。而 getTail() 方法确保了 tail 不为空,并执行它。getHead() 方法收集了我想要返回的元素,一次收集一个,从列表头部拉出一个现有的元素,并要求尾部生成一个新值。对 n.times {} 的调用会按照要求的元素个数多次执行了这一操作,且该方法返回获得的值。

清单 5 中的 filter() 方法使用了与 清单 4 一样的递归方法,但将它作为列表的一部分实现,而不是单独的函数。

Java 中也有惰性列表(参见 参考资料),但在具有函数式特性的语言中实现起来更容易一些。惰性列表在生成资源代价较大的情形下非常有用,如获取完全数的列表。

完全数的惰性列表

如果您一直关注本系列文章,您会知道我最喜欢实验代码,查找完全数(参见 “函数式思维:函数式思考,第 1 部分”)。到目前为止,所有实现的缺点之一就是需要指定分类数目。而我想要返回完全数的惰性列表版本。为了完成此目标,我编写了高度函数式的、非常紧凑的完全数查找器,它支持惰性列表,如清单 7 所示:

清单 7. 数字分类器的简化版,其中包含了 nextPerfectNumberFrom() 方法
class NumberClassifier {
  static def factorsOf(number) {
      (1..number).findAll { i -> number % i == 0 }
  }

  static def isPerfect(number) {
      factorsOf(number).inject(0, {i, j -> i + j}) == 2 * number
  }

  static def nextPerfectNumberFrom(n) {
    while (! isPerfect(++n)) ;
    n
  }
}

如果您觉得 factorsOf()isPerfect() 方法中的代码晦涩难懂,那么您可以参阅 函数式思维:耦合和组合,第 2 部分 中关于这些方法的推导过程。新方法 nextPerfectNumber() 使用了 isPerfect() 方法来查找作为参数传递的数后面的一个完全数。该函数调用将会花费很长时间来执行,即使它对小数值也会检查(尤其是未设置如何优化代码的情况下);实际上没有那么多的完全数。

通过使用新版本的 NumberClassifier,我可以创建一个完全数的惰性列表,如清单 8 所示:

清单 8. 完全数的惰性列表
def perfectNumbers(n) { 
  prepend(n, 
    { perfectNumbers(nextPerfectNumberFrom(n)) }) };

@Test
public void infinite_perfect_number_sequence() {
  def perfectNumbers = perfectNumbers(nextPerfectNumberFrom(1))
  assertEquals([6, 28, 496], perfectNumbers.getHead(3))
}

通过使用 清单 5 中定义的 prepend() 方法,我构建了一个完全数列表,它以初始值作为头部,以及使用一个知道如何计算下一个完全数的闭包作为尾部。我使用 1 之后的第一个完全数初始化列表(使用静态导入,以便可以更容易地调用 NumberClassifier.nextPerfectNumberFrom() 方法),然后要列表返回前三个完全数。

计算新的完全数代价很大,因此我尽可能少进行此项操作。通过把它构建成惰性列表,我可以将计算推迟到最佳的时间。

如果您将 “列表” 抽象成 “带序号的插槽”,那么无穷序列处理起来更加复杂。将列表想象成 “第一个元素” 和 “列表其余部分”,这种设想会激发您去考虑列表中的元素而不是结构,从而能让您考虑像惰性列表一类的内容。


结束语

开发人员在生产力方面取得大幅飞跃的方法之一就是构建有效的抽象来隐藏细节。如果我们仍然用 0 和 1 进行编码,那么永远也不会进步。函数式语言吸引人的一个方面就是能抽象化更多的细节。JVM 的现代动态语言已经为您提供了很多这样的功能。在这期文章中,我展示了,如何在列表构造方面稍微转换一下思路就能够让语言来管理遍历过程中状态的状态。如果您将列表想象成 “头部” 和 “尾部”,那么您将能构建像惰性列表和无穷序列这样的内容。

在下一期文章中,您将会看到 Groovy 元编程方法如何让您的程序变得更加函数,允许您添加第三方函数库以使他们在 Groovy 中运行得更好。

参考资料

学习

获得产品和技术

讨论

  • 加入 developerWorks 中文社区。查看开发人员推动的博客、论坛、组和维基,并与其他 developerWorks 用户交流。

条评论

developerWorks: 登录

标有星(*)号的字段是必填字段。


需要一个 IBM ID?
忘记 IBM ID?


忘记密码?
更改您的密码

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件

 


在您首次登录 developerWorks 时,会为您创建一份个人概要。您的个人概要中的信息(您的姓名、国家/地区,以及公司名称)是公开显示的,而且会随着您发布的任何内容一起显示,除非您选择隐藏您的公司名称。您可以随时更新您的 IBM 帐户。

所有提交的信息确保安全。

选择您的昵称



当您初次登录到 developerWorks 时,将会为您创建一份概要信息,您需要指定一个昵称。您的昵称将和您在 developerWorks 发布的内容显示在一起。

昵称长度在 3 至 31 个字符之间。 您的昵称在 developerWorks 社区中必须是唯一的,并且出于隐私保护的原因,不能是您的电子邮件地址。

标有星(*)号的字段是必填字段。

(昵称长度在 3 至 31 个字符之间)

单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件.

 


所有提交的信息确保安全。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Java technology
ArticleID=783093
ArticleTitle=函数式思维: Groovy 中的函数式特性,第 1 部分
publish-date=12272011