Groovy 学习（2）：函数式编程

Groovy 一般不被看作一种函数式语言，但它具备很多函数式的范式，只是命名上往往带有脚本语言的色彩。

编程范式：

• 命令式编程：是按照“程序是一系列改变状态的命令”来建模的一种编程风格。传统的 for 循环是命令式风格的绝好例子：先确立初始状态，然后每次迭代都执行循环体中的一系列命令。

• 函数式编程：将程序描述为表达式和变换，以数学方程的形式建立模型，并且尽量避免可变的状态。

几个函数的概念：

• 纯函数：pure function ，没有副作用的函数。^[1]
• 一等函数：first-class function，当一门编程语言的函数可以被当作变量一样用时，则称这门语言拥有头等函数。例如，在这门语言中，函数可以被当作参数传递给其他函数，可以作为另一个函数的返回值，还可以被赋值给一个变量。^[2]
• 高阶函数：higher-order function ，又称算子 (运算符) 或泛函，包含多于一个箭头的函数。在无类型 lambda 演算中，所有函数都是高阶的；在有类型 lambda 演算（大多数函数式编程语言都从中演化而来）中，高阶函数一般是那些函数型别包含多于一个箭头的函数。在函数式编程中，返回另一个函数的高阶函数被称为柯里化的函数。^[3]

简单示例

下面是一个 Groovy 函数式编程的示例，写法和 Java 8 的 Stream API 类似，只是方法名有些区别。

static String cleanupNames(listOfNames) {
    listOfNames
            .findAll { it.length() > 1 }
            .collect { it.capitalize() }
            .join ','
}

@Test
void test_cleanup_names() {
    def employees = ['neal', 's', 'stu', 'j', 'rich']
    Assertions.assertEquals 'Neal,Stu,Rich', cleanupNames(employees)
}

上述示例对应的 Java 代码如下：

public static String cleanupNames(List<String> listOfNames) {
    return listOfNames
            .stream()
            .filter(name -> name.length() > 1)
            .map(name -> capitalize(name))
            .collect(Collectors.joining(","));
}

public static String capitalize(String e) {
    return e.substring(0, 1).toUpperCase() + e.substring(1);
}

@Test
public void test_cleanup_names() {
    List<String> employees = Arrays.asList("neal", "s", "stu", "j", "rich");
    Assertions.assertEquals("Neal,Stu,Rich", cleanupNames(employees));
}

可以看到方法的对应关系大致如下：

Groovy	Java
findAll	filter
collect	map
join	collect & Collectors.joining

向函数式思维靠拢，意味着我们逐渐学会何时何地应该求助于这些更高层次的抽象，不要再一头扎进实现细节里去。

学会用更高层次的抽象来思考的好处：

1. 会促使我们换一种角度去归类问题，看到问题的共性；
2. 让运行时有更大的余地去做智能的优化。有时候，在不改变最终输出的前提下，调整一下作业的先后次序会更有效率；
3. 让埋头于实现细节的开发者看到原本视野之外的一些解决方案。

例如将上面的例子改为多线程，只需要添加一个 .parallelStream() 步骤就可以了。

static String cleanupNamesP(listOfNames) {
    listOfNames
            .parallelStream()
            .findAll { it.length() > 1 }
            .collect { it.capitalize() }
            .join ','
}

@Test
void test_cleanup_names_p() {
    def employees = ['neal', 's', 'stu', 'j', 'rich']
    println cleanupNamesP(employees)
}

我们在更高的抽象层次上做事情，运行时才好去优化低层次的细节。

基本构造单元

• 筛选 filter
  • 根据用户定义的条件来筛选列表中的条目。
• 映射 map
  • 对原集合的每一个元素执行给定的函数，从而变换成一个新的集合。
• 折叠 / 化约 | fold / reduce
  • fold 和 reduce 操作在功能上大致重合，但根据具体的编程语言而有微妙的区别。
  • 两者都用一个累积量来“收集”集合元素。
  • reduce 函数一般在需要为累积量设定一个初始值的时候使用，而 fold 起始的时候累积量是空的。
  • 函数在操作集合的时候可以有不同的次序（如 foldLeft 和 foldRight）。
  • 不会改变原集合。

