函数式思维: 大量转换

同义词掩盖了相似性

函数式编程方式目前存在于所有主要的语言中,但很难识别,因为标识它们的常用名称有很多种。这一期的函数式思维系列文章将展示使用七种不同的函数式框架和语言编写的一个示例,并对它们的相似性和差异进行了分析。

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

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



2012 年 10 月 29 日

关于本系列

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

函数式编程语言实现代码重用的方法与面向对象的语言不同,这个主题我在 “第 2 部分” 中进行了分析。面向对象的语言往往拥有众多可进行多种操作的数据结构,而函数式语言却只有极少数可进行多种操作的数据结构。面向对象的语言鼓励您创建特定于类的方法,而您可以捕获一些重复出现的模式,以便以后重用。函数式语言鼓励您将常见转换应用于数据结构,使用更高级的函数来定制特定实例的操作,从而帮助您实现重用。

相同的数据结构和操作出现在所有函数式语言中(也出现在支持 Java 中的函数式编程的众多框架中),但它们的名称通常是不同的。容易导致混淆的命名方式使得将一种语言的知识转换成另一种语言的知识变得十分困难,即使基础概念是完全相同的。

本期文章的目标是让这种转换变得简单一些。本文引入了一个简单问题,该问题要求制定一些策略并进行迭代,使用五种语言(Java、Groovy、Clojure、JRuby 和 Scala)和两种 Java 函数式框架(Functional Java 和 Totally Lazy)来实现该解决方案(请参阅 参考资料)。每种语言的实现都是相同的,但相关细节具有很大的出入。

普通 Java

本文涉及的问题是如何确定某个整数是否是质数,质数的因数只能是 1 及其本身。确定质数的算法有好几种(一些替代解决方案可在 “第 1 部分” 中找到);我将使用这样一种解决方案:首先确定数字的因数,然后检查所有因数的和是否等于该数字加1,从而确定该数字是否为质数。这并非最高效的算法,但我的目的是展示常用集合方法的不同实现,而非效率。

清单 1 显示了普通的 Java 版本:

清单 1. 普通的 Java 质数分类器
public class PrimeNumberClassifier {
    private Integer number;

    public PrimeNumberClassifier(int number) {
        this.number = number;
    }

    public boolean isFactor(int potential) {
        return number % potential == 0;
    }

    public Set<Integer> getFactors() {
		Set<Integer> factors = new HashSet<Integer>();
        factors.add(1);
        factors.add(number);
        for (Integer i = 2; i < number; i++)
            if (isFactor(i))
                factors.add(i);
        return factors;
    }

    public int sumFactors() {
        int sum = 0;
        for (int i : getFactors())
            sum += i;
        return sum;
    }

    public boolean isPrime() {
        return sumFactors() == number + 1;
    }
}

如果您阅读过以前的函数式思维 系列文章,就会觉得 清单 1getFactors() 方法中的算法很熟悉,这种算法对候选因数进行了筛选。


Groovy

Groovy 在演变过程中增加了很多函数式构造,它们形成了清单 2 中所示的实现,这里的实现与 Java 中的实现有很大的差别:

清单 2. Groovy 质数分类器
class PrimeNumberClassifier {
  private int number;

  PrimeNumberClassifier(int number) {
    this.number = number
  }

  public def isFactor(int potential) {
    number % potential == 0;
  }

  public def getFactors() {
    (1..number).findAll { isFactor(it) }.toSet()
  }

  public def sumFactors() {
    getFactors().inject(0, {i, j -> i + j})
  }

  public def isPrime() {
    sumFactors() == number + 1
  }
}

清单 1 中具有相应功能的两个方法与 清单 2 中的方法有很大的出入,并不仅仅改变了它们的语法。首先是 getFactors() 方法,它使用 Groovy 的 Range 类来表示候选的数字。findAll() 方法将代码块应用于集合的每个元素,返回一个列表,其中包含代码块为其返回 true 的项。该代码块接受单个参数,即需要检查的元素。我使用便利的 Groovy 简写法让代码块显得更加简洁。例如,可以将代码块写作 (1..number).findAdd {i-> isFactor(i) },但重复单个参数显得很累赘。Groovy 提供了 清单 2 中所示的选项,使用隐式的 it 来替代单独的参数。

