2014/2/20

erlang basics - list comprehension

list comprehension 是 erlang 裡面很重要的一項功能，它能有效縮減程式碼，讓程式更容易理解。quick sort wiki 收集了很多語言的實作，erlang 很神奇地以三行程式碼大勝。

語法

以下是數學在描述一個集合時，可列出屬於 N 的自然數集合，且大於 0 的所有 x，也就是所有正整數的集合。

{x | x∈N, x>0}

在 erlang 中，可用 list comprehension 語法，描述出類似的概念。 <- 是生成器，|| 的右邊，除了生成器之外，其他的都是約束條件(filter)。

[X || X <- ListOfIntegers, X>0]

以下是 list comprehension 的一般形式，Qualifier 可以是生成器 generator 或是 filter

[X || Qualifier1, Qualifier2, ...]
generator: X <- L
filter: 元素的條件判斷

範例

以下可得到，所有正偶數平方的 list

[math:pow(X,2) || X <- ListOfIntegers, X>0, X rem 2 ==0]

以下可取得面積大於等於 10 的矩形 list。

[{area, H * W} || {rectangle, H, W} <- Shape, H*W>=10 ]

lists:map 與 list comprehension

list comprehension 可用來快速建立一組匹配的 list。

要得到 L 裡面所有元素的兩倍的 list，可以用 lists:map ，也可以直接用 list comprehension 取代處理。

(erlangotp@yaoclNB)5> L=[1,2,3,4,5].
[1,2,3,4,5]
(erlangotp@yaoclNB)6> lists:map(fun(X) -> 2*X end, L).
[2,4,6,8,10]
(erlangotp@yaoclNB)7> [2*X || X <- L].
[2,4,6,8,10]
map(F,L) -> [F(X) || X <- L]

tuple 元素的處理

當 list 裡的元素是 tuple 時，同樣也能使用 list comprehension，來處理。

(erlangotp@yaoclNB)8> Buy = [{oranges, 4}, {newspaper, 1}, {apples, 10}, {pears, 6}, {milk, 5}].
[{oranges,4},{newspaper,1},{apples,10},{pears,6},{milk,5}]
(erlangotp@yaoclNB)9> [{Name, 2*Number} || {Name, Number} <- Buy].
[{oranges,8},{newspaper,2},{apples,20},{pears,12},{milk,10}]

quick sort

quick sort wiki 收集了很多語言的實作，erlang 很神奇地以三行程式碼大勝。

qsort([]) -> [];
qsort([Pivot|T]) ->
    qsort([X || X <-T, X<Pivot]) ++ [Pivot] ++ qsort([X || X <-T, X>=Pivot]).

測試

(erlangotp@yaoclNB)3> L=[23,6,2,9,120,15].
[23,6,2,9,120,15]
(erlangotp@yaoclNB)4> test:qsort(L).
[2,6,9,15,23,120]

運作過程

  1. L = [23,6,2,9,120,15] 符合第二個子句，L 會被切割成 [Pivot|T]，所以 Pivot = 23, T = [6,2,9,120,15]

  2. qsort([X || X <-T, X<Pivot]) 就等於 qsort([X || X <-[6,2,9,120,15], X<23])，也就是把 T 裡面所有小於 23 的元素都取出來產生一個新的 list，然後再放進 qsort 再處理一次，也就是 qsort([6,2,9,15])

  3. qsort([X || X <-T, X>=Pivot]) 就等於 qsort([X || X <-[6,2,9,120,15], X>=23])，也就是把 T 裡面所有大於等於 23 的元素都取出來產生一個新的 list，然後再放進 qsort 再處理一次，也就是 qsort([120])

  4. 第一次處理後的結果為 qsort([6,2,9,15]) ++ [23] ++ qsort([120])

  5. 然後再處理 qsort([6,2,9,15])，同樣符合第二個子句，Pivot = 6，T = [2,9,15]

  6. 結果為 qsort([2]) ++ [6] ++ qsort([9,15])

  7. qsort([2]) 同樣符合第二個子句，Pivot = 2，T = []，結果為 qsort([]) ++ [2] ++ qsort([])

  8. qsort([]) 符合第一個子句，結果為 []

因此整個運作的過程可寫成
qsort([23,6,2,9,120,15])
= qsort([6,2,9,15]) ++ [23] ++ qsort([120])
= qsort([2]) ++ [6] ++ qsort([9,15]) ++ [23] ++ [] + [120] + []
= [] + [2] + [] ++ [6] ++ [] ++ [9] ++ qsort([15]) ++ [23] ++ [] ++ [120] ++ []
= [] ++ [2] ++ [] ++ [6] ++ [] ++ [9] ++ [] ++ [15] ++ [] ++ [23] ++ [] ++ [120] ++ []
= [2,6,9,15,23,120]

畢氏定理

畢氏定理：直角三角形的邊長 {A,B,C}，必須滿足兩股的平方和要等於斜邊的平方這個條件，A^2 + B^2 = C^2。

lists:seq(1,N) 可取得 1 到 N 所有正整數的 list。

pythag(N) 可以取得小於N，並滿足畢氏定理的所有正整數 {A,B,C} 的集合 list。