筛选 filter

筛选函数将用户（通常以高阶函数的形式）给定的布尔逻辑作用于集合，返回由原集合中符合条件的元素组成的一个子集。筛选操作与查找（find）函数的关系很密切，查找函数返回的是集合中第一个符合条件的元素。

@Test
void test_filter() {
    // findAll() 相当于传统函数式语言的 filter() 函数
    assertEquals([3, 6, 9], (1..10).findAll { it % 3 == 0 })
    // findAll() 适用于所有类型，包括字符串
    def words = ['the', 'quick', 'brown', 'fox', 'jumped', 'over', 'the', 'lazy', 'dog']
    assertEquals(['the', 'fox', 'the', 'dog'], words.findAll { it.length() == 3 })
    // 返回一个嵌套的数组 [匹配的元素列表, 其他的元素列表]
    assertEquals([[3, 6, 9], [1, 2, 4, 5, 7, 8, 10]], (1..10).split { it % 3 == 0 })
    // find() 方法返回第一个匹配项
    assertEquals(3, (1..10).find { it % 3 == 0 })
    // find() 方法找不到匹配项时返回 null
    assertNull((1..10).find { it < 0 })
    // takeWhile() 返回满足断言的最长前缀
    assertEquals([1, 2, 3], [1, 2, 3, -4, 5, 6, 7, 8, 9, 10].takeWhile { it > 0 })
    // dropWhile() 丢弃满足断言的最长前缀
    def moreWords = ['the', 'two', 'ton'] + words
    assertEquals(['quick', 'brown', 'fox', 'jumped', 'over', 'the', 'lazy', 'dog'],
            moreWords.dropWhile { it.startsWith('t') })
}

映射 map

传给映射函数的是一个高阶函数和一个集合，它在集合中的每一个元素施用传入的函数之后，产生另一个集合作为返回值。返回的集合大小与原来的集合相同，只是元素的取值变了。

@Test
void test_map() {
    // Groovy 使用 it 作为参数占位标记
    assertEquals(2..6, (1..5).collect { it + 1 })
    // collect() 方法可以用于任意的集合上
    def words = ['the', 'quick', 'brown', 'fox', 'jumped', 'over', 'the', 'lazy', 'dog']
    assertEquals([3, 5, 5, 3, 6, 4, 3, 4, 3], words.collect { it.length() })
    // flatten() 方法消除嵌套结构
    assertEquals(1..9, [[1, 2, 3], [4, 5, 6], [7, 8, 9]].flatten())
    // flatten() 方法同样适用于一些非典型的集合
    (words.collect { it.toList() }).flatten()
    // ['t','h','e','q','u','i','c','k',...]
}

折叠 / 化约 | fold / reduce

Groovy 提供了两个版本的 inject() 方法，分别对应 reduce() 和 foldLeft() 。

@Test
void test_reduce() {
    assertEquals 55, (1..10).inject { a, b -> a + b }
    // 有初始值的版本
    assertEquals 55, (1..10).inject(0, { a, b -> a + b })
}

闭包 closure

闭包（ closure ）是所有函数式语言都具备的一项平常特性。所谓闭包，实际上是一种特殊的函数，它在暗地里绑定了函数内部引用的所有变量。换句话说，这种函数（或方法）把它引用的所有东西都放在一个上下文里“包”了起来。

class Employee {
    def name, salary
}

def paidMore(amount) {
    { Employee e -> e.salary > amount }
}

@Test
void test_closure() {
    def Fred = new Employee(name: 'Fred', salary: 12_0000)
    def Homer = new Employee(name: 'Homer', salary: 8_0000)

    def isHighPaid = paidMore(10_0000)
    assertTrue isHighPaid(Fred)
    assertFalse isHighPaid(Homer)

    def isHigherPaid = paidMore(20_0000)
    assertFalse isHigherPaid(Fred)
    assertFalse isHigherPaid(Homer)
}

