函数式思维和函数式编程

问题导读

1.本文是如何理解函数式编程的？
2.如何用函数式的方式思考、函数式的方式编程实现？






作为一个对Haskell语言[1]彻头彻尾的新手，当第一次看到一个用这种语言编写的快速排序算法的优雅例子时，我立即对这种语言发生了浓厚的兴趣。下面就是这个例子：

[mw_shl_code=bash,true]quicksort :: Ord a => [a] -> [a]  
quicksort [] = []  
quicksort (p:xs) =  
    (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs[/mw_shl_code]

我很困惑。如此的简单和漂亮，能是正确的吗？的确，这种写法并不是“完全正确”的最优快速排序实现。但是，我在这里并不想深入探讨性能上的问题[2]。我想重点强调的是，纯函数式编程是一种思维上的改变，是一种完全不同的编程思维模式和方法，就相当于你要重新开始学习另外一种编程方式。

首先，让我先定义一个问题，然后用函数式的方式解决它。我们要做的基本上就是按升序排序一个数组。为了完成这个任务，我使用曾经改变了我们这个世界的快速排序算法[3]，下面是它几个基本的排序规则：

• 如果数组只有一个元素，返回这个数组
• 多于一个元素时，随机选择一个基点元素P，把数组分成两组。使得第一组中的元素全部 <p，第二组中的全部元素 >p。然后对这两组数据递归的使用这种算法。
  

那么，如何用函数式的方式思考、函数式的方式编程实现？在这里，我将模拟同一个程序员的两个内心的对话，这两个内心的想法很不一样，一个使用命令式的编程思维模式，这是这个程序员从最初学习编码就形成的思维模式。而第二个内心做了一些思想上的改造，清洗掉了所有以前形成的偏见：用函数式的方式思考。事实上，这程序员就是我，现在正在写这篇文章的我。你将会看到两个完全不同的我。没有半点假话。

让我们在这个简单例子上跟Java进行比较：

[mw_shl_code=bash,true]public class Quicksort  {  
  private int[] numbers;
  private int number;

  public void sort(int[] values) {
    if (values == null || values.length == 0){
      return;
    }
    this.numbers = values;
    number = values.length;
    quicksort(0, number - 1);
  }

  private void quicksort(int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high-low)/2];

    while (i <= j) {
      while (numbers < pivot) {
        i++;
      }
      while (numbers[j] > pivot) {
        j--;
      }

      if (i <= j) {
        swap(i, j);
        i++;
        j--;
      }
    }
    if (low < j)
      quicksort(low, j);
    if (i < high)
      quicksort(i, high);
  }

  private void swap(int i, int j) {
    int temp = numbers;
    numbers = numbers[j];
    numbers[j] = temp;
  }
}[/mw_shl_code]

哇塞。到处都是i和j，这是干嘛呢？为什么Java代码跟Haskell代码比较起来如此的长？这就好像是30年前拿C语言和汇编语言进行比较！从某种角度看，这是同量级的差异。[4]

让我们俩继续两个”我”之间的对话。

JAVA:

好 ，我先开始定义Java程序需要的数据结构。一个类，里面含有一些属性来保存状态。我觉得应该使用一个整数数组作为主要数据对象，针对这个数组进行排序。还有一个方法叫做sort，它有一个参数，是用来传入两个整数做成的数组，sort方法就是用来对这两个数进行排序。

[mw_shl_code=bash,true]public class Quicksort {  
    private int[] numbers;

    public void sort(int[] values) {

    }
}[/mw_shl_code]


HASKELL:

好，这里不需要状态，不需要属性。我需要定义一个函数，用它来把一个list转变成另一个list。这两个list有相同之处，它们都包含一样的元素，并有各自的顺序。我如何用统一的形式描述这两个list？啊哈！typeclass….我需要一个typeclass来实现这个…对，Ord.

[mw_shl_code=bash,true]quicksort :: Ord a => [a] -> [a]  
[/mw_shl_code]

我要从简单的开始，如果是空数组，如果数组是空的，我应该返回这个数组。但是…该死的，当这个数组是null时，程序会崩溃。让我来在sort方法开始的地方加一个if语句，预防这种事情。

[mw_shl_code=bash,true]if (values.length == 0 || values == null) {  
    return;
}[/mw_shl_code]

HASKELL:

先简单的，一个空list。对于这种情况，需要使用模式匹配。我看看如何使用，好的，非常棒！

[mw_shl_code=bash,true]quicksort [] = []  
[/mw_shl_code]

JAVA:

好的，现在让我用递归来处理正常的情况。正常的情况下，需要记录sort方法参数状态。需要它的长度，所以，我还需要在Quicksort类里添加一个新属性

[mw_shl_code=bash,true]public void sort(int[] values) {  
    if (values.length == 0 || values == null) {
        return;
    }
    this.numbers = values;
    this.length = values.length;
    quicksort(0, length - 1);
}[/mw_shl_code]

HASKELL:

这已经是递归了。不需要在再做任何事情。

[mw_shl_code=bash,true]No code. Nothing. Nada. That's good.  
[/mw_shl_code]