清单 2 中其他值得注意的方法还有 sumFactors() 方法。使用 getFactors() 方法生成的数字集合时,我调用了Groovy 集合方法 inject() ,它执行了一次 fold 操作。inject() 方法使用第二个参数中提供的代码块来组合集合中的每个元素,并使用第一个参数作为初始的种子值。清单 2 中的代码块参数是 {i, j-> i + j},它返回两个数字的和。inject() 方法应用这个块,从第一个元素开始,依次到每个元素,计算列表中数字的和。

使用与更高级的函数组合在一起的函数式方法有时可能会导致代码密集。即使 清单 2 中的每个方法都是一行,将它们分解为单独的方法仍然是有好处的。按照功能对方法进行拆分,在当前问题的上下文中为它们各自提供一个有意义的名称,使得理解它们变得更容易。


Scala

清单 3 中给出了质数分类器的 Scala 版本:

清单 3. Scala 质数分类器
object PrimeNumberClassifier {
  def isFactor(number: Int, potentialFactor: Int) =
    number % potentialFactor == 0

  def factors(number: Int) =
    (1 to number) filter (isFactor(number, _))

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

  def isPrime(number: Int) =
    sum(factors(number)) == number + 1
}

除了要短得多之外,Scala 版本还有其他许多不同之处。因为我只需要一个实例,所以我将该实例用作一个 object,而非 classfactors() 方法使用相同的实现作为 清单 2 中的 Groovy 版本,但采用了不同的语法;我将 filter (Groovy 的 findAll() 的 Scala 版本)方法应用于数字范围 (1 to number),使用 清单 3 的开始处定义的 isFactor() 方法作为断言。Scala 允许使用参数占位符,即这个示例中的 —_

清单 3 中的 sum() 方法使用了 Scala 的 foldLeft() 方法,它等同于 Groovy 的 inject()。在本例中,我使用 0 作为种子值,并对两个参数都使用了占位符。


Clojure

Clojure 是一种 JVM 上的 Lisp 的实现,因此您在清单 4 中看到的语法截然不同:

清单 4. Clojure 质数分类器
(ns prime)

(defn factor? [n, potential]
  (zero? (rem n potential)))