闭包在生成的时候，会把引用的变量全部圈到代码块的作用域里，封闭、包围起来（故名闭包）。闭包的每个实例都保有自己的一份变量取值，包括私有变量也是如此。

柯里化和函数的部分施用

柯里化（ currying ）和函数的部分施用（ partial application ）都是从数学里借用过来的编程语言技法。

柯里化指的是从一个多参数函数变成一连串单参数函数的变换。它描述的是变换的过程，不涉及变换之后对函数的调用。调用者可以决定对多少个参数实施变换，余下的部分将衍生出一个参数数目较少的新函数。

部分施用指通过提前带入一部分参数值，是一个多参数函数得以省略部分参数，从而转化为一个参数数目较少的函数。

Groovy 通过 curry() 函数实现柯里化，这个函数来自 Closure 类。curry() 虽然叫做这个名字，它在背后对代码块所作的事情其实属于函数的部分施用。尽管名不副实，但用它来模拟柯里化的效果还是可行的，做法是通过连续的部分施用函数变形为一连串单参数的函数。

@Test
void test_currying_vs_pa() {
    // 原函数
    def volume = { h, w, l -> h * w * l }
    // 柯里化
    def area = volume.curry(1)
    // 部分施用
    def lengthPA = volume.curry(1, 1)
    // 柯里化
    def lengthC = volume.curry(1).curry(1)

    println "参数取值为2x3x4的长方体，体积为${volume(2, 3, 4)}"
    println "参数取值为3x4的长方形，面积为${area(3, 4)}"
    println "参数取值为6的线段，长度为${lengthPA(6)}"
    println "参数取值为6的线段，经柯里化函数求得的长度为${lengthC(6)}"
}

递归

递归：以一种自相似的方式来重复事务的过程。

递归式的遍历：

def recurseList(listOfNums) {
    if (listOfNums.size() == 0) return
    println "${listOfNums.head()}"
    recurseList(listOfNums.tail())
}

@Test
void test_recurse() {
    println("递归式的列表遍历")
    recurseList(1..5)
}

递归操作往往受制平台而存在一些固有的技术限制。但对于长度不大的列表来说，递归操作是安全的。

尾调用优化：递归没有成为一种平常的操作，其中一个主要原因是栈的增长。开发者可以使用尾调用优化的写法来帮助运行时克服栈的增长问题。当递归调用是函数的最后一个调用的时候，运行时往往可以在栈里就地更新，而不需要增加新的栈空间。

记忆 memoization

memoization 这个词是英国的人工智能研究者 Donald Michie 生造出来的，指的是在函数级别上对需要多次使用的值进行缓存的机制。目前来说，函数式编程语言普遍都支持记忆特性，有些是直接内建在语言内的，也有一些需要开发者自行实现，但实现起来相对容易。

只有纯函数才适用缓存技术。

Groovy 语言记忆一个函数的方法是，先将要记忆的函数定义成闭包，然后对该闭包执行 memoize() 方法来获得一个新函数，以后我们调用这个新函数的时候，其结果就会被缓存起来。

“记忆一个函数”这件事情，运用了所谓“元函数”技法：我们操纵的对象是函数本身，而非函数的结果。Groovy 把记忆特性内建在它的 Closure 类里。

以 Classifier 类的 sumFactors 方法为例：

def static sumFactors(number) {
    factorsOf(number).inject(0, { i, j -> i + j })
}

在 IDEA 中，只需要选中方法名，然后 Alt + Enter => 转换为闭包属性，即可自动变成如下形式：

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

在闭包后面添加 memoize() 调用：

def static sumFactors = { number ->
    factorsOf(number).inject(0, { i, j -> i + j })
}.memoize()

这样就生成了一个带“记忆”能力的方法。

完整示例如下：

class ClassifierMemoizedSum {

    def static isFactor(number, potential) {
        number % potential == 0
    }

    def static factorsOf(number) {
        (1..number).findAll { i -> isFactor(number, i) }
    }

//    def static sumFactors(number) {
//        println "sumFactors of $number"
//        factorsOf(number).inject(0, { i, j -> i + j })
//    }

