函数式思维和函数式编程

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

quicksort :: Ord a => [a] -> [a]  
quicksort [] = []  
quicksort (p:xs) =  
    (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs

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

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

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

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

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

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[i] < 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[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
  }
}

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

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

　　JAVA:

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

public class Quicksort {  
    private int[] numbers;

    public void sort(int[] values) {

    }
}

　　HASKELL:

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

quicksort :: Ord a => [a] -> [a]  

　　JAVA:

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

if (values.length == 0 || values == null) {  
    return;
}

　　HASKELL:

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

quicksort [] = []  

　　JAVA:

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

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

　　HASKELL:

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

No code. Nothing. Nada. That's good.  

　　JAVA:

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

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

    while (i <= j) {
        while (numbers[i] < 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[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
}

　　使用Haskell

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

quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)  

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

    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs

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

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

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

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

　　看看下面的这种Java代码？

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;

}

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

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

　　标注：

　　[1] Haskell from scratch courtesy of “Learn you a Haskell for Great Good!”

　　[2] This quicksort in Haskell that I am showing here is not in-place quicksort so it loses one of its properties, which is memory efficiency. The in-place version in Haskell would be more like:

import qualified Data.Vector.Generic as V  
import qualified Data.Vector.Generic.Mutable as M 

qsort :: (V.Vector v a, Ord a) => v a -> v a  
qsort = V.modify go where  
    go xs | M.length xs < 2 = return ()
          | otherwise = do
            p <- M.read xs (M.length xs `div` 2)
            j <- M.unstablePartition (< p) xs
            let (l, pr) = M.splitAt j xs 
            k <- M.unstablePartition (== p) pr
            go l; go $ M.drop k pr

　　Discussion here.

　　[3] This version of quicksort is simplified for illustration purposes. It’s always good looking at the source. Boldly go and read this piece of History (with a capital H) by C.A.R. Hoare, “Quicksort”.

　　[4] Taken from http://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html

　　[4] Will we consider uncontrolled state harmful the same way GOTO statement being considered harmful consolidated structured programming?

　　[5] This wiki has LOTS of architectural information about the amazing Glasgow Haskell Compiler, ghc. https://ghc.haskell.org/trac/ghc/wiki/Commentary

　　[6] A big question mark over time on functional programming languages has been the ability (or lack thereof) to effectively code User Interfaces. Don’t despair though! There’s this cool new thing called Functional Reactive Programming (FRP). Still performing babysteps, but there are already implementations out there. One that’s gaining lots of momentum is ReactJS/Om/ClojureScript web app stack. Guess that might be a good follow-up post

　　[7] See http://zeroturnaround.com/rebellabs/java-8-explained-applying-lambdas-to-java-collections/

　　英文原文：Programming (and thinking) the functional way 翻译：vaikan

标签： swap 代码 服务器 云计算

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。