函数式思维: 运用函数式思维,第 3 部分

过滤、单元测试和代码重用的技巧

系列文章 函数式思维 的作者 Neal Ford 将继续介绍函数式编程的构造和范例。您将了解 Scala 中的数字分类 (number-classification) 代码以及函数式世界中的单元测试。接下来,您将了解部分应用和局部套用 (currying),即两种简化代码重用的函数式方法,还将了解递归在函数式思维中发挥作用的方式。

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

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



2011 年 9 月 07 日

关于本系列

本系列文章旨在将您的思维方式向函数式思维方式的方向调整,让您以全新的角度来思考常见问题,并提高您的日常编码工作。本系列介绍了函数式编程概念,函数式编程在 Java 语言中运行的框架、在 JVM 上运行的函数式编程语言、以及语言设计未来的一些方向。本系列主要面向了解 Java 以及其抽象层的工作原理、但缺乏函数式语言使用经验的开发人员。

函数式思维函数式思维:函数式思考,第 1 部分函数式思维:运用函数式思维,第 2 部分 中,我介绍了一些函数式编程内容以及它们与 Java™ 及相关语言的关系。在本文中,我们将继续探讨这些内容,介绍如何使用 Scala 实现前两期文章中的数字分类器,此外还将讨论一些学术性话题,如局部套用部分应用递归

Scala 的数字分类器