    // 将 sumFactors() 方法转换为闭包并对这个闭包执行 memoize() 方法
    def static sumFactors = { number ->
        println "sumFactors of $number"
        factorsOf(number).inject(0, { i, j -> i + j })
    }.memoize()

    def static isPerfect(number) {
        sumFactors(number) == 2 * number
    }

    def static isAbundant(number) {
        sumFactors(number) > 2 * number
    }

    static def isDeficient(number) {
        sumFactors(number) < 2 * number
    }
}

在 sumFactors() 方法中添加了 println 调用以验证实际被调用了几次。

@Test
void test_memoize() {
    assertTrue ClassifierMemoizedSum.isPerfect(6)
    assertFalse ClassifierMemoizedSum.isAbundant(6)
    assertFalse ClassifierMemoizedSum.isDeficient(6)
    // 仅会打印一次消息
}

类似的也可以给 factorsOf() 和 isFactor() 方法添加记忆特性。但是也要注意下方法可能被记忆的数量，如果需要记忆的结果过多反而会使运行速度变慢，甚至导致内存不足。这种情况可以使用 memoizeAtMost() 方法替换 memoize() 。

def static isFactor = { number, potential ->
    number % potential == 0
}.memoizeAtMost(1000)

这表示缓存的上限为 1000。

除此之外还有两个类似的方法：

• memoizeAtLeast : 规定了缓存数量的下限
• memoizeBetween : 规定了缓存数量的上限和下限

语言设计者实现出来的机制总是比开发者自己做的效率更高，因为他们可以不受语言本身的限制。

请保证所有被记忆的函数：

• 没有副作用
• 不依赖任何外部信息

缓求值 lazy evaluation

缓求值（ lazy evaluation ）是函数式编程语言常见的一种特性，指尽可能地推迟求解表达式。缓求值的集合不会预先算好所有的元素，而是在用到的时候才落实下来。这样可以带来以下好处：

1. 昂贵的运算只有到了绝对必要的时候才执行；
2. 我们可以建立无限大的集合，只要一接到请求，就一直送出元素；
3. 按缓求值的方式来使用映射、筛选等函数式概念，可以产生更高效的代码。

看一下下面打印列表长度的伪代码：

print length([2 + 1, 3 * 4, 1 / 0, 5 - 4])

在严格求值（ strict ）的语言里，编译会发生“被零除”的异常；在非严格求值（ non-strict ）的语言里，它会打印 4。

缓求值列表

这个是 Groovy 实现的一个缓求值列表类 LazyList ，通过它可以创建无限大的集合。

class LazyList {

    private head, tail

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

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

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

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

创建缓求值列表的示例：

def prepend(val, closure) {
    new LazyList(val, closure)
}

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

@Test
void lazy_list_acts_like_a_list() {
    def naturalNumbers = integers(1)
    assertEquals(1..10, naturalNumbers.getHead(10))
    def evenNumbers = naturalNumbers.filter { it % 2 == 0 }
    assertEquals((2..20).by(2), evenNumbers.getHead(10))
}

这个类理解起来有些绕。简单来说，就是将列表分为头部的元素和之后的元素，后者在代码中表现为一个生成下一个元素的闭包。

函数式语言中的设计模式

传统设计模式在函数式编程的世界中大致有三种归宿：

• 模式已经被吸收成为语言的一部分。
• 模式中描述的解决方法在函数式范式下依然成立，但实现细节有所变化。
• 由于在新的语言或范式下获得了原本没有的能力，产生新的解决方案（例如很多问题都可以用元编程干净利落的解决，但 Java 没有元编程的能力）。

从根本上说，设计模式的存在意义就是弥补语言功能上的弱点。

Template Method 模式

可以将模板方法中的步骤用类的属性来代替。

传统实现：

abstract class Customer {
    def plan
    
    def Customer() {
        plan = []
    }

    def abstract checkCredit()
    def abstract checkInventory()
    def abstract ship()
    
