函数式思维: 惰性计算,第 2 部分

深入探讨惰性评估

惰性评估在支持闭包的语言中很容易实现。本期 函数式思维 文章将展示您如何使用 Groovy 的闭包作为构建块来生成一个惰性列表。然后,本文将探讨惰性评估在性能和概念上的一些优势,包括以惰性方式在某些语言中初始化字段的能力。

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

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



2013 年 1 月 17 日

关于本系列

本系列旨在将您看问题的角度调整为函数式思维,帮助您以新的方式看待常见问题,并找出改进日常编码的方法。本文探讨了函数式编程的一些概念、在 Java 语言中实现函数式编程的框架、在 JVM 上运行的函数式编程语言,以及未来语言设计的一些倾向。本系列文章面向那些了解 Java 及其工作原理,但极少或没有使用函数式语言的有经验开发人员。

在 "惰性计算,第 1 部分" 中,我探讨了 Java™ 中的惰性库。在本期文章中,我将演示如何使用闭包作为构建块来实现一个简单的惰性列表,探讨惰性评估的一些性能优势,以及 Groovy、Scala 和 Clojure 的一些惰性内容。

构建惰性列表

在本系列 前一期文章 中,我演示了 Groovy 中一个惰性列表的简单实现。但我并没有探讨其工作原理,然而这是本期的主题。

正如从 上一期文章 中所了解到的,可以将语言分为严格的(急切地评估所有表达式)或惰性的(将评估推迟至绝对需要时)。Groovy 从性质上讲是一种严格的语言,但我可以将一个非惰性列表转换成一个惰性列表,方法是在一个闭包中递归严格的列表。这使得我可以通过延迟闭包块的执行而推迟后续值的评估。

在 Groovy 中,严格的空列表是用数组表示的,并使用空的方括号:[]。如果我将空列表存到一个闭包中,它就成为一个惰性的空列表:

{-> [] }

如果我需要将一个 a 元素添加到列表中,那么我可以将它添加到前面,然后再次产生全新的惰性列表:

{-> [ a, {-> [] } ] }

添加到列表前的方法传统上称为 prependcons。为了添加更多元素,我将对每一个新项重复此操作;添加三个元素(abc)到列表中,这可以生成:

{-> [a, {-> [b, {-> [ c, {-> [] } ] } ] } ] }

这个语法有些笨拙,不过,一旦我明白了其中的道理,就可以在 Groovy 中创建一个为创建惰性集合而实现的一组传统方法的类,如清单 1 所示:

清单 1. 在 Groovy 中使用闭包构建惰性列表
class PLazyList {
  private Closure list

  private PLazyList(list) {
    this.list = list
  }

  static PLazyList nil() {
    new PLazyList({-> []})
  }

  PLazyList cons(head) {
    new PLazyList({-> [head, list]})
  }

  def head() {
    def lst = list.call()
    lst ? lst[0] : null
  }

  def tail() {
    def lst = list.call()
    lst ? new PLazyList(lst.tail()[0]) : nil()
  }

  boolean isEmpty() {
    list.call() == []
  }

  def fold(n, acc, f) {
    n == 0 || isEmpty() ? acc : tail().fold(n - 1, f.call(acc, head()), f)
  }

  def foldAll(acc, f) {
    isEmpty() ? acc : tail().foldAll(f.call(acc, head()), f)
  }

  def take(n) {
    fold(n, []) {acc, item -> acc << item}
  }

  def takeAll() {
    foldAll([]) {acc, item -> acc << item}
  }

  def toList() {
    takeAll()
  }
}

清单 1 中,构造函数是私有的,从一个空表开始,使用 nil() 调用它,该方法构造了一个空列表。cons() 方法让我能够在前面加上传递参数,然后将结果包装在一个闭包块中,从而添加新元素。

接下来的三个方法支持列表的遍历。head() 方法返回列表中的第一个元素,tail() 返回子列表中除了第一个元素以外的所有元素。在两种情况下,我都 call() 闭包块,这在惰性术语中称为执行 (forcing) 评估。因为我在检索值,所以在我获得值的时候,它不再是惰性的。并不奇怪的是,isEmpty() 方法会检查是否还有任何术语要进行解析。

