函数式编程和java

在计算机科学中，函数式编程是一种编程范式，通过应用和组合函数来构建程序。它是一种声明式编程范式(对应命令式编程)，其中函数定义是将数值映射到其他数值的表达式树，而不是更新程序运行状态的命令式语句序列。

函数的定义

数学上的函数

是自变量到因变量的映射关系, 函数的三要素: 定义域, 值域, 对应关系

无副作用

函数不依赖外部参数, 结果是确定的
无状态

函数每次调用结果相同
映射

定义域必定映射值域上的值

抽象表达:

\[f = (x_1, x_2,\ldots,x_n) \rightarrow y \]

编程中的函数

函数或子程序是一个执行特定任务的程序指令序列，被包装成一个单元。然后，这个单元可以在任何需要执行该特定任务的程序中使用。

编程函数的三要素: 参数列表, 参数名称, 返回值

这些"函数"有许多不同的名称: 子过程(subroutine), 过程(procedure), 方法(method), 他们想要表达的对象存在一定的区别, 但大体上具备以下性质:

可以有副作用

函数可以修改外部状态, 或进行IO对函数外产生影响
可以有状态

相同参数被多次调用的结果不同
可以没有映射

参数没有对应的返回值(void)

如果函数符合数学函数的特征, 可以称为纯函数(pure function)

抽象表达:

\[f = (x_1,x_2,\ldots,x_n) \rightarrow (y, \text{sied-effect}) \]

起源

lambda演算

λ演算（读作lambda演算）由数学家阿隆佐·邱奇在20世纪30年代首次发表，它从数理逻辑（Mathematical logic）中发展而来，使用变量绑定（binding）和代换规则（substitution）来研究函数如何抽象化定义（define）、函数如何被应用（apply）以及递归（recursion）的形式系统。

λ演算和图灵机等价（图灵完备，作为一种研究语言又很方便）。

lambda演算是一种数学符号系统, 具有和图灵机等价的计算能力.

定义

lambda表达式由以下部分构成

变量, $v_1, v_2, v_3,...,v_n...$
抽象, 符号 $'\lambda'$ (读作lambda)和 $'.'$ (点)
括号 ()

一组lambda表达式, 用 $\Lambda$ 表示, 或称lambda项, 可以归纳定义为:

如果 $x$ 是一个变量, 那么 $\displaystyle x\in \Lambda$, 即任何变量都是lambda项
如果 $x$ 是一个变量并且 $\displaystyle M \in \Lambda$, 那么 $\left(\lambda x.M \in \Lambda\right)$, $M$ 是抽象的主体, 抽象也是lambda项
如果 $M,N\in \Lambda$, 那么 $(M\ N)\in \Lambda$, 应用同样是lambda项

其中, 规则2被称为抽象, 规则3被称为应用.

符号

为了保持 lambda 表达式的符号整洁, 通常应用以下约定

最外面的括号被删除：使用 $M\ N$ 替换 $(M\ N)$
应用假定为左关联, 即 $M\ N\ P$ 替换 $((M\ N)\ P)$
抽象的主体尽可能向右延伸, 即 $ \lambda x.M\ N$ 是 $\lambda x.(M\ N)$而不是 $(\lambda x.M)\ N$
抽象可以收缩: $\lambda x.\lambda y.\lambda z.N$ 可以缩写为 $\lambda x.y.z.N$

自由变量和绑定变量

抽象运算符, 即$\lambda$ , 可以绑定抽象主体中所有它的变量, 属于抽象范围内的变量称为绑定变量, 所有其它变量称为自由变量.

例如: $\lambda y.x\ x\ y$ 中, $y$ 是绑定变量, $x$ 是自由变量.

变量受到最近的抽象影响. 例如: $\lambda x.y(\lambda x.z\ x)$ 中, 抽象主体中的 $x$ 受到第二个lambda表达式$(\lambda x.z\ x)$约束.

假定 lambda表达式 $M$ 的自由变量集合为 $FV(M)$, 定义如下:

