精华内容
下载资源
问答
  • 随着 John Hughes 的一篇论文"为什么函数式编程如此重要"("Why Functional Programming Matters")的发布,它强力论证了主流思想在忽视函数式编程中可能犯的错误。这几乎是你唯一能听到的声音了。 本文试图向大多数...

    对于函数式编程来说,1989/1990 是一个相当黑暗的年代。面向对象程序设计日益突出的表现,使得工业界对于函数式编程的关注越来越少。随着 John Hughes 的一篇论文"为什么函数式编程如此重要"("Why Functional Programming Matters")的发布,它强力论证了主流思想在忽视函数式编程中可能犯的错误。这几乎是你唯一能听到的声音了。

    本文试图向大多数非函数式程序员去论述函数式编程的意义,并同时帮助函数式程序员发现其优势并加以利用。

    我引用的那篇论文总共有23页,其中大部分的内容都是举例阐述作者的观点。它的中心论点相当简洁,讨论激烈,并且与我们上周讨论的主题有关,这就是 模块化 。原谅文章开头部分的大量引用,这是因为 Hughes 的文章写的太好以致于不能省略。

    现在人们普遍认为模块化设计是编程的关键。但是,有个非常重要的点容易被忽视。当用模块化编程去解决问题,需要把一个问题分解为子问题,解决所有子问题后再合并结果。分解原问题的方式直接取决于如何合并结果。因此,为了从概念上提升模块化能力,在编程语言中需要提供新的胶水能力( glue )。

    但我们一直在进步,Hughes 认为绝大多数人谈论到函数式编程的优势时,会经常讨论到:无副作用(side-effect free) 和 不包含赋值语句 (contain no assignment statements)。因此,表达式可以在任何时候计算并替换为其值, 这样程序就是引用透明的(referentially transparent)。即使到了今天也经常讨论计算时值不可变(value of immutability)无副作用(side-effect free),当然,这些很有价值。但对于不熟悉的人来说,并不是很好的方式去解释函数式编程(FP)。

    例如范畴论的"优势"非常明显,但如果其他人不认真了解它,就不会对此感到惊讶。它说了许多函数式编程没有的内容(没有赋值,没有副作用,没有控制流),但是并没有说它的内容是什么。函数式编程听起来就像严守清规戒律的僧徒,牺牲了生活中的乐趣来希望自己变得纯粹。对于物质利益更感兴趣的人来说,这些优势完全没有说服力。

    使用函数式编程程序员会说,函数式编程是数量级更轻的一种,因此开发人员效率更高。

    但为什么会是这样?唯一可能的理由是传统编程中大概有90%的代码是赋值语句,这就是函数式编程优势的基础。在函数式编程中,赋值语句可以省略,这显然很荒谬。如果省略赋值语句带来了如此巨大好处,那么 FORTRAN 程序员可能20年来都这样做了。

    如果函数式编程这些特性不能够说服你,那么什么内容能既诠释函数式编程的威力,又指明函数式程序员所追求的方向呢?想一下结构化程序设计出现的年代,Hughes 总结它的优势可能可以归为一句话:结构化程序设计不包括 goto 语句。这与函数式编程所提的负面优势情形一样。

    事后来看,结构化程序设计这些特性虽然有用,但并没有触及到问题的核心。结构化与非结构化程序设计最重要的不同之处是: 结构化程序设计是一种模块化设计方式。模块化设计带来了极大生产力的提升:

    • 小模块可以快速方便的编写。
    • 通用模块可以复用,加快后续开发进度。
    • 模块化编程能够被单元测试,帮助减少debug时间。

    缺少goto语句有助于"小范围"编程,模块化则有利用"大范围"编程。现在我们回到最初提的问题:分解问题的方式直接依赖于胶水粘合解决结果的方式。

    接下来我们会讲述函数式语言提供的两种新的,很重要的胶水能力。这是函数式编程能力的关键-它提高了模块化能力。它也是函数式程序员必须实现的目标 - 更小更简单更通用的模块,通过新的胶水能力粘合在一起。

    两个新的胶水能力是

    • 高阶函数
    • 惰性求值

    **高阶函数(Higher-order functions)**能够使简单函数粘合成更复杂的函数。我想大多数读者都熟悉这个想法。论文中的例子是foldr,它在列表( list )上抽象了一个通用的计算模式,例如以下几个例子:

    sum = foldr (+) 0
    product = foldr (*) 1
    anytrue = foldr or False
    alltrue = foldr and True
    length = foldr count 0 // where count a n = n + 1
    map f = foldr (Cons .f) Nil
    summatrix = sum . map sum

    更多的例子。

    这些例子总以让读者信服一点:模块化可以走的更远。将简单函数( sum )模块化为高阶函数和一些简单参数的组合,就得到高阶函数(foldr),可以用来编写列表中其他函数而不需要额外开发。

    这不仅仅只适用于列表( list ), 你可以为任何数据结构编写高阶函数。

    所有这些都可以实现,因为函数在传统编程中不可分割,在函数式编程中能够表示为高价函数和特殊函数的组合。一旦定义好,高阶函数使一些操作更容易实现。无论何时定义一个新的数据类型,应该编写高阶函数处理它。这使得操作数据类型变得容易,并且将细节知识进行本地化表示。

    **惰性求值( Lazy evaluation)**需要更多的思考去了解为什么 Hughes 将它归为模块化的机制: 惰性求值使得模块化程序做为生成器成为现实,并且能构造大量可能的答案,选择器会选择合适的一个。没有惰性求值这些不会被实现。(如果可能,那要在有无限生成器的情况下)

    我们已经在函数语言上下文中描述了惰性求值,但是如此有用的特性应该加到非函数式语言中。惰性求值和副作用会共存么?不幸的是他们不能:在命令式符号中增加惰性求值是可能的,但是这种结合会让程序员的工程更加困难。

    对于那些喜欢混合函数和非函数构造的语言,需要考虑一些问题。

    为什么它会让程序员的工作更困难呢?

    因为惰性求值的威力需要程序员放弃程序执行时各部分之间顺序执行的控制能力,这会使带有副作用的编程变得困难,因为预测它们的发生顺序和是否发生,需要足够了解它们内嵌的上下文信息。这种全局依赖性将会破坏函数式语言中的模块性。惰性求值是为改善这种情况设计的。

    下面一系列例子来证明惰性求值和高阶函数的威力: 牛顿-拉佛森平方根法; 数值微分与积分;评估博弈树的 alpha-beta 启发式算法。在所有的例子中,它表现出了如何迅速达到强大和富有表现力的抽象层次,令人印象深刻,值得我们仔细学习。

    Why Functional Programming Matters John Hughes, Research Topics in Functional Programming, 1990 (based on an earlier Computer Journal paper that appeared in 1989).

    转载于:https://juejin.im/post/5c9f27706fb9a05e5716324a

    展开全文
  • 函数式编程中的重要概念

    千次阅读 2019-06-26 11:15:17
    函数式编程中的重要概念函数式编程范式的意义函数类型与高阶函数部分函数柯里化闭包递归记忆化 原文地址 函数式编程范式的意义 在众多的编程范式中,大多数开发人员比较熟悉的是面向对象编程范式。一方面是由于面向...


    原文地址

    函数式编程范式的意义

    在众多的编程范式中,大多数开发人员比较熟悉的是面向对象编程范式。一方面是由于面向对象编程语言比较流行,与之相关的资源比较丰富;另外一方面是由于大部分学校和培训机构的课程设置,都选择流行的面向对象编程语言。面向对象编程范式的优点在于其抽象方式与现实中的概念比较相近。比如,学生、课程、汽车和订单等这些现实中的概念,在抽象成相应的类之后,我们很容易就能理解类之间的关联关系。这些类中所包含的属性和方法可以很直观地设计出来。举例来说,学生所对应的类 Student 就应该有姓名、出生日期和性别等基本的属性,有方法可以获取到学生的年龄、所在的班级等信息。使用面向对象的编程思想,可以直观地在程序要处理的问题和程序本身之间,建立直接的对应关系。这种从问题域到解决域的简单对应关系,使得代码的可读性很强。对于初学者来说,这极大地降低了上手的难度。

    函数式编程范式则相对较难理解。这主要是由于函数所代表的是抽象的计算,而不是具体的实体。因此比较难通过类比的方式来理解。举例来说,已知直角三角形的两条直角边的长度,需要通过计算来得到第三条边的长度。这种计算方式可以使用函数来表示。length(a, b)=√a²+b² 就是具体的计算方式。这样的计算方式与现实中的实体没有关联。

    基于计算的抽象方式可以进一步提高代码的复用性。在一个学生信息管理系统中,可能会需要找到一个班级的某门课程的最高分数;在一个电子商务系统中,也可能会需要计算一个订单的总金额。看似风马牛不相及的两件事情,其实都包含了同样的计算在里面。也就是对一个可迭代的对象进行遍历,同时在遍历的过程中执行自定义的操作。在计算最高分数的场景中,在遍历的同时需要保存当前已知最高分数,并在遍历过程中更新该值;在计算订单总金额的场景中,在遍历的同时需要保存当前已累积的金额,并在遍历过程中更新该值。如果用 Java 代码来实现,可以很容易写出如下两段代码。清单 1 计算学生的最高分数。

    清单 1. 计算学生的最高分数的代码

    int maxMark = 0;
    for (Student student : students) {
      if (student.getMark() > maxMark) {
        maxMark = student.getMark();
      }
    }
    

    清单 2. 计算订单的总金额的代码

    BigDecimal total = BigDecimal.ZERO;
    for (LineItem item : order.getLineItems()) {
       total = total.add(item.getPrice().multiply(new BigDecimal(item.getCount())));
    }
    

    在面向对象编程的实现中,这两段代码会分别添加到课程和订单所对应的类的某个方法中。课程对应的类 Course 会有一个方法叫 getMaxMark,而订单对应的类 Order 会有一个方法叫 getTotal。尽管在实现上存在很多相似性和重复代码,由于课程和订单是两个完全不相关的概念,并没有办法通过面向对象中的继承或组合机制来提高代码复用和减少重复。而函数式编程可以很好地解决这个问题。

    我们来进一步看一下清单 1 和清单 2 中的代码,尝试提取其中的计算模式。该计算模式由 3 个部分组成:

    • 保存计算结果的状态,有初始值。
    • 遍历操作。
    • 遍历时进行的计算,更新保存计算结果的状态值。

    把这 3 个元素提取出来,用伪代码表示,就得到了清单 3 中用函数表示的计算模式。iterable 表示被迭代的对象,updateValue 是遍历时进行的计算,initialValue 是初始值。

    清单 3. 计算模式的伪代码

    function(iterable, updateValue, initialValue) {
      value = initialValue
      loop(iterable) {
          value = updateValue(value, currentValue)
      }
      return value
    }
    

    了解函数式编程的读者应该已经看出来了,这就是常用的 reduce 函数。使用 reduce 对清单 1 和清单 2 进行改写,可以得到清单 4 中的两段新的代码。

    清单 4. 使用 reduce 函数改写代码

    reduce(students, (mark, student) -> {
       return Math.max(student.getMark(), mark);
    }, 0);
     
    reduce(order.lineItems, (total, item) -> {
       return total.add(item.getPrice().multiply(new 
    BigDecimal(item.getCount())))
    }, BigDecimal.ZERO);
    

    函数类型与高阶函数

    对函数式编程支持程度高低的一个重要特征是函数是否作为编程语言的一等公民出现,也就是编程语言是否有内置的结构来表示函数。作为面向对象的编程语言,Java 中使用接口来表示函数。直到 Java 8,Java 才提供了内置标准 API 来表示函数,也就是 java.util.function 包。Function<T, R> 表示接受一个参数的函数,输入类型为 T,输出类型为 RFunction 接口只包含一个抽象方法 R apply(T t),也就是在类型为 T 的输入 t 上应用该函数,得到类型为 R 的输出。除了接受一个参数的 Function 之外,还有接受两个参数的接口 BiFunction<T, U, R>TU 分别是两个参数的类型,R 是输出类型。BiFunction 接口的抽象方法为 R apply(T t, U u)。超过 2 个参数的函数在 Java 标准库中并没有定义。如果函数需要 3 个或更多的参数,可以使用第三方库,如 Vavr 中的 Function0Function8

    除了 FunctionBiFunction 之外,Java 标准库还提供了几种特殊类型的函数:

    • Consumer<T>:接受一个输入,没有输出。抽象方法为 void accept(T t)
    • Supplier<T>:没有输入,一个输出。抽象方法为 T get()
    • Predicate<T>:接受一个输入,输出为 boolean 类型。抽象方法为 boolean test(T t)
    • UnaryOperator<T>:接受一个输入,输出的类型与输入相同,相当于 Function<T, T>
    • BinaryOperator<T>:接受两个类型相同的输入,输出的类型与输入相同,相当于BiFunction<T,T,T>
    • BiPredicate<T, U>:接受两个输入,输出为 boolean 类型。抽象方法为 boolean test(T t, U u)

    在本系列的第一篇文章中介绍 λ 演算时,提到了高阶函数的概念。λ 项在定义时就支持以 λ 项进行抽象和应用。具体到实际的函数来说,高阶函数以其他函数作为输入,或产生其他函数作为输出。高阶函数使得函数的组合成为可能,更有利于函数的复用。熟悉面向对象的读者对于对象的组合应该不陌生。在划分对象的职责时,组合被认为是优于继承的一种方式。在使用对象组合时,每个对象所对应的职责单一。多个对象通过组合的方式来完成复杂的行为。函数的组合类似对象的组合。上一节中提到的 reduce 就是一个高阶函数的示例,其参数 updateValue 也是一个函数。通过组合,reduce 把一部分逻辑代理给了作为其输入的函数 updateValue。不同的函数的嵌套层次可以很多,完成复杂的组合。

    在 Java 中,可以使用函数类型来定义高阶函数。上述函数接口都可以作为方法的参数和返回值。Java 标准 API 已经大量使用了这样的方式。比如 IterableforEach 方法就接受一个 Consumer 类型的参数。

    在清单 5 中,notEqual 返回值是一个 Predicate 对象,并使用在 Streamfilter 方法中。代码运行的输出结果为 2 和 3。

    清单 5. 高阶函数示例

    public class HighOrderFunctions {
        private static <T> Predicate<T> notEqual(T t) {
             return (v) -> !Objects.equals(v, t);
        }public static void main(String[] args) {
           List.of(1, 2, 3)
               .stream()
               .filter(notEqual(1))
               .forEach(System.out::println);
        }
    }
    

    部分函数

    部分函数(partial function)是指仅有部分输入参数被绑定了实际值的函数。清单 6 中的函数 f(a, b, c) = a + b +c 有 3 个参数 a、b 和 c。正常情况下调用该函数需要提供全部 3 个参数的值。如果只提供了部分参数的值,如只提供了 a 值,就得到了一个部分函数,其中参数 a 被绑定成了给定值。假设给定的参数 a 的值是 1,那新的部分函数的定义是 fa(b, c) = 1 + b + c。由于 a 的实际值可以有无穷多,也有对应的无穷多种可能的部分函数。除了只对 a 绑定值之外,还可以绑定参数 b 和 c 的值。

    清单 6. 部分函数示例

    function f(a, b, c) {
      return a + b + c;
    }
    ​
    function fa(b, c) {
      return f(1, b, c);
    }
    

    部分函数可以用来为函数提供快捷方式,也就是预先绑定一些常用的参数值。比如函数 add(a, b) = a + b 用来对 2 个参数进行相加操作。可以在 add 基础上创建一个部分函数 increase,把参数 b 的值绑定为 1。increase 相当于进行加 1 操作。同样的,把参数值 b 绑定为 -1 可以得到函数 decrease。

    Java 标准库并没有提供对部分函数的支持,而且由于只提供了 Function 和 BiFunction,部分函数只对 BiFunction 有意义。不过我们可以自己实现部分函数。部分函数在绑定参数时有两种方式:一种是按照从左到右的顺序绑定参数,另外一种是按照从右到左的顺序绑定参数。这两个方式分别对应于 清单 7 中的 partialLeft 和 partialRight 方法。这两个方法把一个 BiFunction 转换成一个 Function。

    清单 7. 部分函数的 Java 实现

    public class PartialFunctions {
      private static  <T, U, R> Function<U, R> partialLeft(BiFunction<T, 
    U, R> biFunction, T t) {
       return (u) -> biFunction.apply(t, u);
      }private static  <T, U, R> Function<T, R> partialRight(BiFunction<T, 
    U, R> biFunction, U u) {
       return (t) -> biFunction.apply(t, u);
      }
    ​
    ​
      public static void main(String[] args) {
        BiFunction<Integer, Integer, Integer> biFunction = (v1, v2) -> v1 
    - v2;
        Function<Integer, Integer> subtractFrom10 = 
    partialLeft(biFunction, 10);
        Function<Integer, Integer> subtractBy10 = partialRight(biFunction, 
    10);
        System.out.println(subtractFrom10.apply(5)); // 5
        System.out.println(subtractBy10.apply(5));   // -5
      }
    }
    

    柯里化

    柯里化(currying)是与λ演算相关的重要概念。通过柯里化,可以把有多个输入的函数转换成只有一个输入的函数,从而可以在λ演算中来表示。柯里化的名称来源于数学家 Haskell Curry。Haskell Curry 是一位传奇性的人物,以他的名字命令了 3 种编程语言,Haskell、Brook 和 Curry。柯里化是把有多个输入参数的求值过程,转换成多个只包含一个参数的函数的求值过程。对于清单 6 的函数 f(a, b, c),在柯里化之后转换成函数 g,则对应的调用方式是 g(a)(b)©。函数 (x, y) -> x + y 经过柯里化之后的结果是 x -> (y -> x + y)。

    柯里化与部分函数存在一定的关联,但两者是有区别的。部分函数的求值结果永远是实际的函数调用结果;而柯里化函数的求值结果则可能是另外一个函数。以清单 6 的部分函数 fa 为例,每次调用 fa 时都必须提供剩余的 2 个参数。求值的结果都是具体的值;而调用柯里化之后的函数 g(a) 得到的是另外的一个函数。只有通过递归的方式依次求值之后,才能得到最终的结果。

    闭包

    闭包(closure)是函数式编程相关的一个重要概念,也是很多开发人员比较难以理解的概念。很多编程语言都有闭包或类似的概念。

    在上一篇文章介绍 λ 演算的时候提到过 λ 项的自由变量和绑定变量,如 λx.x+y 中的 y 就是自由变量。在对λ项求值时,需要一种方式可以获取到自由变量的实际值。由于自由变量不在输入中,其实际值只能来自于执行时的上下文环境。实际上,闭包的概念来源于 1960 年代对 λ 演算中表达式求值方式的研究。

    闭包的概念与高阶函数密切相关。在很多编程语言中,函数都是一等公民,也就是存在语言级别的结构来表示函数。比如 Python 中就有函数类型,JavaScript 中有 function 关键词来创建函数。对于这样的语言,函数可以作为其他函数的参数,也可以作为其他函数的返回值。当一个函数作为返回值,并且该函数内部使用了出现在其所在函数的词法域(lexical scope)的自由变量时,就创建了一个闭包。我们首先通过一段简单的 JavaScript 代码来直观地了解闭包。

    清单 8 中的函数 idGenerator 用来创建简单的递增式的 ID 生成器。参数 initialValue 是递增的初始值。返回值是另外一个函数,在调用时会返回并递增 count 的值。这段代码就用到了闭包。idGenerator 返回的函数中使用了其所在函数的词法域中的自由变量 count。count 不在返回的函数中定义,而是来自包含该函数的词法域。在实际调用中,虽然 idGenerator 函数的执行已经结束,其返回的函数 genId 却仍然可以访问 idGenerator 词法域中的变量 count。这是由闭包的上下文环境提供的。

    清单 8. JavaScript 中的闭包示例

    function idGenerator(initialValue) {
    let count = initialValue;
    return function() {
           return count++;
    };
    }let genId = idGenerator(0);
    genId(); // 0
    genId(); // 1
    

    从上述简单的例子中,可以得出来构成闭包的两个要件:

    • 一个函数
    • 负责绑定自由变量的上下文环境

    函数是闭包对外的呈现部分。在闭包创建之后,闭包的存在与否对函数的使用者是透明的。比如清单 8 中的 genId 函数,使用者只需要调用即可,并不需要了解背后是否有闭包的存在。上下文环境则是闭包背后的实现机制,由编程语言的运行时环境来提供。该上下文环境需要为函数创建一个映射,把函数中的每个自由变量与闭包创建时的对应值关联起来,使得闭包可以继续访问这些值。在 idGenerator 的例子中,上下文环境负责关联变量 count 的值,该变量可以在返回的函数中继续访问和修改。

    从上述两个要件也可以得出闭包这个名字的由来。闭包是用来封闭自由变量的,适合用来实现内部状态。比如清单 8 中的 count 是无法被外部所访问的。一旦 idGenerator 返回之后,唯一的引用就来自于所返回的函数。在 JavaScript 中,闭包可以用来实现真正意义上的私有变量。

    从闭包的使用方式可以得知,闭包的生命周期长于创建它的函数。因此,自由变量不能在堆栈上分配;否则一旦函数退出,自由变量就无法继续访问。因此,闭包所访问的自由变量必须在堆上分配。也正因为如此,支持闭包的编程语言都有垃圾回收机制,来保证闭包所访问的变量可以被正确地释放。同样,不正确地使用闭包可能造成潜在的内存泄漏。

    闭包的一个重要特性是其中的自由变量所绑定的是闭包创建时的值,而不是变量的当前值。清单 9 是一个简单的 HTML 页面的代码,其中有 3 个按钮。用浏览器打开该页面时,点击 3 个按钮会发现,所弹出的值全部都是 3。这是因为当点击按钮时,循环已经执行完成,i 的当前值已经是 3。所以按钮的 click 事件处理函数所得到是 i 的当前值 3。

    清单 9. 闭包绑定值的演示页面

    <!DOCTYPE html>
    <html lang="en">
    <head>
       <title>Test</title>
    </head>
    <body>
       <button>Button 1</button>
       <button>Button 2</button>
       <button>Button 3</button>
    </body>
    <script>
       var buttons = document.getElementsByTagName("button");
       for (var i = 0; i < buttons.length; i++) {          
         buttons[i].addEventListener("click", function() {
           alert(i);              
         });
       }
    </script>
    </html>
    

    如果把 JavaScript 代码改成清单 10 所示,就可以得到所期望的结果。我们创建了一个匿名函数并马上调用该函数来返回真正的事件处理函数。处理函数中访问的变量 i 现在成为了闭包的自由变量,因此 i 的值被绑定到闭包创建时的值,也就是每个循环执行过程中的实际值。

    清单 10. 使用闭包解决绑定值的问题

    var buttons = document.getElementsByTagName("button");
    for (var i = 0; i < buttons.length; i++) {          
       buttons[i].addEventListener("click", function(i) {
          return function() {
            alert(i);              
          }
        }(i));
    }
    

    在 Java 中有与闭包类似的概念,那就是匿名内部类。在匿名内部类中,可以访问词法域中声明为 final 的变量。不是 final 的变量无法被访问,会出现编译错误。匿名内部类提供了一种方式来共享局部变量。不过并不能对该变量的引用进行修改。在清单 11 中,变量 latch 被两个匿名内部类所使用。

    清单 11. Java 中的匿名内部类

    public class InnerClasses {public static void main(String[] args) {
        final CountDownLatch latch = new CountDownLatch(1);final Future<?> task1 = ForkJoinPool.commonPool().submit(() -> {
          try {
            Thread.sleep(ThreadLocalRandom.current().nextInt(2000));
          } catch (InterruptedException e) {
            e.printStackTrace();
          } finally {
            latch.countDown();
          }
        });final Future<?> task2 = ForkJoinPool.commonPool().submit(() -> {
          final long start = System.currentTimeMillis();
          try {
            latch.await();
          } catch (InterruptedException e) {
            e.printStackTrace();
          } finally {
            System.out.println("Done after " + (System.currentTimeMillis() 
    - start) + "ms");
          }
        });try {
          task1.get();
          task2.get();
        } catch (InterruptedException | ExecutionException e) {
          e.printStackTrace();
        }
      }
    }
    

    可以被共享的变量必须声明为 final。这个限制只对变量引用有效。只要对象本身是可变的,仍然可以修改该对象的内容。比如一个 List 类型的变量,虽然对它的引用是 final 的,仍然可以通过其方法来修改 List 内部的值。

    递归

    递归(recursion)是编程中的一个重要概念。很多编程语言,不仅限于函数式编程语言,都有递归这样的结构。从代码上来说,递归允许一个函数在其内部调用该函数自身。有些函数式编程语言并没有循环这样的结构,而是通过递归来实现循环。递归和循环在表达能力上是相同的,只不过命令式编程语言偏向于使用循环,而函数式编程语言偏向于使用递归。递归的优势在于天然适合于那些需要用分治法(divide and conquer)解决的问题,把一个大问题划分成小问题,以递归的方式解决。经典的通过递归解决的问题包括阶乘计算、计算最大公约数的欧几里德算法、汉诺塔、二分查找、树的深度优先遍历和快速排序等。

    递归分为单递归和多递归。单递归只包含一个对自身的引用;而多递归则包含多个对自身的引用。单递归的例子包括列表遍历和计算阶乘等;多递归的例子包括树遍历等。在具体的编程实践中,单递归可以比较容易改写成使用循环的形式,而多递归则一般保持递归的形式。清单 12 给出了 JavaScript 实现的计算阶乘的递归写法。

    清单 12. 递归方式计算阶乘

    int fact(n) {
      if (n === 0) {
          return 1;
      } else {
          return n * fact(n - 1);
      }
    }
    

    而下面的清单 13 则是 JavaScript 实现的使用循环的写法。

    清单 13. 循环方式计算阶乘

    int fact_i(n) {
       let result = 1;
       for (let i = n; i > 0; i--) {
         result = result * i;
       }
       return result;
    }
    

    有一种特殊的递归方式叫尾递归。如果函数中的递归调用都是尾调用,则该函数是尾递归函数。尾递归的特性使得递归调用不需要额外的空间,执行起来也更快。不少编程语言会自动对尾递归进行优化。

    下面我们以欧几里德算法来说明一下尾递归。该算法的 Java 实现比较简单,如清单 14 所示。函数 gcd 的尾调用是递归调用 gcd 本身。

    清单 14. 尾递归的方式实现欧几里德算法

    int gcd(x, y) {
       if (y == 0) {
          return x;
       }
       return gcd(y, x % y);
    }
    

    尾递归的特性在于实现时可以复用函数的当前调用栈的帧。当函数执行到尾调用时,只需要简单的 goto 语句跳转到函数开头并更新参数的值即可。相对于循环,递归的一个大的问题是层次过深的函数调用栈导致占用内存空间过大。对尾递归的优化,使得递归只需要使用与循环相似大小的内存空间。

    记忆化

    记忆化(memoization)也是函数式编程中的重要概念,其核心思想是以空间换时间,提高函数的执行性能,尤其是使用递归来实现的函数。使用记忆化要求函数具有引用透明性,从而可以把函数的调用结果与调用时的参数关联起来。通常是做法是在函数内部维护一个查找表。查找表的键是输入的参数,对应的值是函数的返回结果。在每次调用时,首先检查内部的查找表,如果存在与输入参数对应的值,则直接返回已经记录的值。否则的话,先进行计算,再用得到的值更新查找表。通过这样的方式可以避免重复的计算。

    最典型的展示记忆化应用的例子是计算斐波那契数列 (Fibonacci sequence)。该数列的表达式是 F[n]=F[n-1]+Fn-2。清单 15 是斐波那契数列的一个简单实现,直接体现了斐波那契数列的定义。函数 fib 可以正确完成数列的计算,但是性能极差。当输入 n 的值稍微大一些的时候,计算速度就非常之慢,甚至会出现无法完成的情况。这是因为里面有太多的重复计算。比如在计算 fib(4) 的时候,会计算 fib(3) 和 fib(2)。在计算 fib(3) 的时候,也会计算 fib(2)。由于 fib 函数的返回值仅由参数 n 决定,当第一次得出某个 n 对应的结果之后,就可以使用查找表把结果保存下来。这里需要使用 BigInteger 来表示值,因为 fib 函数的值已经超出了 Long 所能表示的范围。

    清单 15. 计算斐波那契数列的朴素实现

    import java.math.BigInteger;
     
    public class Fib {
     
     public static void main(String[] args) {
       System.out.println(fib(40));
     }
     
     private static BigInteger fib(int n) {
       if (n == 0) {
         return BigInteger.ZERO;
       } else if (n == 1) {
         return BigInteger.ONE;
       }
       return fib(n - 1).add(fib(n - 2));
     }
    }
    

    清单 16 是使用记忆化之后的计算类 FibMemoized。已经计算的值保存在查找表 lookupTable 中。每次计算之前,首先查看查找表中是否有值。改进后的函数的性能有了数量级的提升,即便是 fib(100) 也能很快完成。

    清单 16. 使用记忆化的斐波那契数列计算

    import java.math.BigInteger;
    import java.util.HashMap;
    import java.util.Map;
     
    public class FibMemoized {
     
     public static void main(String[] args) {
       System.out.println(fib(100));
     }
     
     private static Map<Integer, BigInteger> lookupTable = new 
    HashMap<>();
     
     static {
       lookupTable.put(0, BigInteger.ZERO);
       lookupTable.put(1, BigInteger.ONE);
     }
     
     private static BigInteger fib(int n) {
       if (lookupTable.containsKey(n)) {
         return lookupTable.get(n);
       } else {
         BigInteger result = fib(n - 1).add(fib(n - 2));
         lookupTable.put(n, result);
         return result;
       }
     }
    }
    

    很多函数式编程库都提供了对记忆化的支持,会在本系列后续的文章中介绍。

    总结
    本文对函数式编程相关的一些重要概念做了系统性介绍。理解这些概念可以为应用函数式编程实践打下良好的基础。本文首先介绍了函数式编程范式的意义,接着介绍了函数类型与高阶函数、部分函数、柯里化、闭包、递归和记忆化等概念。下一篇文章将介绍 Java 8 所引入的 Lambda 表达式和流处理。

    展开全文
  • 什么函数式编程? 函数式编程是一种面向函数和函数组合的编程方式。  什么是函数?从数学的角度,函数即Function,是从集合A到集合B的一种映射关系。如果集合A中的每一个元素都对应到集合B中的某一个元素,那么...

    什么是函数式编程?

      函数式编程是一种面向函数和函数组合的编程方式。
      什么是函数?从数学的角度,函数即Function,是从集合A到集合B的一种映射关系。如果集合A中的每一个元素都对应到集合B中的某一个元素,那么这种映射关系就叫做函数。比如每个人都有一个名字,那么“人”这个集合中的每一个元素,都能对应到String集合中的一个字符串,因此“将人通过名字映射到字符串”是一个函数,它的签名可以是mapToName(Person):String,换个名称,就是getName(Person):String
      再举一个例子,每个人都有父亲,因此“人”能通过“父亲”这个关系映射到另一个“人”,函数签名是getFather(Person):Person,当集合A与B相等时,称为自函数即Endofunction。同时注意上述两个函数是全局静态的,不像方法需要挂靠在特定的“类”之下。
      若是函数有多个参数,那么可以将这些参数看成一个新的数据类型或一个N元组。如sum(a:Int, b:Int):Int,可以看成是将一个(Int,Int)的元组映射到Int的一个函数。除了这些有名称的函数外,还可以通过Lambda表达式产生匿名函数,如(i,j) => i+j就定义了一个匿名的sum函数。
      那么函数组合呢?是指给定两个函数,f1(a):A->B(从A集合映射到B集合),f2(b):B->C(从B集合映射到C集合),那么就能将两个函数组合起来得到一个新的函数f3(a)=f2(f1(a)),从A映射到C,也写作f3=f2°f1或f1 andThen f2。以上面的两个函数为例子,能组合出第三个函数“获得父亲的名字”:

    def getFatherName(p: Person):String = getName(getFather(p)) //通过两个函数来实现新函数
    val getFatherName:Person=>String = getName andThen getFather //通过直接组合两个函数产生新函数

    函数式编程有哪些特性?

      个人认为函数式编程虽然有很多重要特性,但核心的特性主要是函数的组合与引用透明,后续其它的特性以及优点均由这两个特性衍生而来。衍生的这些特性以及优点我们留到下篇介绍。

    核心1. 关键在于函数的组合

      上面的getFatherName的函数是通过组合两个固定的函数产生的,如若将getFather替换为其它任何从“人”到“人”的函数,比如getMother,那么就能得到getMotherName(p:Person):String=getName(getMother(p))。
      因此,若有一个f:Person=>Person可以作为参数,那么就能动态地产生不同的获取名字的方法,而这种接受函数作为参数的函数称为高阶函数,也是函数组合的主要手段,而函数在函数式编程中也成为了可以独立存在,并成为输入和输出的一等公民:

    def getPersonName(p: Person, f:Person=>Person) = getName(f(p))
    def getMotherName(p: Person) = getPersonName(p, getMother)
    def getFatherName(p: Person) = getPersonName(p, getFather)
    def getSelfName(self: Person) = getPersonName(self, p => p) //使用Lambda定义了一个返回自身的匿名函数

      高阶函数除了可以接受函数作为参数外,还可以输出函数作为返回结果,涉及闭包和函数生成器等概念。如:

    def sumByN(n: Int):Int=>Int = i => i+n
    val sumBy3:Int=>Int = sumByN(3) = i => i+3
    sumBy3(2) //return 5
    sumBy3(1) //return 4

     高阶函数作为一种组合的手段还会衍生出其它复杂的函数组合方式,相对比较复杂,会在后续文章中解释。如Option[]和Future[]等单子类(Monad)的组合方式:

    val o1:Option[Int] = Option(1)
    val o2:Option[String] = o1.map(_ * 10).flatmap(i => Option(i.toString())) //使用了Lambda作为匿名函数
    o2.get //return "10"

    核心2. 引用透明与无副作用

      引用透明,是指每次将同一个参数输入给函数,函数总是能返回同样的输出,因此总是可以将(函数+输入)替换为函数执行的结果,这种无论何时何地的可替换性就称为引用透明Referential Transparency。比如def square(a:Int) = a*a这个函数是引用透明的,因为无论何时,遇到square(2),总是可以用2*2的结果4来替换square(2)。
      若想实现引用透明,那么这个函数一定是无副作用的,或者称纯函数Pure Function。比如下面这个getAge的函数就不是引用透明的,因为它修改了宿主的状态,从而每次调用p.getAge()都不能用它的结果来替换。

    class Person(var age:Int) {
        def getAge() {
            age = age + 1
            age
        }
    }
    val p = new Person(10)
    p.getAge() //11
    p.getAge() //12

     因此,可以实现下面这个版本来实现同样的功能,却保持无副作用:

    class Person(val age:Int) {
        def getAge():(Person, Int) {
            (new Person(age + 1), age + 1)
        }
    }
    val p1 = new Person(10)
    val (p2, p1Age) = p1.getAge() //p1Age = 11
    val (p3, p2Age) = p2.getAge() //p2Age = 12
    p1.getAge() //依然返回(_,11)

      关于更多如何处理副作用的方式,及其优点会在系列的后续文章中介绍。

    核心3. 申明式的风格

     申明式的风格与命令式的风格相对。命令式的风格就像我们编写的传统语言,如C, java等,通过一条条的指令来告诉计算机应该进行什么操作,从而最终实现某一功能。而申明式的风格则相反,强调描述最终要实现的功能的样子,语言背后的类库会帮助我们完成这些功能。一个典型的申明式的例子就是Spring中的注解,我们只是申明了@Autowire,表明此处需要一个某类型的成员变量,而框架和类库会自动帮我们解决这个问题;而用命令式的实现注入,则需要手工创建一个对象,并调用set方法。两者在可读性和抽象层次上都有所不同。
     申明式的风格是强调函数作为一种映射的自然结果。比如,scala的Future就有map方法对Future类型进行映射,可以在Future的结果返回之前,就将原来的Future[X]映射为Future[Y]类型,如下面的代码直接对Future[Int]进行映射,产生了Future[String],最后的结果即为新Future返回的结果,并且主线程不会停止(除非刻意等待这个Future的返回结果):

    //scala
    val f:Future[Int] = xxx
    val f1:Future[Int] = f.map(i => i*10) //还记得对象上的方法能在逻辑上转换为函数吗?等价为: def map(f, i => i*10)
    val f2:Future[String] = f1.map(j => j.toString()) //f2的返回即为最终结果
    
    val f2 = f.map(i => i*10).map(j => j.toString())//内联整理之后更加简洁
    println("over") //能瞬间运行到这里,因为线程不会停止

      在上面的例子中,我们通过函数的组合来描述功能本身。我们将i => i*10和j => j.toString()这两个函数组合进了map这个函数,因此很直接地申明了我们想要的最终功能:即将一个还未产生的数字*10并转换为String。我们其实并不知道scala的Future.map()是如何将一个还未返回的结果进行变换处理的,甚至不知道这个变换是在哪个线程上执行的,在这方面类库帮了我们很多,就像Spring能@Autowire一样地神奇。因此,整个语言就通过函数的组合表现出了申明式的风格,使得编程本身所面向的抽象层次更高,不再执着于如何实现,而是强调要实现什么。

    与面向对象的区别?

    1. 函数是一等公民

      在面向对象的语言中,只有类才是一等公民,而所谓函数在其中只能称为类和对象的”方法”。”方法”一词暗指其属于某一对象(除非申明static),而函数则优先将其考虑为全局的,因为它代表了一种将A类对象转换为B类对象的一种客观存在的映射关系。
      上面例子中的getAge()看上去更像是一个”方法”,但任何对象中的”方法”都可以被改写为函数,这两种结构在形式上的等价的。上面这个例子可以改写为:def getAge(p:Person):(Person, Int),如此一来getAge就从隶属于Person类的方法转为全局的函数了。
      在面向对象的语言中,只有对象才是一等公民,因此只能将对象(和数值)作为返回值和参数传递。部分拥有函数式功能的OO语言,如java8和C#,可以将Lambda表达式会被解析为函数接口类型的对象,依然在面向对象的框架下将函数作为对象传递。
      如下面的一段java8代码能返回一个Function类型的对象,虽然能实现类似高阶函数的功能,但本质仍然是对象的传递。

    public static Function<String, String> addPost(Function<String, String> f1) {
        return (String s) -> f1.apply(s)+"_post";
    }

    2. 强调函数的无副作用

      在面向对象的语言中,方法也可以是无副作用的;而在既支持函数式编程又支持面向对象的scala中,函数也可以被误写成带有副作用的。但是scala在语法上更支持无副作用函数。
      无副作用的函数强调这样的函数只是一种映射关系,任何输入的对象在参与计算后都不会/不能被更改,同时执行这种映射关系自然也不会修改函数之外的环境。函数式编程强调的是函数本身,与方法相比,函数本身与所在的类的字段是平级的关系,类的字段属于函数之外的环境,因此是不能被变更的。
      而面向对象则强调以对象为粒度去封装状态,并且时常暴露一些变更的方法,这些方法存在的目的就是操作和变更对象的成员变量。这与函数不变更函数之外的环境是相反的理念。

    3. 对函数组合的支持

      对函数组合的支持一方面体现在语法上。虽然scala也用面向对象的手法实现函数的传递,但它看上去更像是函数式编程,能够支持函数类型的申明、匿名函数及类型的快速推导,所以在表现力和简洁性方面远优于java8。下面这段代码是用scala来实现之前java8的例子:

    def addPost(f1: String=>String) = s => f1(s)+"_post"

      此外,在语法上Scala等更函数式的语言还提供单子类操作的快捷语法糖:

    for {
        f1 <- Future{longIntProducer()} //f1花一段时间后返回一个Int
        f2 <- Future{longIntProcessor(f1)} //f2又花一段时间返回另一个Int
    } yield f2 //以Future的形式返回f2的结果

      对函数组合的支持另一方面体现在类库上。比如java也有Future这个类型,但是java的Future并不像scala的Future那样支持map映射,它仅支持线程等待的get操作,通过get操作可以让当前线程等待,并获取Future返回的结果。之前scala的Future的例子用java来实现的话效果会是这样:

    //java
    Future<Integer> f = xxx;
    Integer i = f.get(); //注意!当前线程会停止,直到Future计算结束
    Integer j = i * 10; //然后再依次对i进行其它计算
    String s = j.toString();

      可以看出面向对象的语言更倾向于命令式的风格,强调按步骤详细描述功能的实现过程,提供的类库也反映出这个现象;而函数式语言提供的类库大多为高阶函数,已经封装了很多高层次的功能,因此整体语言更倾向于申明式的风格,抽象层次更高。

    总结

      函数式编程虽然有很多特点和特征,但我认为其本质是面向函数以及函数的组合。它的核心特征是强调函数组合、引用透明以及申明式的风格,因此和面向对象的主要不同点也在于函数的地位、副作用的处理以及命令与申明式的区别上。
      我觉得函数式编程与之前熟悉的面向对象的风格有很大的差异,是编程范畴下的另一种的范式。虽然有一定的学习门槛,但一旦越过后能带来很大的效率提升,有很多的优点值得我们进一步探索。
      因此一方面出于编程效率和技能的原因,建议在生产工作中逐步尝试;然而更重要其背后的思想价值。函数式编程背后有一套数学理论作为支撑,在世界观与认知上与传统编程有很大的不同,如果想要拓展个人的视野和思维方式,那么函数式编程就更有学习的价值了。

    应该如何学习?

      如果想再深入地学习函数式编程,建议结合scala这门语言。因为这门语言既支持面向对象及命令式的编程,又支持函数式的申明式编程,功能强大特性丰富。在微观细节上命令式风格的代码更容易理解,但在复杂功能上申明式的风格效率更高更直观,可以说scala能很好地同时具有两者的优点。
      本系列后续第二篇会继续介绍函数式编程的其它特性和优点,这些特性都或多或少地源于它的核心特征。第三篇会介绍如何从面向对象的思维模式切换到函数式的思维模式,重点讲解OO的设计模式在函数式编程的框架上要如何实现。第四篇会简单介绍函数式编程背后与范畴论有关的数学知识,以领略函数式编程的世界观。

    展开全文
  • 到目前为止,在本系列的每期文章中,我都说明了为什么理解函数式编程非常重要。但是,有些原因是在多期文章中进行说明的,只有在综合思路的更大背景中,才可以完全了解这些原因。在本期文章中,我会探讨函数式编程...

    到目前为止,在本系列的每期文章中,我都说明了为什么理解函数式编程非常重要。但是,有些原因是在多期文章中进行说明的,只有在综合思路的更大背景中,才可以完全了解这些原因。在本期文章中,我会探讨函数式编程方兴未艾的所有原因,并综合前几期文章中的一些个人经验教训。

    在计算机科学短短的发展历史中,技术的主流有时会产生分支,包括实用分支和学术分支。20 世纪 90 年代的 4GL(第四代语言)是一个实用分支,而函数式编程是来自学术界的一个示例。每隔一段时间,都会有一些分支加入主流,函数式编程目前也是这种情况。函数式语言不仅在 JVM 上刚刚崭露头脚(其中两个最有趣的新语言是 Scala 和 Clojure),在 .NET 平台上也是才开始得到应用,在 .NET 平台上,F# 是头等公民。为什么所有平台都如此欢迎函数式编程?答案是,随着时间的推移,随着运行时都要能够处理更多的繁忙工作,开发人员已经能够将日常任务的更多控制权割让给它们。

    割让控制权

    在 20 世纪 80 年代初,在我上大学的时候,我们使用一个被称为 Pecan Pascal 的开发环境。其独特的特性是,相同的 Pascal 代码可以在 Apple II 或 IBM PC 上运行。Pecan 工程师使用某个称为 “字节码” 的神秘东西实现了这一壮举。开发人员将 Pascal 代码编译为 “字节码”,它可以在每个平台本地编写的 “虚拟机” 上运行。这是一个可怕的体验!所生成的代码慢得让人痛苦,甚至简单的类赋值也非常缓慢。当时的硬件还没有准备好迎接这个挑战。

    在发布 Pecan Pascal 之后的十年,Sun 发布了 Java,Java 使用了相同的架构,对于 20 世纪 90 年代中期的硬件环境,运行该代码显得有些紧张,但最终取得了成功。Java 还增加了其他开发人员友好的特性,如自动垃圾收集。使用过像 C++ 这样的语言之后,我再也不想在没有垃圾收集的语言中编写代码。我宁愿花将时间花在更高层次上的抽象上,思考解决复杂业务问题的方法,也不愿意在内存管理等复杂的管道问题上浪费时间。

    Java 缓解了我们与内存管理的交互;函数式编程语言使我们能够用高层次的抽象取代其他核心构建块,并更注重结果而不是步骤。

    结果比步骤更重要

    函数式编程的特点之一是存在强大的抽象,它隐藏了许多日常操作的细节(比如迭代)。我在本系列文章中一直使用的一个示例是数字分类:确定某个数字是 perfectabundant 还是 deficient(完整的定义参见 第一期文章)。清单 1 中显示的 Java 实现可以解决这个问题:

    清单 1. 自带缓存总数的 Java 数字分类器
    import static java.lang.Math.sqrt;
    
    public class ImpNumberClassifier {
        private Set<Integer> _factors;
        private int _number;
        private int _sum;
    
        public ImpNumberClassifier(int number) {
            _number = number;
            _factors = new HashSet<Integer>();
            _factors.add(1);
            _factors.add(_number);
            _sum = 0;
        }
    
        private boolean isFactor(int factor) {
            return _number % factor == 0;
        }
    
        private void calculateFactors() {
            for (int i = 1; i <= sqrt(_number) + 1; i++)
                if (isFactor(i))
                    addFactor(i);
        }
    
        private void addFactor(int factor) {
            _factors.add(factor);
            _factors.add(_number / factor);
        }
    
        private void sumFactors() {
            calculateFactors();
            for (int i : _factors)
                _sum += i;
        }
    
        private int getSum() {
            if (_sum == 0)
                sumFactors();
            return _sum;
        }
    
        public boolean isPerfect() {
            return getSum() - _number == _number;
        }
    
        public boolean isAbundant() {
            return getSum() - _number > _number;
        }
    
        public boolean isDeficient() {
            return getSum() - _number < _number;
        }
    }

    清单 1 中的代码是典型的 Java 代码,它使用迭代来确定和汇总系数。在使用函数式编程语言时,开发人员很少关心细节(比如迭代,由calculateFactors() 使用)和转换(比如汇总一个列表,该列表由 sumFactors() 使用),宁愿将这些细节留给高阶函数和粗粒度抽象。

    粗粒度的抽象

    用抽象来处理迭代等任务,使得需要维护的代码变得更少,因此可能出现错误的地方也就更少。清单 2 显示了一个更简洁的数字分类器,用 Groovy 编写,借用了 Groovy 的函数风格方法:

    清单 2. Groovy 数字分类器
    import static java.lang.Math.sqrt
    
    class Classifier {
      def static isFactor(number, potential) {
        number % potential == 0;
      }
    
      def static factorsOf(number) {
        (1..number).findAll { isFactor(number, it) }
      }
    
      def static sumOfFactors(number) {
        factorsOf(number).inject(0, {i, j -> i + j})
      }
    
      def static isPerfect(number) {
        sumOfFactors(number) == 2 * number
      }
    
      def static isAbundant(number) {
        sumOfFactors(number) > 2 * number
      }
    
      def static isDeficient(number) {
        sumOfFactors(number) < 2 * number
      }
    }

    清单 2 中的代码使用很少的代码完成 清单 1 的所有工作(减去缓存总数,这会重新出现在下面的示例中)。例如,用于确定 factorsOf() 中的系数的迭代消失了,替换为使用 findAll() 方法,它接受一个具有我的筛选器条件的代码块(一个高阶函数)。Groovy 甚至允许使用更简洁的代码块,它允许单参数块使用 it 作为隐含参数名称。同样,sumOfFactors() 方法使用了 inject(),它(使用 0 作为种子值)将代码块应用于每个元素,将每个对减少为单一的值。{i, j -> i + j} 代码块返回两个参数的总和;每次将列表 “折叠” 成一个对时,都会应用此块,产生总和。

    Java 开发人员习惯于框架 级别的重用;在面向对象的语言中进行重用所需的必要构件需要非常大的工作量,他们通常会将精力留给更大的问题。函数式语言在更细化的级别提供重用,在列表和映射等基本数据结构之上通过高阶函数提供定制,从而实现重用。

    少量数据结构,大量操作

    在面向对象的命令式编程语言中,重用的单元是类以及与这些类进行通信的消息,这些信息是在类图中捕获的。该领域的开创性著作是 Design Patterns: Elements of Reusable Object-Oriented Software(参阅 参考资料),至少为每个模式提供一个类图。在 OOP 的世界中,鼓励开发人员创建独特的数据结构,以方法的形式附加特定的操作。函数式编程语言尝试采用不同的方式来实现重用。它们更喜欢一些关键的数据结构(如列表、集和映射),并且在这些数据结构上采用高度优化的操作。传递数据结构和高阶函数,以便 “插入” 这种机制,针对某一特定用途对其进行定制。例如,在 清单 2 中,findAll() 方法接受使用一个代码块作为 “插件” 高阶函数(该函数确定了筛选条件),而该机制以有效方式应用了筛选条件,并返回经过筛选的列表。

    函数级的封装支持在比构建自定义类结构更细的基础级别上进行重用。此方法的优势之一已经体现在 Clojure 中。最近,库中的一些巧妙创新重写了 map 函数,使它可以自动并行化,这意味着所有映射操作都可以受益于没有开发人员干预的性能提升。

    例如,考虑一下解析 XML 的情况。大量的框架可用于在 Java 中完成这个任务,每个框架都有自定义的数据结构和方法语义(例如,SAX 与 DOM)。Clojure 将 XML 解析为一个标准的 Map 结构,而不是强迫您使用自定义的数据结构。因为 Clojure 中包含大量与映射配合使用的工具,如果使用内置的列表理解函数 for,那么执行 XPath 样式的查询就会很简单,如清单 3 所示:

    清单 3. 将 XML 解释为 Clojure
    (use 'clojure.xml)
    
    (def WEATHER-URI "http://weather.yahooapis.com/forecastrss?w=%d&u=f")
    
    (defn get-location [city-code]
      (for [x (xml-seq (parse (format WEATHER-URI city-code))) 
            :when (= :yweather:location (:tag x))]
        (str (:city (:attrs x)) "," (:region (:attrs x)))))
    
    (defn get-temp [city-code]
      (for [x (xml-seq (parse (format WEATHER-URI city-code))) 
            :when (= :yweather:condition (:tag x))]
        (:temp (:attrs x))))
    
    (println "weather for " (get-location 12770744) "is " (get-temp 12770744))

    在 清单 3 中,我访问雅虎的气象服务来获取某个给定城市的气象预报。因为 Clojure 是 Lisp 的一个变体,所有从内部读取是最简单的。对服务端点的实际调用发生在 (parse (format WEATHER-URI city-code)) 上,它使用了 String 的 format() 函数将 city-code 嵌入字符串。列表理解函数 for 放置了解析后的 XML,使用 xml-seq 将它投放到名称为 x 的可查询映射中。:when 谓词确定了匹配条件;在本例中,我要搜索一个标签(转换成一个 Clojure 关键字) :yweather:condition

    如欲了解从数据结构中读取值所用的语法,那么查看该语法中包含的内容会非常有用。在解析的时候,气象服务的相关调用会返回在此摘录中显示的数据结构:

    ({:tag :yweather:condition, :attrs {:text Fair, :code 34, :temp 62, :date Tue, 
       04 Dec 2012 9:51 am EST}, :content nil})

    因为已经为了与映射配合使用而优化了 Clojure,所以关键字在包含它们的映射上成为了函数。在 清单 3 中,对 (:tag x) 的调用是一个缩写,它等同于 “从存储在 x 中的映射检索与 :tag 键对应的值”。因此,:yweather:condition 产生与该键关联的映射值,其中包括我使用相同语法从中提取 :temp 的 attrs

    最初,Clojure 中令人生畏的细节之一是:与映射和其他核心数据结构进行交互的方法似乎有无限多种。然而,它反映了这样一个事实:在 Clojure 中,大多数内容都尝试解决这些核心的、优化的数据结构。它没有将解析的 XML 困在一个独特的框架中,相反,它试图将其转换为一个已存在相关工具的现有结构。

    对基础数据结构的依赖性的优点体现在 Clojure 的 XML 库中。为了遍历树形结构(如 XML 文档),1997 年创建了一个有用的数据结构,名为zipper(参阅 参考资料)。zipper 通过提供坐标系方向,让您可以结构性地导航树。例如,可以从树的根开始,发出 (-> z/down z/down z/left) 等命令,导航到第二级的左侧元素。Clojure 中已经有现成的函数可将解析的 XML 转换为 zipper,在整个树形结构中实现一致的导航。

    新的、不同的工具

    函数式编程提供了新的工具类型,以优雅的方式解决棘手的问题。例如,Java 开发人员不习惯尽能延迟生成其值的惰性 数据结构。而未来的函数式语言将对这种高级特性提供支持,一些框架将此功能加装到 Java 中。例如,清单 4 所示的数字分类器版本使用了 Totally Lazy 框架(参阅参考资料):

    清单 4. Java 数字分类器通过 Totally Lazy 使用惰性和函数式数据结构
    import com.googlecode.totallylazy.Predicate;
    import com.googlecode.totallylazy.Sequence;
    
    import static com.googlecode.totallylazy.Predicates.is;
    import static com.googlecode.totallylazy.numbers.Numbers.*;
    import static com.googlecode.totallylazy.predicates.WherePredicate.where;
    
    
    public class Classifier {
      public static Predicate<Number> isFactor(Number n) {
          return where(remainder(n), is(zero));
      }
    
      public static Sequence<Number> getFactors(final Number n){
          return range(1, n).filter(isFactor(n));
      }
    
      public static Sequence<Number> factors(final Number n) {
          return getFactors(n).memorise();
      }
    
      public static Number sumFactors(Number n){
          return factors(n).reduce(sum);
      }
    
      public static boolean isPerfect(Number n){
          return equalTo(n, subtract(sumFactors(n), n));
      }
    
      public static boolean isAbundant(Number n) {
        return greaterThan(subtract(sumFactors(n), n), n);
      }
    
      public static boolean isDeficient(Number n) {
        return lessThan(subtract(sumFactors(n), n), n);
      }
    
    }

    Totally Lazy 增加了惰性集合和流畅接口方法,大量使用静态导入,使代码具有可读性。如果您羡慕下一代语言中的某些特性,那么一些研究可能会提供可以解决某个特定问题的特定扩展。

    让语言迁就问题

    大多数开发人员都将他们的工作误解为接受一个复杂的业务问题,将它转换成 Java 等语言。他们的这种误解是因为 Java 并不是一种特别灵活的语言,它迫使您让自己的想法适应于已经存在的刚性结构。但是,当开发人员使用可塑语言时,他们看到了让语言迁就问题,而不是让问题迁就语言的机会。像 Ruby(它为领域特定语言 (DSL) 提供了比主流更友好的支持)等语言证明了这种潜在可能。现代函数式语言甚至走得更远。Scala 旨在协调内部 DSL 的托管,并且所有 Lisp(包括 Clojure)都可以提供无与伦比的灵活性,使开发人员能够让语言适应问题。例如,清单 5 使用了 Scala 中的 XML 基元来实现 清单 3 的天气示例:

    清单 5. Scala 的 XML 语法修饰
    import scala.xml._
    import java.net._
    import scala.io.Source
    
    val theUrl = "http://weather.yahooapis.com/forecastrss?w=12770744&u=f"
    
    val xmlString = Source.fromURL(new URL(theUrl)).mkString
    val xml = XML.loadString(xmlString)
    
    val city = xml \\ "location" \\ "@city"
    val state = xml \\ "location" \\ "@region"
    val temperature = xml \\ "condition" \\ "@temp"
    
    println(city + ", " + state + " " + temperature)

    Scala 是为获得可塑性而设计的,它支持操作符重载和隐式类型等扩展。在 清单 5 中,Scala 被扩展为可以使用 \\ 操作符支持类似 XPath 的查询。

    与语言的趋势相一致

    函数式编程的目标之一是最大程度地减少可变状态。在 清单 1 中,有两种类型的共享状态清单。_factors 和 _number 都存在,它们使代码测试变得更容易(编写原代码版本是为了说明最大可测试性),并可以折叠成更大的函数,从而消除它们。但是,_sum 是因为各种原因而存在。我预计,这段代码的用户可能需要检查多个分类。(例如,如果一个完美的检查失败,那么下一次我可能会检查百分比。)合计系数总数的操作可能很昂贵,所以我为它创建了一个经过惰性初始化的访问器。在第一次调用时,它会计算总和,并将它存储在 _sum 成员变量中,以便优化未来的调用。

    像垃圾收集一样,现在缓存也可以降级用于语言。清单 2 中的 Groovy 数字分类器忽略了 清单 1 中总数的惰性初始化。如果想要实现同样的功能,可以修改分类器,如清单 6 所示:

    清单 6. 手动添加一个缓存
    class ClassifierCachedSum {
      private sumCache
    
      ClassifierCachedSum() {
        sumCache = [:]
      }
    
      def sumOfFactors(number) {
        if (sumCache.containsKey(number))
          return sumCache[number]
        else {
          def sum = factorsOf(number).inject(0, {i, j -> i + j})
          sumCache.putAt(number, sum)
          return sum
        }
      }
      // ... other code omitted

    在最新版的 Groovy 中,清单 6 中的代码不再是必要的。考虑使用清单 7 中的改进版的分类器:

    清单 7. 备忘数字分类器
    class ClassifierMemoized {
      def static dividesBy = { number, potential ->
        number % potential == 0
      }
      def static isFactor = dividesBy.memoize()
    
      def static factorsOf(number) {
        (1..number).findAll { i -> isFactor.call(number, i) }
      }
    
      def static sumFactors = { number ->
        factorsOf(number).inject(0, {i, j -> i + j})
      }
      def static sumOfFactors = sumFactors.memoize()
    
      def static isPerfect(number) {
        sumOfFactors(number) == 2 * number
      }
    
      def static isAbundant(number) {
        sumOfFactors(number) > 2 * number
      }
    
      def static isDeficient(number) {
        sumOfFactors(number) < 2 * number
      }
    }

    任何纯函数(没有副作用的函数)都可以备忘,比如 清单 7 中的 sumOfFactors() 方法。备忘函数允许运行时缓存重复出现的值,从而消除手工编写缓存的需要。事实上,请注意执行实际工作的 getFactors() 和 factors() 方法之间的关系,该方法是备忘版本的 getFactors()。Totally Lazy 还为 Java 增加了备忘功能,这是反馈到主流中的另一个高级函数特性。

    由于运行时获得了更多的能力并且有多余的开销,开发人员可以将繁忙的工作割让给语言,将我们解放出来,去思考更重要的问题。Groovy 中的备忘功能就是众多示例中的一个;因为基础运行时允许这样做,所有现代语言都添加了函数式构造,包括 Totally Lazy 等框架。

    结束语

    因为运行时的能力变得更强,并且语言获得了更强大的抽象,所以开发世界变得更加函数化,这使开发人员可以花费更多的时间来思考结果的影响,而不是思考如何生成结果。由于高阶函数等抽象出现在语言中,它们将成为高度优化的操作的自定义机制。您不需要创建框架来处理问题(如 XML),您可以将其转换成您已经可以使用工具来处理的数据结构。

    随着第 20 期文章的发布,函数式思维 将告一段落,我将准备开始一个新的系列,探索下一代的 JVM 语言。Java 下一代 会让您对不久的将来有一个大致了解,并帮助您对必须投入新语言学习的时间作出明智选择。


    转载自:http://www.ibm.com/developerworks/cn/java/j-ft20/

    展开全文
  • 函数式编程

    2015-07-19 13:29:51
    相较于指令式编程,函数式编程强调函数的计算比指令的执行重要。相较于过程化编程,函数的计算可随时调用。以编写一个计算阶乘的函数例,我们可以编写一个循环程序解决问题,也可以使用递归来得到所有数字的乘积。...
  • 什么函数式编程

    万次阅读 2018-08-22 11:21:35
    当我们说起函数式编程来说,我们会看到如下函数式编程的长相: 函数式编程的三大特性: immutable data 不可变数据:像Clojure一样,默认上变量是不可变的,如果你要改变变量,你需要把变量copy出去修改。这样一来...
  • 函数式编程常用术语

    千次阅读 2017-02-11 20:56:50
    近年来函数式编程这种概念渐渐流行起来,尤其是在React/Vuejs这两个前端框架的推动下,函数式编程就像股新思潮一般瞬间席卷整个技术圈。虽然博主接触到的前端技术并不算深入,可这并不妨碍我们通过类似概念的延伸来...
  • 函数式编程和响应式编程

    万次阅读 2017-06-12 21:37:57
    函数式编程函数式编程是一系列被不公平对待的编程思想的保护伞,它的核心思想是,它是一种将程序看成是数学方法的求值、不会改变状态、不会产生副作用(后面我们马上会谈到)的编程方式。FP 核心思想强调: 声明式...
  • 原文地址:Functional-Light-JS ...分享,是 CSS 里最闪耀的一瞥;总结,是 JavaScript 中最严谨的逻辑。经过捶打磨练,成就了本书的中文版...本书包含了函数式编程之精髓,希望可以帮助大家在学习函数式编程的道路上走的
  • Kotlin函数式编程 (KotlinFunctionalProgramming) 陈光剑 1.函数式概述6 1.1.函数式简史6 1.2.函数式编程语言家族7 1.2.1.概述7 1.2.2.函数式编程语言介绍8 1.3.函数式编程的特征10 1.3.1.函数是"第一...
  • 欢迎来到函数式编程的世界。在这个只有函数的世界中,我们愉快地生活着,没有任何外部环境的依赖,没有状态,没有突变——永远没有。函数式编程是最近的一个热点。...本章的目的就是:用通俗的语言你介绍函数式编程
  • 从函数字面量发现函数式编程

    千次阅读 多人点赞 2015-04-27 11:54:09
    版权声明:本文由本人撰写并发表于2015年3月下半月的《程序员》杂志,原文题目《从字面量发现函数式编程》,本文版权归《程序员》杂志所有,未经许可不得转载。 引言 我相信很多像我一样初次接触函数式编程的...
  • Python函数式编程指南

    千次阅读 2014-04-14 12:38:45
    1.1. 什么函数式编程函数式编程使用一系列的函数解决问题。函数仅接受输入并产生输出,不包含任何能影响产生输出的内部状态。任何情况下,使用相同的参数调用函数始终能产生同样的结果。 在一个函数式的...
  • 1.1 什么函数式编程

    千次阅读 2014-07-18 16:00:58
    1.1 什么函数式编程?   想给函数式编程下个明确的定义,是困难的。因为,存在不同的函数语言,但是,并没有明确的、每种函数语言必须具有的特征集。尽管如此,函数语言仍有一些共同的属性,只是表达解决编程...
  • 函数式编程之函子

    千次阅读 2018-09-19 16:46:35
    8. 函子 昨天我们学习了组合与管道,在学习新的知识之前我们需要复习一下几个重要的函数,比如 curry,partial,compose,pipe。现在还能写出来吗?...今天我们要学习的是函数式编程中一个重要的概念——错...
  • 浅析C++的函数式编程

    千次阅读 多人点赞 2019-04-26 14:08:34
    函数式编程(Functional Programming,FP)思想几乎成为了目前编程语言的下一个主要的演化趋势。Java8在Java中通过lambda表达式、Stream API引入了函数式编程,那么C++中是否也支持函数式编程呢?答案是肯定的。目前...
  • 部分应用和复合,则是函数式编程重要特征。采用命令式编程时,每当我们感觉需要抽象出一个新的功能时,就会定义一个函数。在函数式编程中,被同样需要的新函数,往往无需定义,就能像变魔术一样产生,两位魔术师的...
  • 函数式编程扫盲篇

    万次阅读 多人点赞 2015-11-22 23:47:37
    1. 概论 在过去的近十年的时间里,面向对象编程大行其道。以至于在大学的教育里,...孰不知,在面向对象产生之前,在面向对象思想产生之前,函数式编程已经有了数十年的历史。 那么,接下来,就让我们回顾这
  • 最近接触到了K8S的架构,其中有一点很重要的是整体架构采用的是声明式编程,主要的编程范式有三种:命令式编程,声明式编程和函数式编程。 #命令式编程: 命令式编程的主要思想是关注计算机执行的步骤,即一步一步...
  • 《Java8函数式编程

    2017-01-12 12:53:21
    我的 Java 不好,对具体的 API 也不感兴趣,只是想从中看看函数式编程什么样子。面向对象编程是对数据进行抽象,函数式编程是对行为进行抽象,现实世界中,数据和行为并存,程序也是如此。面向对象也好,函数式...
  • 实战函数式编程:使用Ramda.js

    千次阅读 2017-05-13 20:02:42
    对我来说,使得JavaScript如此有趣的一个原因是它函数式编程方面的特性。从一开始函数就是JavaScript世界中的一等公民。这使得通过多种方式的组合编写优雅,富有表现力的代码成为可能。 然而,仅仅是拥有一些函数式...
  • 学会JavaScript函数式编程(第3部分)

    千次阅读 2018-12-29 16:42:06
    摘要: JS函数式编程入门。 原文:学会使用函数式编程的程序员(第3部分) 作者:前端小智 Fundebug经授权转载,版权归原作者所有。 本系列的其它篇: 学会使用函数式编程的程序员(第1部分) 学会使用函数式编程的...
  • 什么函数式编程?实用指南

    千次阅读 2021-05-15 11:17:27
    功能编程是指以最佳效果使用功能来创建干净且可维护的软件。本文通过JavaScript和Java中的实际示例说明了功能范例背后的概念。
  • 函数式编程含义

    千次阅读 2017-03-13 12:57:41
    1. 概论 在过去的近十年的时间里,面向对象编程大行其道。以至于在大学的教育里,...孰不知,在面向对象产生之前,在面向对象思想产生之前,函数式编程已经有了数十年的历史。 那么,接下来,就让我们回顾这
  • 越来越多的主流语言在设计的时候几乎无一例外都会参考**函数式特性**( `lambda` 表达式,原生支持 `map,reduce...`),就连面向对象语言的 `Java8` 也慢慢开始支持函数式编程,所以再不学习函数式编程可能就晚了!
  • 函数式编程和命令式编程

    万次阅读 2011-05-16 23:28:00
    <br />所谓命令式编程,是以命令主的,给机器提供一条又一条的命令序列让其原封不动的执行。程序执行的效率取决于执行命令的数量。因此才会出现大O表示法等等表示时间空间复杂度的符号。 <br />而函数...
  • [函数式编程]之美--开篇

    千次阅读 2013-04-24 14:05:43
    1 什么函数式编程 函数式编程(Functional Programming),顾名思义就是基于函数的编程模式,非过程、非对象。 In computer science, functional programming is a programming paradigm that treats ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 61,672
精华内容 24,668
关键字:

为什么函数式编程如此重要