(defn factors [n]
  (filter #(factor? n %) (range 1 (+ n 1))))

(defn sum-factors [n]
  (reduce + (factors n)))

(defn prime? [n]
  (= (inc n) (sum-factors n)))

清单 4 中的所有方法对于 Java 开发人员都很陌生,但这段代码实现了我一直使用的算法。(factor?) 方法负责检查余数(Clojure 中的 rem 函数)是否为 0。(factors) 方法使用了 Clojure 的 (filter) 方法,它接受两个参数。第一个参数是在每个元素上执行的断言代码块,返回一个 boolean 值结果,指示是否通过了过滤器的标准。#(factor? n %) 语法表示一个 Clojure 匿名函数,该函数使用了 Clojure 的 % 替代参数。(filter) 函数的第二个参数是要过滤的集合,在本例中是从 1 到我的目标数字加 1 之间的范围;该范围不包含上一个元素。

清单 4 中的 (sum-factors) 方法使用了 Clojure 的 (reduce) 方法,它与 Groovy 的 inject() 和 Scala 的 foldLeft() 方法意义相同。在本例中,操作是一个简单的 + 运算符,对于 Clojure 而言,它与接受两个参数并返回一个结果的其他任何方法并无区别。

如果您对这种语法还不熟悉,它可能会令人感到畏惧,而 Clojure 版本十分简洁。和在 Groovy 版本中一样,好的函数名称非常重要,即使每个函数都只占用了一行,因为行有时候很重要。


JRuby

JRuby 提供了 Ruby 的一种 JVM 实现,它在整个生命周期内也获得了很多函数式构造。请考虑清单 5 中提供的质数分类器的 (J)Ruby 版本:

清单 5. JRuby 质数分类器
class PrimeNumberClassifier
  def initialize(num)
    @num = num
  end

  def factor?(potential)
    @num % potential == 0
  end

  def factors
    (1..@num).select { |i| factor?(i) }
  end
    
  def sum_factors
    factors.reduce(0, :+)
  end

  def prime?
    (sum_factors == @num + 1)
  end
end

清单 5 中的 factors 方法为 Groovy 的 findAll 方法以及 Scala 和 Clojure 的 filter 方法添加了 select 同义词。JRuby 的优秀特性之一是为方法起别名很容易,为在不同上下文中使用方法提供了更方便的名称。当然,JRuby 包含了 select 方法的一个别名,叫做 find_all,但这不是常见的习惯用法。

对于 清单 5 中的 sum_factors 方法,我使用了 JRuby 的 reduce 方法,模仿了其他几种语言。在 JRuby 中,和在 Clojure 中一样,运算符就是具有有趣名称的方法;Ruby 允许我按照符号指定加法方法的名称,:+。作为可读性方面的一种辅助手段,Clojure 与 Ruby 都允许我给期望返回布尔值的函数添加问号。而且与其本质一致,Ruby 包含 reduce 的一个 inject 方法别名。


函数式 Java

为了不忽略仍然使用 Java 变体的用户,一些函数式编程库为 Java 添加了函数式构造。函数式 Java 正是这样一种框架;清单 6 中给出了使用 Java 和函数式 Java 的质数分类器:

清单 6. 函数式 Java 质数分类器
public class FjPrimeNumberClassifier {
    private int number;

    public FjPrimeNumberClassifier(int number) {
        this.number = number;
    }

    public boolean isFactor(int potential) {
        return number % potential == 0;
    }

    public List<Integer> getFactors() {
        return range(1, number + 1)
                .filter(new F<Integer, Boolean>() {
                    public Boolean f(final Integer i) {
                        return isFactor(i);
                    }
                });
    }

    public int sumFactors() {
        return getFactors().foldLeft(fj.function.Integers.add, 0);
    }

    public boolean isPrime() {
        return sumFactors() == number + 1;
    }
}

清单 6 中的 getFactors() 方法在 range 上使用了 filter() 方法(和在 Clojure 中一样,该范围是专用的,它是范围定义中的number + 1)。因为 Java 没有更高级的函数,所以函数式 Java 使用其内置 F 类的匿名内部类实例,使用泛型参数化了类型,从而回避了这个问题。

和 Scala 一样,函数式 Java 包含一个 foldLeft() 方法,在本例中,该方法接受一个预定义的代码块,对数字和种子值求和。


Totally Lazy

Totally Lazy 是一个针对 Java 的函数式库,为 Java 添加了大量惰性 集合。惰性数据结构没有预先定义元素,而是对请求时如何生成下一个值的规则进行编码。清单 7 中给出了使用 Totally Lazy 实现的质数分类器:

清单 7. Totally Lazy 质数分类器
public class TlPrimeNumberClassifier {
    private int number;

    public TlPrimeNumberClassifier(int number) {
        this.number = number;
    }

    public boolean isFactor(Integer potential) {
        return (number % potential) == 0;
    }

    private List<Integer> listOfPotentialFactors() {
        List<Integer> results = new ArrayList<Integer>();
        for (int i = 1; i <= number + 1; i++)
            results.add(i);
        return results;
    }

    public boolean isPrime() {
        return (this.number + 1) ==
            Sequences.init(listOfPotentialFactors())
                     .filter(new Predicate<Integer>() {
                         @Override
                         public boolean matches(Integer other) {
                             return isFactor(other);
                      }})
                     .foldLeft(0, sum())
                     .intValue();
    }
}

清单 7 中的 isPrime() 方法使用了 Sequences 类,使用所有可能因数(即从 1 到目标数字的所有数字)的一个列表进行初始化,然后应用了它的 filter() 方法。在 Totally Lazy 中,filter() 方法期望获得 Predicate 类的一个子类,其中很多已经针对常见情况进行了实现。在我的示例中,我重写了 matches() 方法,提供我的 isFactor() 方法来确定包含内容。有了因素列表之后,我使用了 foldLeft 方法,并使用所提供的 sum() 方法进行求和操作。

清单 7 所示的示例中,isPrime() 方法完成了绝大部分的工作。Totally Lazy 中的所有数据结构都是惰性结构,当您组合它们时,就会带来麻烦。请考虑清单 8 中所示的 getFactors() 方法版本:

清单 8. 使用了惰性迭代器的 Totally Lazy 的 getFactors 方法
public Iterator<Integer> getFactors() {
    return Sequences
            .init(listOfPotentialFactors())
            .filter(new Predicate<Integer>() {
                @Override
                public boolean matches(Integer other) {
                    return isFactor(other);
                }
            })
            .iterator();
}

清单 8getFactors() 方法的返回值是 Iterator<Integer> ,但它是一个惰性迭代器,这表示只有在您进行迭代之后,它才有值。这使得测试惰性集合成为一个难题。请考虑对 清单 8 中的 Totally Lazy 示例进行单元测试,如清单 9 中所示:

清单 9. 测试 Totally Lazy 集合
@Test
public void factors() {
    TlPrimeNumberClassifier pnc = new TlPrimeNumberClassifier(6);
    List<Integer> expected = new ArrayList<Integer>() {{
        add(1);
        add(2);
        add(3);
        add(6);
    }};
    Iterator<Integer> actual = pnc.getFactors();
    assertTrue(actual.hasNext());
    int count = 0;
    for (int i = 0; actual.hasNext(); i++) {
        assertEquals(expected.get(i), actual.next());
        count++;
    }
    assertTrue(count == expected.size());
}

对于惰性集合,我必须遍历集合来检索值,才能确保惰性列表中的元素数量不会超过预期。

可以使用 Totally Lazy 编写一个与其他版本同样分解良好的版本,但您可能会受困于不断变得更加错综复杂的数据结构,比如 <Iterator<Iterator<Number>>>


结束语

在这一期的文章中,我阐明了各种函数式语言和框架中相同行为的名称的演变过程。所有这些语言和框架中的方法名称绝不可能达成一致,但 Java 运行时增加了很多构造,如闭包,互操作将会变得更加简单,因为它们能够共享通用的标准表示(而不需要一些尴尬的构造,比如 Totally Lazy 中 <Iterator<Iterator<Number>>>)。

在下一期的文章中,我将通过分析 map 继续说明转换中的相似性。

参考资料

学习

  • The Productive Programmer(Neal Ford,O'Reilly Media,2008):Neal Ford 撰写的一本书籍,讨论了能够帮助您提高编码效率的工具和实践。
  • Scala:Scala 是运行在 JVM 上的一种现代函数式语言。
  • Clojure:Clojure 是运行在 JVM 上的一种现代函数式 Lisp。
  • Totally Lazy:Totally Lazy 是一种为 Java 添加了各种惰性集合的框架。
  • JRuby:JRuby 是一种运行在 JVM 上的 Ruby 实现,提供了大量函数式构造。
  • Groovy:Groovy 是一种动态的类似 Java 的语言,包含对 Java 语法的大量函数式扩展。
  • Functional Java:Functional Java 是一种给 Java 添加了大量函数式语言构造的框架。
  • 浏览 技术书店,阅读关于这些和其他技术主题的书籍。
  • developerWorks 中国网站 Java 技术专区:您可以找到关于 Java 编程的所有方面的数以百计的文章。

讨论

  • 加入 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=843487
ArticleTitle=函数式思维: 大量转换
publish-date=10292012