    def process() {
        checkCredit()
        checkInventory()
        ship()
    }
}

使用一等函数的实现：

class CustomerBlocks {
    def plan, checkCredit, checkInventory, ship

    def CustomerBlocks() {
        plan = []
    }

    def process() {
        checkCredit()
        checkInventory()
        ship()
    }
}

Strategy 模式

传统实现：

interface Calc {
    def product(n, m)
}

class CalcMult implements Calc {
    @Override
    def product(n, m) { n * m }
}

class CalcAdds implements Calc {
    @Override
    def product(n, m) {
        def result = 0
        n.times {
            result += m
        }
        result
    }
}

@Test
void product_verifier() {
    def listOfStrategies = [new CalcMult(), new CalcAdds()]
    listOfStrategies.each { s -> assertEquals(10, s.product(5, 2)) }
}

使用 Groovy 代码块作为一等函数的能力，可以将策略模式做的更好。

@Test
void exp_verifier() {
    def listOfExp = [
            { i, j -> Math.pow(i, j) },
            { i, j ->
                def result = i
                (j - 1).times { result *= i }
                result
            }
    ]
    listOfExp.each { e ->
        assertEquals(32, e(2, 5))
        assertEquals(100, e(10, 2))
        assertEquals(1000, e(10, 3))
    }
}

Flyweight 模式和记忆

假设有几个 Computer 类：

class Computer {
    def type, cup, memory, hardDrive, cd
}

class Desktop extends Computer {
    def driveBays, fanWattage, videoCard
}

class Laptop extends Computer {
    def usbPorts, dockingBay
}

class AssignedComputer {
    def computerType, userId

    AssignedComputer(computerType, userId) {
        this.computerType = computerType
        this.userId = userId
    }
}

传统方法的 Flyweight 模式实现：

这里使用 Groovy 的 @Singleton 注解简化工厂类的实现。

@Singleton(strict = false)
class ComputerFactory {
    def types = [:]

    private ComputerFactory() {
        def laptop = new Laptop()
        def tower = new Desktop()
        types.put("MacBookPro6_2", laptop)
        types.put("SunTower", tower)
    }

    def ofType(computer) {
        types[computer]
    }
}

使用函数的“记忆”功能可以实现相同的效果：

def computerOf = { type ->
    def of = [MacBookPro6_2: new Laptop(), SunTower: new Desktop()]
    return of[type]
}
def computerOfType = computerOf.memoize()

两种实现方式的比较：

@Test
void flyweight_computers() {
    def bob = new AssignedComputer(
            ComputerFactory.instance.ofType("MacBookPro6_2"),
            "Bob"
    )
    def steve = new AssignedComputer(
            ComputerFactory.instance.ofType("MacBookPro6_2"),
            "Steve"
    )
    assertEquals(bob.computerType, steve.computerType)

    def sally = new AssignedComputer(
            computerOfType("MacBookPro6_2"),
            "Sally"
    )
    def betty = new AssignedComputer(
            computerOfType("MacBookPro6_2"),
            "Betty"
    )
    assertEquals(sally.computerType, betty.computerType)
}

元编程

给 Integer 扩展 Classifier 类的方法：

class MetaClassTest {
    {
        Integer.metaClass.isPerfect = {
            Classifier.isPerfect(delegate)
        }
        Integer.metaClass.isAbundant = {
            Classifier.isAbundant(delegate)
        }
        Integer.metaClass.isDeficient = {
            Classifier.isDeficient(delegate)
        }
    }

    @Test
    void meta_integer_classifier() {
        assertTrue 6.isPerfect()
        assertFalse 6.isAbundant()
        assertFalse 6.isDeficient()
    }
}

在 C# 中可以通过扩展方法来实现类似的效果，Java 中貌似只能通过 AOP 来实现方法扩展。

---

1. Pure Functions - GeeksforGeeks ↩︎

2. First-class Function（头等函数） - MDN Web 文档术语表：Web 相关术语的定义 _ MDN ↩︎

3. 高阶函数_百度百科 ↩︎