$FV(x) = \{x\}$, 表示lambda表达式 $x$ 的自由变量集合为 $\{x\}$
$FV(\lambda x.M) = FV(M)/\{x\}$, 表示lambda表达式 $\lambda x.M$ 的自由变量集合为 $M$ 的自由变量集合排除 $\{x\}$
$FV(M\ N) = FV(M)\cup FV(N)$, 表示lambda表达式 $M$ 的自由变量集合与lambda表达式 $N$ 的自由变量集合的并集

不包含自由变量的表达式称为封闭表达式. 封闭的 lambda 表达式也称为组合器，相当于组合逻辑中的项

规约

规约表示lambda表达式的简化方式

有三种方式: $\alpha$ 变换, $\beta$ 规约, $\eta$ 规约

$\alpha$ 变换

alpha变换可以修改变量的名称, 也叫做alpha-renaming. 例如, $\lambda x.x$ 经过alpha变换可以转换为 $\lambda y.y$

其含义等价于函数参数可以重命名为不影响函数体的名称: $f(x) = 2x$ 等价于 $f(y) = 2y$

$\beta$ 规约

beta规约可以简化lambda表达式, beta规约指lambda应用可以对抽象体内的变量进行代换, 其实际上是函数的参数替换.

例如: $\lambda x.x * x \ 2$ 经过beta规约后变为: $2 * 2$, 即 $f(x) = x*x, f(2) = 2 * 2$

$\eta$ 规约

对于 $\lambda x.M\ x$, 如果 $x \notin FV(M)$, 那么 $\lambda x.M\ x \equiv M$, 实际上是抽象的简化

例如: $\lambda x.\lambda y.y\ x\equiv \lambda y.y$, $(x) \rightarrow (y) \rightarrow y \equiv (y) \rightarrow y$ ,

java中的lambda

现在, 许多语言引入了函数式编程和lambda表达式.

语法

以java为例, java中的lambda表达式的结构为:

\[(参数列表) \rightarrow \{lambda体\} \]

其中, 连接参数列表和lambda体的箭头符号是-和>组合构成的.

当只有一个参数时, 参数括号可以省略

当参数类型可以推断时, 参数类型可以省略

当lambda体只有一行是, lambda体大括号可以省略

public class Test {
  public static void main() {
    Runnable runnable = () -> System.out.println("hello world lambda");
    runnable.run();
  }
}

lambda表达式只能用来实现函数式接口.

在java中, 函数式接口指只有一个未实现方法的接口.

通过@FunctionalInterface注解标记, 可以在编译时检查.

@FunctionalInterface
public interface Runnable {
    public abstract void run();
}

abstract class Foo {
  public abstract void foo();
}
class Test {
  public static void main() {
    // 编译错误: Target type of a lambda conversion must be an interface
    Foo foo = () -> System.out.println("hello world lambda");
  }
}

然而java中, 不存在函数约束类型, 没有对应接口时无法使用lambda表达式.

// kotlin中的lambda
val printHelloWorld = { println("hello world")} // printHelloWorld的类型是 () -> Unit
printHelloWorld()
val printLog = { msg: Any -> println("log ---- " + msg)} // printLog的类型是 (Any) -> Unit
printLog("helle world")

java中的lambda表达式, 一定程度是上对匿名内部类的简化, 几乎所有场合中, lambda表达式换成匿名内部类不会影响运行结果. 尽管他们的实现方式上区别较大.

public class Test {
  public static void main() {
    Runnable runnable = new Runnable() { public void run() { System.out.println("hello world"); } };
    runnable.run();
  }
}

因此, 在java中, 不用将lambda视作所谓函数, 而是一个定义了某种逻辑的回调对象, 该对象通过函数式接口进行约束.

常见的一些函数式接口:

Runnable: 一段代码片段的包装

Callable: 可调用的对象, 返回一个值, 与Supplier的不同是方法是抛出异常的.

Function: 接收一个参数映射为另一个值的函数

Predicate: 接收一个参数, 返回true或false

Supplier: 使用该函数生成一个对象(生成器)

Consumer: 消费器, 接收一个参数进行处理, 无返回值

Comparator: 比较器, 接收同类的两个对象, 比较大小

BiFunction: Function的两个参数版本

BiPredicate: Predicate的两个参数版本

BiConsumer: Consumer的两个参数版本

BinaryOperator: 本质上是一个BiFunction, 接收的两个参数和返回类型相同.

