解读 Erlang lists 源码

写在前面

  lists官方文档在此http://erlang.org/doc/man/lists.html,不知因为什么原因,官方文档中函数顺序和lists.erl源码里的顺序完全不一样。我是按照源码里的顺序来写的,目的是为了熟悉一下Erlang的编程风格和巩固基础语法。也不会所有函数都提到,挑下面一些来学习学习。

1. 属性说明
2. keyfind/3
3. suffix/2
4. seq/2, seq/3
5. sort/1 6. merge/1
7. concat/1
8. flatten/1, flatten/2
10. filter/2, map/2, filtermap/2
11. foldl/3, foldr/3
12. keydelete/3
13. keymap/3

1. 属性说明

  源文件里注明了 -compile({no_auto_import, [max/2]}).,这是一个预定义的模块属性【预定义的模块属性有以下四种:module,import,export,compile,vsn】。其中-compile(Options)是将Options添加到编译器选项表中,Options可以是单个原子,也可以是一个列表。这里的no_auto_import是说函数max/2不要自动从erlang模块里导出了,这是为了解决内置函数冲突。没听明白吧,ok,下面详细讲讲这个。至于模块属性,详见《Erlang程序设计》第二版,8.4节;有关compile选项,请移步http://erlang.org/doc/man/compile.html
  首先,什么叫自动导出:easy,自动导出就是你不加模块前缀就可以运行的函数。平常使用模块函数不都是模块名:函数名的吗。比如说我们要使用erlang模块里的max函数,一般都是erlang:max这样使用。so,顾名思义,如果max函数在erlang里是自动导出的,那我猜想我们可以直接在console里运行max函数了,而且注意,在console里不加模块名直接运行的max函数一定是定义在erlang这个模块里面的。猜想一下,如果含有其他模块【假定为erl】也定义了一个max函数,并且也自动导出了,那当你直接运行max函数时,erlang虚拟机是该运行erl里的max呢还是erlang里的max呢。
  好的,简单测试下,直接看代码得了:

root@kali:~/Desktop/erlcode# erl
Erlang/OTP 17 [erts-6.1] [source] [64-bit] [smp:4:4] [async-threads:10] [hipe] [kernel-poll:false]

Eshell V6.1  (abort with ^G)
1> erlang:max(1,2).
2
2> max(1,2).
2
3>

  现在,这个问题解决了,那我们来看看,为什么在lists模块里要阻止max/2自动导入呢。just think it,就和我上面说的一样,防止自动导出的核心是什么?不就是为了防止函数冲突吗?so,我猜想我们lists.erl模块里也有一个max/2函数,而且这个max/2函数的实现必须是和erlang模块里的实现是不同的。CTRL+F查找,果然不出所料:  

%% max(L) -> returns the maximum element of the list L

-spec max(List) -> Max when
      List :: [T,...],
      Max :: T,
      T :: term().

max([H|T]) -> max(T, H).

max([H|T], Max) when H > Max -> max(T, H);
max([_|T], Max)              -> max(T, Max);
max([],    Max)              -> Max.

  好了,到这里关于模块预定义属性就差不多了,以后遇到了再慢慢补上。

2. keyfind/3

  lists里的keyfind/3, keymember/3, keysearch/3, member/2, reverse/2都是通过内置函数实现的,源码都在erl_bif_types.erl这个文件里面。在keyfind/3的定义中,看到了pos_integer()这样一个变量类型,看来基础还是不行啊,没办法,大家有空都来这里补补基础吧。7 Types and Function Specifications

3. suffix/2

  之所以要介绍suffix,是想借suffix来简单介绍一下Erlang里的布尔表达式和所谓的短路布尔表达式。函数定义和实现如下,检查Suffix是否是List的后缀。实现就用了两行,真是精湛啊,突然发现其实很多操作不用循环也能很清楚的表达了。
  这里的 andalso 叫做短路布尔表达式,其含义是指 Expr1 andalso Expr2 这样一个表达式只有在Expr1为真的情况下才会执行Expr2。同样可以理解一下orelse这个短路布尔表达式。而普通的布尔表达式和其他语言里一样的,not, and, or, xor。

%% suffix(Suffix, List) -> (true | false)

-spec suffix(List1, List2) -> boolean() when
      List1 :: [T],
      List2 :: [T],
      T :: term().

suffix(Suffix, List) ->
    Delta = length(List) - length(Suffix),
    Delta >= 0 andalso nthtail(Delta, List) =:= Suffix.

4. seq/2

  seq/2是一个高级接口,调用了一个三参数的接口seq_loop(N, X, L),如下,其中N=Last-First+1,是需要生成的长度,X=Last,是最后一个元素的值,L是一个空列表[],将结果保存到第三个参数L中,最后再返回它。而生成这个列表的方法确实很高效,要么一次生成4个数,要么一次生成2个数,要么生成一个数或者直接返回结果。而实际应用中,大多数情况应该都是一次生成4个数,然后可能会调用1到2次一次生成2个数,最后要么直接返回结果,要么就再生成1个数后再返回结果。极为高效!我又想起了Python里相似的range函数,过两天看看Python里是怎么实现的。

-spec seq(From, To) -> Seq when
      From :: integer(),
      To :: integer(),
      Seq :: [integer()].

seq(First, Last)
    when is_integer(First), is_integer(Last), First-1 =< Last ->
    seq_loop(Last-First+1, Last, []).

seq_loop(N, X, L) when N >= 4 ->
     seq_loop(N-4, X-4, [X-3,X-2,X-1,X|L]);
seq_loop(N, X, L) when N >= 2 ->
     seq_loop(N-2, X-2, [X-1,X|L]);