pythag(N) ->
    [ {A,B,C} ||
      A <- lists:seq(1,N),
      B <- lists:seq(1,N),
      C <- lists:seq(1,N),
      A+B+C =< N,
      A*A+B*B =:= C*C
    ].

測試

(erlangotp@yaoclNB)9> test:pythag(16).
[{3,4,5},{4,3,5}]
(erlangotp@yaoclNB)10> test:pythag(30).
[{3,4,5},{4,3,5},{5,12,13},{6,8,10},{8,6,10},{12,5,13}]
(erlangotp@yaoclNB)11> test:pythag(40).
[{3,4,5},
 {4,3,5},
 {5,12,13},
 {6,8,10},
 {8,6,10},
 {8,15,17},
 {9,12,15},
 {12,5,13},
 {12,9,15},
 {15,8,17}]

anagram 回文

perms 可取得一個英文字串，能找到的字母的所有排列組合。

perms([]) ->
    [[]];
perms(L) ->
    [[H|T] || H <- L, T <- perms(L--[H])].

測試

(erlangotp@yaoclNB)12> test:perms("123").
["123","132","213","231","312","321"]
(erlangotp@yaoclNB)13> test:perms("cats").
["cats","cast","ctas","ctsa","csat","csta","acts","acst",
 "atcs","atsc","asct","astc","tcas","tcsa","tacs","tasc",
 "tsca","tsac","scat","scta","sact","satc","stca","stac"]

運作過程

  1. perms("123") 因為字串就等同於 list，所以滿足第二個子句，有三種狀況
    1.1 H 為 "1"，T 為 perms("23")
    1.2 H 為 "2", T 為 perms("13")
    1.3 H 為 "3", T 為 perms("12")

  2. perms("23") 滿足第二個子句，有兩種狀況
    2.1 H 為 "2", T 為 perms("3")
    2.2 H 為 "3", T 為 perms("2")

  3. perms("3") 滿足第二個子句，有一種狀況
    3.1 H 為 "3", T 為 perms(""), T 就滿足第一個子句，結果為 [[]]，因此 [H|T] 就是 ["3"]

  4. 回到 2.1，H 為 "2", T 為 "3"，因此 [H|T] 就是 ["23"]，而2.2 的結果為 ["32"]

  5. 回到 1.1，H 為 "1"，T 為 "23" 或 "32"，結果為 ["123", "132"]

  6. 加上 1.2 與 1.3 的結果為 ["123","132","213","231","312","321"]

以自然順序建立 list

建立 list 最有效率的方式，就是把新的元素加入到 list 的頭部，我們常會看到有這樣的程式碼，這會走入 list，取出 list 的頭部，然計算得到 H1，最後將 H1 加入 Result 中，當輸入的資料耗盡，會滿足第二個條件，此函數會輸出 Result 結果。

some_function([H|T], ..., Result, ...) ->
    H1 = ... H ...,
    some_function(T, ..., [H1|Result], ...);
some_function([], ..., Result, ...) ->
    {..., Result, ...}.

注意的事項

  1. 增加元素一定要放在 list 的頭部
  2. 從頭部取出元素，處理後加入到另一個 list 的頭部，這會讓 Result list 跟輸入的 list 的元素順序相反。
  3. 如果順序一定要一樣，就呼叫 lists:reverse/1 進行反轉
  4. 反轉 list 要呼叫 lists:reverse/1，絕對不能用 List ++ [H]，這會造成效能問題

從一個函數取得兩個 list

如果要寫一個函數，將 list 分為 奇數跟偶數 兩個 list，直觀的作法，就直接用 list comprehension 處理兩次。

odds_and_evens(L) ->
    Odds = [X || X<-L, (X rem 2) =:= 1],
    Evens = [X || X<-L, (X rem 2) =:= 0],
    {Odds, Evens}.

但 traverse list 兩次，並不是個好方法，應該改為 traverse 一次，然後根據 X rem 2 的 結果，將 H 放入不同的 result list 中，最後再以 lists:reverse 把順序反轉。

odds_and_evens_acc(L) ->
    odds_and_evens_acc(L, [], []).

odds_and_evens_acc([H|T], Odds, Evens) ->
    case (H rem 2) of
        1 -> odds_and_evens_acc( T, [H|Odds], Evens);
        0 -> odds_and_evens_acc( T, Odds, [H|Evens])
    end;

odds_and_evens_acc([], Odds, Evens) ->
    {lists:reverse(Odds), lists:reverse(Evens)}.

測試

(erlangotp@yaoclNB)1> test:odds_and_evens([1,2,3,4,5,6,7,8]).
{[1,3,5,7],[2,4,6,8]}
(erlangotp@yaoclNB)2> test:odds_and_evens_acc([1,2,3,4,5,6,7,8]).
{[1,3,5,7],[2,4,6,8]}

結語

當我們需要滿足某個條件的集合時，我們要先思考到在數學的集合表示式，然後再想到，以 list comprehension 來將這個集合實作出來。

參考

Erlang and OTP in Action
Programming Erlang: Software for a Concurrent World

張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)