我直到最后才演示使用 Scala 编写的数字分类器,因为它涉及的语法内容是所有语言中最少的,至少对于 Java 开发人员是这样。(我们来回顾一下分类器的要求:对于任何大于 1 的正整数,必须将其归为以下几个类别:完全数过剩数亏数。完全数是指该数的因子(除了该数本身外)相加的总和正好等于它本身。过剩数是指所有因子的和大于该数,而亏数是指该数的因子的总和小于该数。清单 1 显示了 Scala 版本的数字分类器:

清单 1. Scala 版本的数字分类器
package com.nealford.conf.ft.numberclassifier

object NumberClassifier {

  def isFactor(number: Int, potentialFactor: Int) =
    number % potentialFactor == 0

  def factors(number: Int) =
    (1 to number) filter (number % _ == 0)

  def sum(factors: Seq[Int]) =
    factors.foldLeft(0)(_ + _)

  def isPerfect(number: Int) =
    sum(factors(number)) - number == number

  def isAbundant(number: Int) =
    sum(factors(number)) - number > number

  def isDeficient(number: Int) =
    sum(factors(number)) - number < number
}

即使您之前对 Scala 一无所知,仍然可以非常轻松地阅读该代码。和以前一样,您需要注意 factors()sum() 方法。factors() 方法获得从 1 到目标数字之间的数字的列表,并应用 Scala 的内置 filter() 方法,使用右侧的代码块作为过滤条件(或称为谓语)。代码块利用了 Scala 的隐式参数,在不需要某个命名变量时,可以用占位符 (_) 暂时替代。由于 Scala 的语法非常灵活,所以您可以像调用一个运算符一样调用 filter() 方法。如果愿意的话,还可以使用 (1 to number).filter((number % _ == 0))

sum() 方法使用了您目前已经非常熟悉的 fold left 运算(在 Scala 中,实现为 foldLeft() 方法)。在本例中,我不需要命名变量,因此将 _ 用作为一个占位符,利用这种简单、明了的语法来定义代码块。foldLeft() 方法与函数 Java 库中具有类似名称的方法的功能是一样的(请参阅 参考资料),本系列的 函数式思维:函数式思考,第 1 部分 文章对此进行了介绍:

  1. 获取初始化值,并通过在列的首个元素上的操作来与其组合。
  2. 获取结果并对下一个元素实施同样的操作。
  3. 持续进行该操作直到列表为空。

当您对一列数应用运算(如求和),需要执行以下操作:从零开始,加上第一个元素,获取结果并将其加到第二个数上,一直操作,直至列的末尾。

单元测试

尽管我没有展示以前版本的单元测试,但实际上所有的示例都已经进行了测试。Scala 提供了一个有效的单元测试库,名为 ScalaTest(请参阅 参考资源)。清单 2 展示了为检验 清单 1 中的 isPerfect() 方法而编写的第一个测试方法:

清单 2. Scala 数字分类器的单元测试
@Test def negative_perfection() {
  for (i <- 1 until 10000)
    if (Set(6, 28, 496, 8128).contains(i))
      assertTrue(NumberClassifier.isPerfect(i))
    else
      assertFalse(NumberClassifier.isPerfect(i))
}

和您一样,我也在尝试以更加函数化的方式进行思考,而 清单 2 中的代码存在两个问题。第一,它以迭代方式执行操作,这不利于紧急式思考 (imperative thinking)。其次,我并不关心 if 语句的二进制总受器 (catch-all)。我试图解决的问题是确保我的数字分类器不会将非完全数识别为完全数。清单 3 展示了这个问题的解决方法,与清单 2 稍有不同:

清单 3. 完全数分类的另一种测试方法
@Test def alternate_perfection() {
  assertEquals(List(6, 28, 496, 8128),
              (1 until 10000) filter (NumberClassifier.isPerfect(_)))
}

清单 3 断定 1 到 100000 之间的完全数为已知完全数列表中的数字。函数式思维不仅针对您的代码,还包括您思考测试的方式。


部分应用和局部套用

我所展示的用于过滤列表的函数方法在函数编程语言和库中非常普遍。我使用这种功能将代码作为参数进行传递(清单 3 中的 filter() 方法),展示一种不同的代码重用思维。如果您过去使用的是传统的、受设计模式驱动的面向对象语言,那么可以将此方法与 Gang of Four 设计模式 一书中的 Template Method 设计模式进行比较。(请参阅 参考资料)。Template Method 模式定义了基类算法的骨架,使用了抽象方法和覆盖将具体细节放到子类中。通过使用复合,函数式方法允许您将功能传递给方法,从而恰当地应用该功能。

另一种实现代码重用的方式是通过局部套用(currying)。它以数学家 Haskell Curry(Haskell 编程语言也是以该数学家命名)的名字命名,其作用是对多参数函数进行了转换,可将它用作一系列单参数函数进行调用。与此密切相关的是部分应用,该技巧可以将固定值分配给函数的一个或多个参数,从而生成另一个更小的 arity 函数(函数的参数的个数)。要了解两种代码重用方式的差异,首先应查看清单 4 中的 Groovy 代码,其中演示了局部套用的用法:

清单 4. Groovy 中的局部套用
def product = { x, y -> return x * y }

def quadrate = product.curry(4)
def octate = product.curry(8) 

println "4x4: ${quadrate.call(4)}"
println "5x8: ${octate(5)}"

清单 4 中,我将 product 定义为一个代码块,它接受两个参数。通过使用 Groovy 的内置 curry() 方法,我使用 product 作为两个新代码块的构建块:quadrateoctate。Groovy 简化了对代码块的调用:您可以显式执行 call() 方法,或使用提供的语言级别的语法糖:在代码块名称后面放置一组包含任意参数的圆括号(例如,如 octate(5) 所示)。

部分应用是一种更广泛的技巧,它与局部套用类似,但是生成的函数并不限于单函数。Groovy 使用 curry() 方法处理局部套用和部分应用,如清单 5 所示:

清单 5. 部分应用和局部套用均使用 Groovy 的 curry() 方法
def volume = { h, w, l -> return h * w * l }
def area = volume.curry(1)
def lengthPA = volume.curry(1, 1) //partial application
def lengthC = volume.curry(1).curry(1) // currying

println "The volume of the 2x3x4 rectangular solid is ${volume(2, 3, 4)}"
println "The area of the 3x4 rectangle is ${area(3, 4)}"
println "The length of the 6 line is ${lengthPA(6)}"
println "The length of the 6 line via curried function is ${lengthC(6)}"

清单 5 中的 volume 代码块使用常用公式计算长方体的体积。我创建了一个 area 代码块(计算矩形的面积),将 volume 的第一个维度(h 用于表示高度)确定为 1。要使用 volume 作为代码块的构建块并返回线段的长度,可以执行部分应用或局部套用。lengthPA 使用部分应用将头两个参数的每一个确定为 1lengthC 通过应用两次局部套用生成了相同的结果。这两者之间的差别非常微小,最终结果也是相同的,但是如果您在一名函数编程人员的面前混用局部套用部分应用,那么他一定会纠正您的说法。

函数式编程为您提供了新的、不同的构建块,可以实现命令式语言使用其他机制实现的相同效果。这些构建块之间的关系是经过精心设计的。在以前的文章中,我展示了通过复合实现的代码重用机制。因此,您可以将局部套用和复合组合在一起。请考虑清单 6 中的 Groovy 代码:

清单 6. 部分应用复合
def composite = { f, g, x -> return f(g(x)) }
def thirtyTwoer = composite.curry(quadrate, octate)

println "composition of curried functions yields ${thirtyTwoer(2)}"

清单 6 中,我创建了一个由两个函数组成的 composite 代码块。通过使用这个代码块,我创建了一个 thirtyTwoer 代码块,使用部分应用将两种方法组合在一起。

通过使用部分应用和局部套用,您实现了与 Template Method 设计模式等机制类似的效果。例如,您可以在 adder 代码块的上方创建一个 incrementer 代码块,如清单 7 所示:

清单 7. 不同的构建块
def adder = { x, y -> return x + y }
def incrementer = adder.curry(1)

println "increment 7: ${incrementer(7)}"

当然,Scala 支持局部套用,如清单 8 展示的 Scala 文档的部分片段所示:

清单 8. Scala 中的局部套用
object CurryTest extends Application {

  def filter(xs: List[Int], p: Int => Boolean): List[Int] =
    if (xs.isEmpty) xs
    else if (p(xs.head)) xs.head :: filter(xs.tail, p)
    else filter(xs.tail, p)

  def dividesBy(n: Int)(x: Int) = ((x % n) == 0)

  val nums = List(1, 2, 3, 4, 5, 6, 7, 8)
  println(filter(nums, dividesBy(2)))
  println(filter(nums, dividesBy(3)))
}

清单 8 中的代码展示了如何实现 filter() 方法所使用的 dividesBy() 方法。我将一个匿名函数传递给 filter() 方法,使用局部套用将 dividesBy() 方法的第一个参数的值设置为用来创建代码块的值。当我传递代码块(将目标数字作为参数传递)时,Scala 创建了一个新的函数。


通过递归实现过滤

另一个与函数编程关系比较紧密的主题是递归,根据 Wikipedia 的定义,递归是指 “以类己 (self-similar) 的方式重复某个项”。实际上,它是一种计算机科学方法,通过调用来自自身的同一方法在某个操作上进行迭代(确保您具备某个退出条件)。许多情况下,递归可以产生易于理解的代码,因为问题的关键是 “需要不断重复某个操作直到满足某个条件”。

考虑对一个列表进行过滤。通过使用某种迭代方法,我可以确定过滤条件并对内容进行循环,过滤掉我不需要的内容。清单 9 展示了使用 Groovy 实现的简单过滤:

清单 9. 使用 Groovy 实现的过滤
def filter(list, criteria) {
  def new_list = []
  list.each { i -> 
    if (criteria(i))
      new_list << i
  }
  return new_list
}

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

l = filter(1..20, modBy2)
println l

清单 9 中的 filter() 方法接受了一个 list 和一个 criteria(指定如何过滤列表的代码块)并对列表进行遍历,将满足谓语的项添加到一个新列表中。

现在看一下 清单 8,它在 Scala 中以递归方式实现了过滤功能。它采用函数语言中的一种常见模式处理列表。列表的一个特点是它由两部分组成:列表前端(头部)的项和所有其他项。许多函数语言均利用这一特点通过特定的方法实现列表遍历。filter() 方法首先检查列表是否为空,这是该方法的重要退出条件。如果列表为空,则返回。否则,使用谓语条件 (p) 作为参数传递。如果该条件为 true(即我希望该项存在于列表中),则将返回一个新列表,该列表由当前的头部项和列表中过滤后剩下的项组成。如果不能满足谓语条件,则将返回一个新列表,其中只包含过滤剩下的项(去掉了第一个元素)。Scala 中的列表构造操作符使得这两种情况下的返回条件变得非常易读、易于理解。

我猜您现在根本就没有使用递归,它甚至不在您的工具箱中。然而,造成这种现象的部分原因是大多数命令式语言没有提供相应的支持,因此使用递归很困难。通过增加简明的语法和支持,函数式语言使递归成为实现简单代码重用的候选方法。


结束语

在本期文章中,我继续探讨了函数式思维中的一些特性。本文的大部分内容碰巧都与过滤有关,展示了许多与使用和实现过滤有关的方法。但是,这并不是什么值得惊讶的事。许多函数式范例都是围绕列表构建,因为大多数编程的最终目的就是解决列表问题。因此,创建专门针对列表的语言和框架是有一定道理的。

在下一期文章中,我将深入介绍函数编程中的重要概念:不可变性。

参考资料

学习

获得产品和技术

讨论

  • 加入 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=756627
ArticleTitle=函数式思维: 运用函数式思维,第 3 部分
publish-date=09072011