值得注意的是, 因为java中的基本类型不能作为泛型使用, 因此, 泛型定义的函数式接口接收的对象总是需要装箱, 使用时又总是要拆箱, 对性能有一定影响

而java内部为基础类型提供了额外的函数式接口, 这里不在赘述, 使用时应当注意基本类型装箱拆箱的问题.

方法引用

方法引用的语法是: 方法来源::方法名

对静态方法引用时, 方法来源是类名, 对实例方法引用时, 方法来源是对象.

方法引用可以实现与引用的方法具有相同的的参数列表和返回值类型的函数式接口, 被引用的方法名称和实现的函数式接口的方法名并不重要.

class Test {
  private String name;

  Test(String name) {
    this.name = name;
  }

  public static void main(String[] args) {
    Runnable runnable = Test::printRun;
    runnable.run(); // 输出 run
    Runnable objRunnable = new Test("bob")::printName;
    objRunnable.run(); // 输出 bob
  }

  public static void printRun() {
    System.out.println("run");
  }

  public void printName() {
    System.out.println(name);
  }
}

如果使用实例的方法引用, 会捕获该实例.

捕获

lambda表达式可以捕获外部变量.

public IntSupplier incrementer() {
  var integer = new AtomicInteger();
  return integer::incrementAndGet; // () -> integer.incrementAndGet();
}

这个方法构造了一个捕获外部变量, 可以重复调用获取递增序列的生成器.

var incrementer = incrementer();
System.out.println(incrementer.getAsInt()); // 1
System.out.println(incrementer.getAsInt()); // 2

捕获非常常见, 大多数lambda捕获并不会对捕获的变量做出修改, 每次被调用是仍然能够得出相同的结果(如果捕获的变量不会在其他位置发生改变), 因此这种lambda表达式仍然是无状态的.

但是类似上文中的捕获中, 捕获变量的状态会发生改变, 因此这种lambda是有状态的.

为了避免外部变量的改变因此lambda表达式捕获的错误, java规定了捕获的变量必须是final的

public IntSupplier incrementer() {
  int i = 0;
  return () -> ++i; // 编译错误: Variable used in lambda expression should be final or effectively final
}

public Supplier<String> test() {
  String a = "";
  a = "b";
  return () -> a; // 编译错误: Variable used in lambda expression should be final or effectively final
}

lambda可以捕获lambda外的this, 并访问其字段

class Test {
  String value = "hello world";
  public void foo() {
    Runnable runnable = () -> System.out.println(value); // 隐式地捕获了this, 等价于System.out.println(this.value)
    runnable.run();
    Runnable runnable1 = () -> {
      value = "hello"; // 隐式地捕获了this, 等价于 this.value = "hello";
      System.out.println(value); // hello
    };
    runnable1.run();
  }
}

上面的代码中, 你可以对value做出修改, 这是因为对value的访问实际上是通过捕获了this实现的, 被捕获的this是不变的.

显然, 虽然不能修改被捕获的变量, 可以修改被捕获的变量指向的对象的状态, 并且, 也可以在外部对该对象的字段进行修改, 在lambda内部对外部修改也是可见的.

函数式编程特性

无副作用

前文提到, 计算机科学中的副作用指的是除了可能的函数的返回值外, 还会对产生附加的影响, 例如修改函数外的变量, 修改参数, 亦或者存在IO等等.

在某些情况下函数副作用会给程序设计带来不必要的麻烦，给程序带来十分难以查找的错误，并降低程序的可读性与可移植性。严格的函数式语言要求函数必须无任何副作用，但功能性静态函数本身的目的正是产生某些副作用。在生命科学中，副作用往往带有贬义，但在计算机科学中，副作用有时正是“主要作用”。

纯函数

纯函数（英语：Pure Function）——输入输出数据流全是显式（英语：Explicit）的。

显式的意思是，函数与外界交换数据只有一个唯一渠道——参数和返回值；函数从函数外部接受的所有输入信息都通过参数传递到该函数内部；函数输出到函数外部的所有信息都通过返回值传递到该函数外部。

不可变

下面是一段树的变换的代码, 将一棵树的左右节点交换.

class TreeNode {
  private Object val;
  private TreeNode left;
  private TreeNode right;

