This page is READ-ONLY. It is generated from the old site.
All timestamps are relative to 2013 (when this page is generated).
If you are looking for TeX support, please go to VietTUG.org

Erlang map, filter, fold functions

all funtional programming languages support these functions.
Added by bronzeboyvn almost 2 years ago  »  Votes: 1/1

Một chương trình được viết bằng ngôn ngữ lập trình hàm có vai trò nhận input, xử lý và trả ra output. Như vậy viết một chương trình chẳng khác nào xây dựng một ánh xạ:

f: X     -> Y
   input |-> output = f(input)

Những bạn đã trải qua khóa Giải tích hàm đều biết rằng input không chỉ có thể là giá trị thông thường mà có thể là một hàm số. Chẳng hạn, xây dựng một ánh xạ G, với input là một hàm f(x), output sẽ là tích phân của hàm f(x) trên miền U (cho trước). Khi lập trình hàm (tức là xây dựng một ánh xạ nào đó) bạn cũng sẽ gặp những vấn đề tương tự.

1. map

Ví dụ, ta có 2 hàm: incr(x), decr(x).

increment                           decrement
incr: N -> N                        decr: N -> N
      n |-> n+1                           n |-> n-1

% Erlang source code
-module(hhfuns).

incr(X) -> X + 1.
decr(X) -> X - 1.

map(_, []) -> [];
map(F, [H|T]) -> [F(H)|map(F,T)].

Ta xây dựng một ánh xạ map sao cho: map(incr) sẽ tăng các số trong tập hợp U lên một đơn vị , map(decr) sẽ giảm các số trong tập hợp U đi một đơn vị.
map: f |-> output={f(u) | u thuộc U}, với U cho trước.

Sau khi biên dịch module hhfuns, ta có thể chạy thử trong erlang shell:
> U = [1,2,3,4,5].
[1,2,3,4,5]
> hhfuns:map(fun hhfuns:incr/1, U).
[2,3,4,5,6]
> hhfuns:map(fun hhfuns:decr/1, U).
[0,1,2,3,4]
> hhfuns:map(fun(X) -> math:pow(2,X) end, U).
[2.0,4.0,8.0,16.0,32.0]

Dòng cuối cùng trả về những lũy thừa bậc u của 2, với u thuộc list U = [1, 2, 3, 4, 5].

2. filter

là một ánh xạ nhận tham số là hàm f, f(x) chỉ có giá trị true/false, với mọi x thuộc miền U (U cho trước). Và filter được định nghĩa như sau:

filter: f |-> output={u | f(u) = true, u thuộc U}
% Erlang source code (module hhfuns)
filter(Pred, L) -> lists:reverse(filter(Pred, L,[])).

filter(_, [], Acc) -> Acc;
filter(Pred, [H|T], Acc) ->
  case Pred(H) of
    true  -> filter(Pred, T, [H|Acc]);
    false -> filter(Pred, T, Acc)
  end.

Sau khi biên dịch module hhfuns, ta có thể chạy thử trong erlang shell:

> hhfuns:filter(fun(X) -> X rem 2 == 0 end, lists:seq(1,10)).
[2,4,6,8,10]

Câu lệnh trên lọc ra các số chẵn từ list các số tự nhiên từ 1 tới 10.

3. fold

%Erlang source code (module hhfuns)
fold(_, Start, []) -> Start;
fold(F, Start, [H|T]) -> fold(F, F(H,Start), T).

nhận tham số là hàm f, f(u) sẽ quyết định cất u vào accumulator hay không. Ví dụ tính tổng, tích của các phần từ u của list U, tìm giá trị lớn nhất, nhỏ nhất trong list U. Trường hợp tính tổng, tích thì mỗi lần dợt qua 1 phần tử u, ta cộng dồn, nhân dồn giá trị vào accumulator. Trường hợp tìm giá trị lớn nhất, thì mỗi lần dợt qua phần tử u, nếu u > accumulator thì ta giữ lại u.
Sau khi biên dịch module hhfuns, ta có thể chạy thử trong erlang shell:
> [H|T] = [1,7,3,5,9,0,2,3].
[1,7,3,5,9,0,2,3]
> hhfuns:fold(fun(A,Acc) when A > Acc -> A; (_,Acc) -> Acc end, H, T).
9
> hhfuns:fold(fun(A,Acc) when A < Acc -> A; (_,Acc) -> B end, H, T).
0
> hhfuns:fold(fun(A,Acc) -> A + Acc end, H, T).
30
>hhfuns:foldl(fun(X, Acc) -> X * Acc end, H, T).
0

Conclusion

Khi dùng ngôn ngữ lập trình hàm để viết chương trình, việc sử dụng map, filter, fold là thường xuyên. Tôi nghĩ ngôn ngữ lập trình hàm khác cũng vậy, có thể tên hàm nó khác nhưng ở đó vẫn cần những hàm có vai trò tương tự như bộ 3 map, filter, fold của Erlang. Bài viết đào sâu bản chất của map, filter, fold, còn trên thực tế khi lập trình ta không viết lại từ đầu những hàm này, mà sử dụng các hàm lists:map/2 , lists:filter/2, lists:foldl/3 and lists:foldr/3 từ thư viện chuẩn của Erlang.

Người viết có tham khảo trang learnyousomeerlang.com khi viết bài.


Comments

Added by icy almost 2 years ago

hhfuns:map(fun hhfuns:incr/1, U) có thể hiểu theo nghĩa toán học là: lấy tác động hàm f (ở đây f -> incr/1) lên tập hợp U, tức là f(U). Định nghĩa của nó (toán học) là f(U) = {f(u) : u \in U}. Luôn có thể coi f(U) là kết quả khi tác động f trên U, hoặc là kết quả khi tác động U trên f. Như vậy, mapmột hàm lấy kết quả của tác động :) Điều này có thể gây bối rối cho dân học toán, bởi f(U) rất tự nhiên; nhưng do trong lập trình, thì phải xây dựng thêm một ánh xạ map thì máy mới hiểu :D

Phần còn lại filter thì theo mình, hiểu theo kiểu ánh xạ ngược sẽ thú vị hơn :) Filter(f,U) chính là f^{-1}({TRUE}). Như vậy, bài toán tổng quát chính là đi tìm ánh xạ ngược; trong một số trường hợp điều này sẽ tránh phải sử dụng vòng lặp (hoặc phép tìm kiếm) và tối ưu hóa mã :P