函数式思维和函数式编程

oschina
 oschina
发布于 2014年09月05日
收藏 96

作为一个对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;
  }
}

哇塞。到处都是ij,这是干嘛呢?为什么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作为每次迭代的两个队列。等一下!我们可以使用标准的headtail函数来获取第一个值作为基点数据。这样我们可以它的两个部分进行递归调用!

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

非常好,这里我声明了lessergreater两个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 ]

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处,尊重他人劳动共创开源社区。
转载请注明:文章转载自 OSCHINA 社区 [http://www.oschina.net]
本文标题:函数式思维和函数式编程
加载中

最新评论(24

ApacheCN_飞龙
ApacheCN_飞龙
这篇文章说明了java可以写原地或者非原地的快排,而haskell只能写原地快排。= =
水山清风
水山清风
在这里为作者平反一下,lisp,haskell这些语言跟java,ruby这些语言的关系有点像哲学跟数学的关系。
ruby的作者在书中就说说他大量参考了lisp等语言的特性,而且,java的自动回收垃圾功能早在lisp那里就有了,lisp可以说是很多语言的始祖,而且在某些领域还是不可替代的语言。
至于haskell,很多函数式的语言都是参照了lisp和haskell而创作出来的,例如scala,函数式语言在分布式系统中有不可替代的优势,那就是为什么spark用scala编写的原因,大家也可以搜搜akka的简介(貌似说得也很吊)。
另外,楼上说i,j看得不错的试试把
List(1,2,3,4,5,6,7,8,9,0)输出成"88,99,00"试试,在scala里面,
myList.take(7).map(_.toString * 2).mkString(",")
即可
说比较语言没有用的,个人觉得,比较语言是很必要的,只有充分比较各种语言在各种情况下展现出来的各种优势和劣势,才能确定一个系统用什么语言适合,例如spark用ruby写估计就没有那么好了,scala的不变对象在这里帮了大忙,但是你要用scala的快速开发一个原形估计又会遇到很多波折,这是充分比较了各种语言的优点和缺点才得出来的结果。
说“个别经过精心挑选优化的示例不足以证明某种语言的优劣特性”的,不是有个叫控制变量法么,这里控制了示例的输出不变,研究各种语言实现的优劣。说不定改变了输出之后的某些示例java比haskell优秀很多,但你总不可以做个全面的比较吧,这是博客啊,不是一本书。。。
哆啦比猫
哆啦比猫
试图将方程思想带入计算机世界的都是扯淡
********
********
垃圾语言
赵云30
赵云30
我最鄙视haskell lisp程序员,他们喜欢写不到100行的程序来吹自己多么优秀,就好比小学生和大学生说自己乘法表背的滚瓜烂熟。
Helo
Helo
真心看不懂 啊啊!!
我也叫龙哥
我也叫龙哥
异端!恶魔!正义的力量会轻而易举的打到它!! ;-)
做个坏人
做个坏人
优雅个毛,哪里优雅了 ?找出一堆不常用的特有的功能显摆一下就是优雅 ?代码优雅体现在大家一看就懂,而不是彰显独特。
stnick
stnick
C++ 本身 template 也带有函数式的影子, 写起来也很有趣, 在旧标准中使用类重载 () 符号,模仿 lambda 也是比较 trick 的方式, 如果觉得自己的代码中使用该方式比使用传统的方式开发在代码上语义更清晰, 也是值得尝试的.
stnick
stnick
作者目的是想推荐大家使用函数式的语法开发, 在某些场景下可以清晰表达功能的含义, 提高开发效率, 同时代码维护方便, 评论里扯到语言争论就没意义了, 和文章的论点毫无关系.
Java 新版 以及 C++11 支持 lambda 也是在改善语言的开发效率, 既然已经支持了, 作者当然会根据自己工作经验推荐大家在合适的地方使用.
Python web 开发里封装的框架也大量使用了装饰器, 那本身就是一种函数式编程方式, 不说Java程序员, 如果有Python 开发经验的,只知道在框架里堆代码,对内部实现机制不了解, 可以先看看. 比如 Python Tornado 框架源码
返回顶部
顶部