seq_loop(1, X, L) ->
     [X|L];
seq_loop(0, _, L) ->
     L.

5. sort/1

  Link:

6. merge/1

  Link:

7. concat/1

  concat函数本身的意图是把参数组合成一个项式,特别需要注意的是,当这个项式是可打印的时候,就打印其字符串形式的结果,当该项式是不可打印的时候,就以把它组合成一个list形式。我们先看下面的例子:

  

root@kali:~/Desktop/erlcode/lists# erl
Erlang/OTP 17 [erts-6.1] [source] [64-bit] [smp:4:4] [async-threads:10] [hipe] [kernel-poll:false]

Eshell V6.1  (abort with ^G)
1> lists:concat([1,2,3]).
"123"
2> lists:concat([1,2,3,a,b,c]).
"123abc"
3> lists:concat([1,2,3,[a,b,c]]).
[49,50,51,a,b,c]
4> lists:concat([1,2,3,[1,2,3]]).
[49,50,51,1,2,3]
5> lists:concat([1,2,3,a,b,c,[1,2,3]]).
[49,50,51,97,98,99,1,2,3]
6> lists:concat([1,2,3,a,b,c,[1,2,[a,b,c],3]]).
[49,50,51,97,98,99,1,2,[a,b,c],3]
7> lists:concat([1,2,3,a,b,c,[1,2,[a,b,c],3],d,e,f]).
[49,50,51,97,98,99,1,2,[a,b,c],3,100,101,102]

  从例子1、2可以看出,若参数是一个无嵌套的term组成的list,则会返回由这些term组成的一个字符串;若参数是含有嵌套的list,则会把最外层term打印成其在ASCII中的下标,而嵌套的会保持原形。我想这个函数一般都会用在无嵌套的情况吧。下面是源码。

%% concat(L) concatenate the list representation of the elements
%%  in L - the elements in L can be atoms, numbers of strings.
%%  Returns a list of characters.

-spec concat(Things) -> string() when
      Things :: [Thing],
      Thing :: atom() | integer() | float() | string().

concat(List) ->
    flatmap(fun thing_to_list/1, List).

thing_to_list(X) when is_integer(X) -> integer_to_list(X);
thing_to_list(X) when is_float(X)   -> float_to_list(X);
thing_to_list(X) when is_atom(X)    -> atom_to_list(X);
thing_to_list(X) when is_list(X)    -> X.       %Assumed to be a string

-spec flatmap(Fun, List1) -> List2 when
      Fun :: fun((A) -> [B]),
      List1 :: [A],
      List2 :: [B],
      A :: term(),
      B :: term().

flatmap(F, [Hd|Tail]) ->
    F(Hd) ++ flatmap(F, Tail);
flatmap(F, []) when is_function(F, 1) -> [].

8. flatten/1, flatten/2

  flatten/1 和 flatten/2 都是把一个有嵌套的list返回成一个无嵌套的list的函数,其中flatten/2允许在flatten/1的结果后再append一个list,而且不管这个list的形式。其实一会儿可以在源码里看见,flatten/1和flatten/2的唯一区别是flatten/1相当于flatten/2的第二个参数是一个空list。

  

-spec flatten(DeepList) -> List when
      DeepList :: [term() | DeepList],
      List :: [term()].

flatten(List) when is_list(List) ->
    do_flatten(List, []).

-spec flatten(DeepList, Tail) -> List when
      DeepList :: [term() | DeepList],
      Tail :: [term()],
      List :: [term()].

flatten(List, Tail) when is_list(List), is_list(Tail) ->
    do_flatten(List, Tail).

do_flatten([H|T], Tail) when is_list(H) ->
    do_flatten(H, do_flatten(T, Tail));
do_flatten([H|T], Tail) ->
    [H|do_flatten(T, Tail)];
do_flatten([], Tail) ->
    Tail.

10. filter/2, map/2, filtermap/2

  先看看函数参数,filter函数是对List1里的每个term都应用一次Pred函数,然后将能使Pred函数返回true的元素按序构成一个新的列表返回。map函数是对List1里对每个term都应用一次Fun函数,然后将Fun函数在每个元素上都返回值按顺序构造成返回值。顾名思义,filtermap函数就是这两个函数的结合,即先filter,再做map操作。下面是源码,有时候发现,如果看document看烦了,可以选择性地看看源码,也许比看document管用。

-spec map(Fun, List1) -> List2 when
      Fun :: fun((A) -> B),
      List1 :: [A],
      List2 :: [B],
      A :: term(),
      B :: term().

map(F, [H|T]) ->
    [F(H)|map(F, T)];
map(F, []) when is_function(F, 1) -> [].

-spec filter(Pred, List1) -> List2 when
      Pred :: fun((Elem :: T) -> boolean()),
      List1 :: [T],
      List2 :: [T],
      T :: term().

filter(Pred, List) when is_function(Pred, 1) ->
    [ E || E <- List, Pred(E) ].   

-spec filtermap(Fun, List1) -> List2 when
      Fun :: fun((Elem) -> boolean() | {'true', Value}),
      List1 :: [Elem],
      List2 :: [Elem | Value],
      Elem :: term(),
      Value :: term().

filtermap(F, [Hd|Tail]) ->
    case F(Hd) of
  true ->
      [Hd|filtermap(F, Tail)];
  {true,Val} ->
      [Val|filtermap(F, Tail)];
  false ->
      filtermap(F, Tail)
    end;
filtermap(F, []) when is_function(F, 1) -> [].

扫一扫

2014-10-31-erlang-lists-source-code.md