JAVA:

现在，我需要根据上面说明的规则实现快速排序的过程。我选择第一个元素作为基点元素，这不需要使用其它奇异方法。比较，递归。每次比较从两头同时遍历，一个从头至尾(i, 生成<p的list)，一个从尾至头(j, 生成>p的list)。每次在i方向遍历中发现有比j方向遍历的当前值大时，交互它们的位置。当i的位置超过j时，停止比较，对形成的两个新队列继续递归调用。

[mw_shl_code=bash,true]private void quicksort(int low, int high) {  
    int i = low, j = high;
    int pivot = numbers[low];

    while (i <= j) {
        while (numbers < pivot) {
           i++;
        }
        while (numbers[j] > pivot) {
            j--;
        }

        if (i <= j) {
            swap(i, j);
            i++;
            j--;
        }
    }

    if (low < j)
        quicksort(low, j);
    if (i < high)
        quicksort(i, high);
}[/mw_shl_code]


交换位置的方法：
[mw_shl_code=bash,true]private void swap(int i, int j) {  
    int temp = numbers;
    numbers = numbers[j];
    numbers[j] = temp;
}[/mw_shl_code]


使用Haskell

我先定义一个lesser和一个greater作为每次迭代的两个队列。等一下！我们可以使用标准的head和tail函数来获取第一个值作为基点数据。这样我们可以它的两个部分进行递归调用！

[mw_shl_code=bash,true]quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)  
[/mw_shl_code]

非常好，这里我声明了lesser和greater两个list，现在我将要用where——Haskell语言里一个十分强大的用来描述函数内部值(not 变量)的关键字——描述它们。我需要使用filter函数，因为我们已经得到除首元素之外的其它元素，我们可以调用(xs)，就是这样：

[mw_shl_code=bash,true] where
        lesser = filter (< p) xs
        greater = filter (>= p) xs[/mw_shl_code]

我试图用最详细的语言解释Java里用迭代+递归实现快速排序。但是，如果在java代码里，我们少写了一个i++，我们弄错了一个while循环条件，会怎样？好吧，这是一个相对简单的算法。但我们可以想象一下，如果我们整天写这样的代码，整天面对这样的程序，或者这个排序只是一个非常复杂的算法的第一步，将会出现什么情况。当然，它是可以用的，但难免会产生潜在的、内部的bug。

现在我们看一下关于状态的这些语句。如果出于某些原因，这个数组是空的，变成了null，当我们调用这个Java版的快速排序方法时会出现什么情况？还有性能上的同步执行问题，如果16个线程想同时访问Quicksort方法会怎样？我们就要需要监控它们，或者让每个线程拥有一个实例。越来越乱。

最终归结到编译器的问题。编译器应该足够聪明，能够“猜”出应该怎样做，怎样去优化[5]。程序员不应该去思考如何索引，如何处理数组。程序员应该思考数据本身，如何按要求变换数据。也许你会认为函数式编程给思考算法和处理数据增添的复杂，但事实上不是这样。是编程界普遍流行的命令式编程的思维阻碍了我们。

事实上，你完全没必要放弃使用你喜爱的命令式编程语言而改用Haskell编程。Haskell语言有其自身的缺陷[6]。只要你能够接受函数式编程思维，你就能写出更好的Java代码。你通过学习函数式编程能变成一个更优秀的程序员。

看看下面的这种Java代码？

[mw_shl_code=bash,true]public List<Comparable> sort(List<Comparable> elements) {  
    if (elements.size() == 0) return elements;

    Stream<Comparable> lesser = elements.stream()
    .filter(x -> x.compareTo(pivot) < 0)
    .collect(Collectors.toList());

    Stream<Comparable> greater = elements.stream()
    .filter(x -> x.compareTo(pivot) >= 0)
    .collect(Collectors.toList());

    List<Comparable> sorted = new ArrayList<Comparable>();
    sorted.addAll(quicksort(lesser));
    sorted.add(pivot);
    sorted.addAll(quicksort(greater));

    return sorted;

}[/mw_shl_code]

是不是跟Haskell代码很相似？没错，也许你现在使用的Java版本无法正确的运行它，这里使用了lambda函数，Java8中引入的一种非常酷的语法[7]。看到没有，函数式语法不仅能让一个程序员变得更优秀，也会让一种编程语言更优秀。 :)

函数式编程是一种编程语言向更高抽象阶段发展的自然进化结果。就跟我们认为用C语言开发Web应用十分低效一样，这些年来，我们也认为命令式编程语言也是如此。使用这些语言是程序员在开发时间上的折中选择。为什么很多初创公司会选择Ruby开发他们的应用，而不是使用C++？因为它们能使开发周期更短。不要误会。我们可以把一个程序员跟一个云计算单元对比。一个程序员一小时的时间比一个高性能AWS集群服务器一小时的时间昂贵的多。通过让犯错误更难，让出现bug的几率更少，使用更高的抽象设计，我们能使程序员变得更高效、更具创造性和更有价值。

感谢楼主分享