其余的方法是在列表上执行操作的高阶功能。fold()foldAll() 方法执行折叠 抽象,这也称为减少,或者仅在 Groovy 中称为 injectAll()。在以前的许多文章(如 "运用函数式思维,第 3 部分")中,我已经演示过该系列的方法的使用,但这是我第一次演示纯粹以闭包块编写的递归定义。foldAll() 方法检查该列表是否为空,如果是,则返回 acc(累加器,折叠操作的种子值)。否则,它在列表的 tail() 上递归调用 foldAll(),传递累加器和列表的头。函数(f 参数)应接受两个参数并生成单一结果;这就是 “折叠” 操作,因为您将一个元素折叠到相邻的另一个元素之上。

构建一个列表并操作它,如清单 2 所示:

清单 2. 执行惰性列表
def lazylist = PLazyList.nil().cons(4).cons(3).cons(2).cons(1)
println(lazylist.takeAll()) //[1, 2, 3, 4]
println(lazylist.foldAll(0, {i, j -> i + j})) // 10
lazylist = PLazyList.nil().cons(1).cons(2).cons(4).cons(8)
println(lazylist.take(2))  //[8, 4]

清单 2 中,我通过将一些值 cons() 到一个空列表上来创建列表。请注意,当我 takeAll() 元素时,返回它们的顺序与它们添加到列表的顺序是相反的。请记住,cons() 其实是在前面加上 的简写;它将元素添加到列表的前面。foldAll() 方法让我可以通过提供转换代码块 {i, j -> i + j} 来汇总列表,该代码块使用添加作为折叠操作。最后,我使用 take() 方法来执行前两个元素的评估。

实际的惰性列表实现与此不同,避免了递归并增加更灵活的操作方法。不过,从概念上了解在实现内部发生了什么事情助于理解和使用惰性列表。


惰性的好处

惰性列表有几个好处。首先,您可以用它们来创建无限序列。因为直到需要时才计算值,您可以使用惰性集合模拟无限列表。我在 "Groovy 中的函数式特性,第 1 部分" 中演示了一个在 Groovy 中实现此功能的示例。第二个好处是减少了存储空间。如果(不是保存整个集合)我可以得到后续的值,那么我就可以用存储来换取执行速度。选择使用惰性集合,这成为存储值与计算新值的代价之间的一个权衡。

第三,惰性集合的主要好处之一是,运行时可以生成更高效的代码。考虑清单 3 中的代码:

清单 3. 在 Groovy 中查找回文
def isPalindrome(s) {
  def sl = s.toLowerCase()
  sl == sl.reverse()
}

def findFirstPalindrome(s) {
  s.tokenize(' ').find {isPalindrome(it)}
}

s1 = "The quick brown fox jumped over anna the dog";
println(findFirstPalindrome(s1)) // anna

s2 = "Bob went to Harrah and gambled with Otto and Steve"
println(findFirstPalindrome(s2)) // Bob

清单 3 中的 isPalindrome() 方法标准化了主题词的大小写,然后确定该单词在反方向是否具有相同的字符。findFirstPalindrome() 方法尝试通过使用 Groovy 的 find() 方法找到所传递字符串中的第一个回文,该方法接受使用代码块作为过滤机制。

假设我有一个巨大的字符序列,我需要找到里面的第一个回文。在 findFirstPalindrome() 方法的执行过程中,清单3 中的代码首先急切地标记化整个序列,创建一个中间数据结构,然后发出 find() 命令。Groovy 的 tokenize() 方法是不是惰性的,所以在本例中,它可能会建立一个巨大的临时数据结构,只为了丢弃其中的大部分数据。

考虑使用 Clojure 编写的相同代码,如清单 4 所示:

清单 4. Clojure 的回文
(defn palindrome? [s]
  (let [sl (.toLowerCase s)]
  (= sl (apply str (reverse sl)))))