  TreeNode(Object val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }

  // 方法一, 原地交换, 修改原树的节点的左右引用
  public static void reverseTree1(TreeNode root) {
    if (root == null) {
      return;
    }
    var left = root.left;
    root.left = root.right;
    root.right = left;
    reverseTree1(root.left);
    reverseTree1(root.right);
  }
  
  // 方法二, 创建一个新的树, 新树的左节点映射原树的右节点, 新树的右节点映射原树的左节点
  // 使用这种方式变换, TreeNode的字段定义可以改为final.
  // 准确来说, 这里是映射而非变换
  public static TreeNode reverseTree2(TreeNode root) {
    if (root == null) {
      return null;
    }
    return new TreeNode(root.val, reverseTree2(root.right), reverseTree2(root.left));
  }
}

这两种方式各有场景, 但在函数式编程中, 一个函数不应该去改变原有的引用值，避免对运算的其他部分造成影响, 一个元如果是引用值，请使用一个副本（克隆、复制、替代等方式）来得到状态变更.

不可变带来的好处有很多, 例如

稳定不变, 可以作为key, 可以缓存起来重复使用
防止错误修改带来的bug
线程安全, 因此无需考虑同步, 编写会并行的代码时更简单
没有循环引用, 如果A和B互相存在引用, 那么实际创建的对象, 要么A引用B要么B引用A, 不会同时出现AB相互引用的情况
更容易理解的代码, 创建对象后就不会再发生变化, 因此不会出现某个方法修改对象导致逻辑变化, 造成理解上的困难, 所见即所得.

然而, 代价就是更多的对象和gc

高阶函数和科里化

高阶函数是对其他函数进行操作的函数，操作可以是将它们作为参数，或者是返回它们。简单来说，高阶函数是一个接收函数作为参数或将函数作为输出返回的函数。

const curry = (func) => {
    const curried = (...args) => {
        if(args.length >= func.length) {
            return func(...args)
        } else {
            return (...args2) => {
                return curried(...args.concat(args2))
            }

        }
    }
    return curried;
}
const curringAdd = curry((a,b) => a + b)
curringAdd(1)(2) // 3

柯里化：一个lambda函数只能有一个参数，柯里化就是将多参数函数（例如(x, y) -> x + y）转换成符合lambda函数约定的情况，已经知道一个lambda函数的输入和输出也可以是函数，那么基于它，可以把多参数函数和单参数函数做以下转换：

(x, y) -> x + y ====> x -> y -> x + y.

外层函数接受一个参数x返回一个函数λy.x + y，这个返回函数（内层函数）又接受一个参数y返回x + y，x绑定于外层函数，y绑定于内层函数，这样我们就在满足lambda函数只接受一个参数的约束下实现了多参数函数的功能.

java并不能实现这种通用的科里化函数, 只能以下面方式实现类似的功能.

class Test {
  public static Function<Integer, Function<Integer, Integer>> curry(
      BiFunction<Integer, Integer, Integer> numFunc) {
    return (num1) -> (num2) -> numFunc.apply(num1, num2);
  }

  public static void main(String[] args) {
    var curry = curry(Integer::sum);
    var c = curry.apply(1).apply(2);
    System.out.println(c); // 3
  }
}

上面这个例子中, 因为都是基础类型运算, 可以考虑使用等价的基础类型的函数式接口, 避免装箱拆箱.

class Test {
  public static IntFunction<IntUnaryOperator> curry(IntBinaryOperator numFunc) {
    return (num1) -> (num2) -> numFunc.applyAsInt(num1, num2);
  }

  public static void main(String[] args) {
    var curry = curry(Integer::sum);
    var c = curry.apply(1).applyAsInt(2);
    System.out.println(c);
  }
}

组合函数

在使用纯函数和柯里化时很容易写出洋葱代码，h(g(f(x)))，也就是一层包一层的代码，将多个依次调用的函数组合在一起，避免洋葱代码

Function<String, String> concat = "abc"::concat;
Function<String, Integer> length = String::length;
// 组合前
length.apply(concat.apply("xxx")); // 6

// 组合后
Function<String, Integer> compose = concat.andThen(length);
compose.apply("xxx"); // 6