Haskell语言实例分析

这篇“Haskell语言实例分析”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“Haskell语言实例分析”文章吧。

例子：

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

以上就是关于“Haskell语言实例分析”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注编程网精选频道。