(defn find-palindromes [s]
  (filter #(palindrome? %) (clojure.string/split s #" ")))

(println (find-palindromes "The brown fox jumped over anna."))
; (anna)
(println (find-palindromes "Bob went to Harrah and gambled with Otto"))
; (Bob Harrah Otto)
(println (take 1 (find-palindromes "Bob went to Harrah and gambled with Otto")))
; (Bob)

清单 3清单 4 中的实现细节是相同的,但使用了不同的语言构造。在 Clojure 的 palindrome? 函数中,我让参数字符串变成小写,然后检查是否与反转字符串相同。额外地调用 apply,将 reverse 返回的字符序列转换成为字符串,以便进行比较。find-palindromes 函数使用了 Clojure 的 filter 函数,它接受使用一个函数作为过滤器以及将被过滤的集合。#(palindrome? %) 的调用是一个匿名函数的简写,它接受单个参数,完整版本如下所示:

(fn [x]
  (palindrome? x))

如果我只有一个参数,那么 Clojure 允许我避免声明匿名函数并命名该参数,我会用 #(palindrome? %) 函数调用中的 % 替代它。

从 Groovy 到 Clojure 的转换需要的不仅仅是语法。Clojure 中可以 具有惰性的所有数据结构都 惰性的,包括 filtersplit 等在集合上的操作。因此,在 Clojure 的版本中,一切都是自动惰性的,这体现在 清单 4 的第二个示例中,当我在有多个参数的集合上调用 find-palindromes 时。filter 返回的是一个惰性集合,在我打印它时执行。如果只想要第一个条目,则必须从列表中 take 我所需的惰性条目数量。

Scala 以稍有不同的方式实现了惰性。它没有在默认情况下让一切成为惰性的,而是提供了集合上的惰性视图。请考虑清单 5 中回文问题的 Scala 实现:

清单 5. Scala 回文
def isPalindrome(x: String) = x == x.reverse
def findPalidrome(s: Seq[String]) = s find isPalindrome

findPalindrome(words take 1000000)

清单 5 中,通过 take 方法从集合中取出 1 百万个单词,这样做非常低效,尤其在目标只是找到第一个回文时。要将 words 集合转换为一个惰性集合,可以使用 view 方法:

findPalindrome(words.view take 1000000)

view 方法允许执行集合的惰性遍历,并支持更高效的代码。


惰性字段初始化

在结束惰性主题之前,我想要提及的是,这两种语言都有一个很好的工具来支持昂贵的初始化惰性。通过将 lazy 添加到 val 声明的前面,可以将 Scala 中的字段从急切转换为按需评估:

lazy val x = timeConsumingAndOrSizableComputation()

这对于清单 6 中的代码基本上是语法糖 (syntactic sugar):

清单 6. Scala 为惰性字段生成的语法糖
var _x = None
def x = if (_x.isDefined) _x.get else {
  _x = Some(timeConsumingAndOrSizableComputation())
  _x.get
}

Groovy 也有一个类似的工具,它使用了一个称为 Abstract Syntax Tree (AST) Transformations 的高级语言特性。这些特性使您能够与编译器生成的底层抽象语法树进行交互,允许进行低层次的用户转换。其中一个预定义的转换是 @Lazy 属性,如清单 7 中的行动所示:

清单 7. Groovy 中的惰性字段
class Person {
    @Lazy pets = ['Cat', 'Dog', 'Bird']
}

def p = new Person()
assert !(p.dump().contains('Cat'))

assert p.pets.size() == 3
assert p.dump().contains('Cat')

清单 7 中,在第一次访问数据结构之前,Person 实例 p 不会显示有一个 Cat 值。Groovy 还允许您使用一个闭包块来初始化数据结构:

class Person {
    @Lazy List pets = { /* complex computation here */ }()
}

最后,您也可以告诉 Groovy 使用软引用(Java 的可以回收的指针引用版本,如果需要的话)来保存以惰性方式初始化的字段:

class Person {
    @Lazy(soft = true) List pets = ['Cat', 'Dog', 'Bird']
}

结束语

在本期文章中,我更深入地探讨了惰性,使用 Groovy 中的闭包从头开始建立一个惰性集合。我还讨论了为什么您可能会考虑使用一个惰性结构,并列出了一些好处。尤其是,运行时可以优化资源的能力就是一个巨大的胜利。最后,我演示了在 Scala 和 Groovy 中的一些深奥但很有用的惰性表现形式,它们与采用惰性方式初始化的字段有关。

参考资料

学习

  • Lazy lists in Groovy:感谢 Andrey Paramonov 的博客提供他对于使用闭包构建惰性列表的观点。
  • Scala:Scala 是在 JVM 上的一个现代化函数语言。
  • Clojure:Clojure 是在 JVM 上运行的一个现代化函数式 Lisp。
  • Totally Lazy:Totally Lazy 框架使用了类似于 DSL 的直观界面,将大量函数式扩展添加到 Java。
  • Functional Java:Functional Java 是一个框架,将许多函数式语言结构添加到 Java。
  • 面向 Java 开发人员的 Scala 指南:在这个 developerWorks 系列中,了解关于 Scala 的更多信息。
  • 浏览 技术书店,阅读关于这些主题和其他技术主题的书籍。
  • 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=854841
ArticleTitle=函数式思维: 惰性计算,第 2 部分
publish-date=01172013