Erlang Erlang 入门-递归和模式匹配

DavidAlphaFox · 发布于 2017年09月23日 · 469 次阅读
84794b

两大基本概念

学过计算机编程的读者们都会知道,程序是由算法和数据组成的,近一步说是控制结构和数据体。拿C语言举个例子来说,控制结构有if语句,for语句和case语句等,就是这些控制结构和逻辑判断组成了一个又一个算法。在Erlang这个函数语言中,只要理解递归和模式匹配这两个概念,就完全可以组合出上面的控制结构。本文将重点介绍这两大概念,并用实际例子向读者说明。

递归

我们都知道阶乘这个算法,下面先用C实现一遍这个算法:

int factorial(int a){
   if(a > 0) {
     return a * factorial( a - 1);
   } else {
     return 1;
   }
} 

有经验的读者会发现这个例子会导致堆栈溢出,int上溢出等问题,在此我们不深究这些问题。读者可以很容易发现这个是一个递归算法,那么现在就用Erlang来编写下这个例子:

-module(ex1).
-export([factorial/1]).
factorial(0) -> 1;
factorial(A) -> A * factorial(A -1). 

在Erlang中这种递归一样存在堆栈溢出的问题,读者都知道C语言可以通过使用for循环和一个中间变量来解决堆栈溢出。那么对于变量不可变的Erlang应当怎么做呢?让我们重新修改下上面阶乘这个例子:

-module(ex2).
-export([factorial/1]).
factorial(N) -> factorial(N,1).
factorial(0,Acc) -> Acc;
factorial(N,Acc) when N > 0 -> factorial(N-1,N*Acc).

看起来似乎和前面的那个ex1版本没什么区别,但是其中的差异很大。ex2版本的factorial被称为尾递归,Erlang编译器在编译的过程中,会自动将代码转化成循环形式。同时尾递归也是Erlang中用来保持进程存活,进行列表(数组)遍历的重要工具,在后面教程中,会不断深入介绍相关知识。

模式匹配

在上面ex1中的例子,可以看到factorial(0)这种写法,这种写法就是Erlang的模式匹配。Erlang会将传入函数的参数和函数的参数列表进行匹配。

就ex1的例子来说,当我们传入参数3,Erlang会按照factorial函数的定义的顺序,从上到下逐条匹配。第一次执行的时候,参数3和factorial(0)并不匹配,直接进入第二条和factorial(A)进行匹配,Erlang会自动的将参数3绑定到A上。并且值得注意的是,Erlang中大写字母开头的变量一旦绑定了在作用范围内就不可以再次绑定。当执行到最后一次的时候,参数已经变成0,直接和factorial(0)匹配,Erlang对于两个常量并不会进行绑定。

为了理解模式匹配,我们需要理解Erlang的变量。

变量

Erlang的变量比较特殊,Erlang的变量是不可变的。Erlang的变量一旦绑定了特定的值之后,再作用范围之内就不能再次进行绑定,因此Erlang的变量是被认为不可变的。Erlang中变量的语法非常简单,任何以大写字母开头的单词,大写字母开头后续是字母和数字混合的标识或以下划线开头的标识。例如说,Erlang,JID1,UserA和User1都是合法的变量标识。

我们可以将Erlang的变量想象成一个盒子,这个盒子一开始是空的,但是一旦放入东西后,就不能放入别的东西了,并且当我们取出这个东西的时候,盒子会自动生成一个一模一样的东西。 如图所示,绑定变量的时候就相当于我们把东西放入盒子。 如图所示,当我们取出变量的时候,我们得到一个东西和一个仍装有东西的盒子。因此,我们依然不能将别的东西继续放入这个盒子了。

Erlang中还有一个比较特殊的变量 “_”,我们可以把它认为是个黑洞,它无需遵循Erlang变量不变的特性,任何放入 “_” 中的值都无法再次取出使用。“_” 虽然在作为变量使用时,虽然没有什么太大的意义,但是当进行模式匹配的时候它就非常有意义了。

什么是模式匹配

那么对于“=”这个操作符号就很好理解了,“=”先检查左侧和右侧两个值,如果左侧是一个未绑定的变量,右侧是一个常量,就把常量放入变量这个盒子里面;如果左侧是一个绑定的变量,右侧是一个绑定变量,就都把盒子打开拿出里面的东西进行比较;如果左侧是绑定的变量,右侧是常量,那么就把盒子打开取出东西进行比较。

从这里我们就可以看出,模式匹配就是尝试比较装有东西的盒子里面的东西和外面的东西比较,或者比较两个装有东西的盒子中的两个东西是否一样。

对于上面提到的黑洞‘“_”,在进行模式匹配的时候,它会匹配任何内容,并且在匹配完成后立刻忘记,这么做就可以让我们在写Erlang代码的时候忽略那些我们不行关心的变量。尤其是Erlang的函数有多个参数需要匹配或匹配元组的时候。

读者这时也许会问到,上面ex1的例子中函数并没有使用“=”的地方,那它怎么进行的模式匹配呢?这是因为Erlang编译器默认替我们做了一下,将函数定义的参数和函数调用时候传入的参数进行了下绑定操作。

共收到 0 条回复
84794b DavidAlphaFox Erlang 入门-模块和进程 中提及了此贴 12月26日 20:29
需要 登录/注册 后方可回复, 如果你还没有账号请点击这里 注册