Contents
Lập trình hướng hàm: Một phương pháp đơn giản và tiện ích
Lập trình hướng hàm là một phương pháp lập trình linh hoạt và mạnh mẽ. So với lập trình truyền thống như C, C++, Java, … lập trình hướng hàm giúp chúng ta dễ dàng xử lý các bài toán. Ví dụ, khi muốn nhân đôi từng phần tử trong một mảng, chúng ta sẽ viết mã như sau trong C:
int* arr;
for (int i = 0; i < n; ++i) {
arr[i] *= 2;
}
Tuy nhiên, trong Haskell, chúng ta chỉ cần viết như sau:
Bạn đang xem: Lập trình hàm!
map (*2) list
Dù cả hai mã trên thực hiện công việc tương tự nhau, nhưng cách tiếp cận trong Haskell mang lại sự tự nhiên và dễ hiểu hơn là chỉ cần mô tả yêu cầu: Nhân đôi từng phần tử. Trong khi ở phía C, chúng ta phải nghĩ là: Duyệt từng phần tử và nhân đôi chúng.
Haskell cung cấp nhiều tiện ích như danh sách, map, filter, scanl, scanr, zip, zipWith, foldl, foldr, … và những hàm này rất hữu ích trong việc xây dựng lại bài toán một cách súc tích chỉ dựa trên mô tả.
Bắt đầu với một ví dụ đơn giản: Dãy Fibonacci
Hãy bắt đầu với bài toán kinh điển về dãy Fibonacci. Với cách viết fib n = fib (n – 1) + fib (n – 2), mọi người đều biết cách này có hiệu suất rất tệ khi tính toán lại nhiều giá trị lặp đi lặp lại. Để khắc phục vấn đề này, ta sẽ sử dụng các biến đã tính toán trước đó:
fib = go (0, 1)
where go (a, _) 0 = a
go (a, b) n = go (b, a + b) (n - 1)
Nếu muốn tính n phần tử đầu tiên của dãy Fibonacci, ta có thể sử dụng cách trên và bổ sung thêm:
fibs = go (0, 1)
where go (a, b) n = if n == 0 then [] else a : go (b, a + b) (n - 1)
Với cách này, ta có thể tạo ra dãy Fibonacci vô hạn:
go (a, b) = a : go (b, a + b)
fibs = go (0, 1)
Mặc dù cách viết trên vẫn lưu lại các giá trị đã tính để tính toán bước tiếp theo, nhưng mô tả của các hàm đã trở nên rõ ràng hơn: Số tiếp theo bằng tổng hai số trước đó. Với cách mô tả này, hàm scanl rất hiệu quả trong bài toán này:
fibs = 0 : scanl (+) 1 fibs
Các phép toán trên ma trận
Trước tiên, chúng ta hãy viết phép nhân vô hướng của hai vector:
Với hai vector a = (a1, a2, …, an) và b = (b1, b2, …, bn), tích vô hướng <a, b> = a1b1 + a2b2 + … + anbn.
Xem thêm : Tìm Hiểu Về Các Khóa Học ReactJs Từ Cơ Bản Đến Nâng Cao
Với cách truyền thống, chúng ta sẽ viết mã như sau:
vecmul [] _ = 0
vecmul _ [] = 0
vecmul (x:xs) (y:ys) = x * y + vecmul xs ys
Nhưng chúng ta có thể viết gọn hơn sử dụng hàm zipWith và sum:
vecmul = sum . zipWith (*)
Với phép chuyển vị ma trận, chúng ta sẽ lấy phần tử đầu của từng hàng và tạo thành một hàng mới, sau đó làm tương tự với phần còn lại. Do đó, phép chuyển vị sẽ có mã như sau:
transpose ([]:_) = []
transpose x = [head a | a <- x] : transpose [tail a | a <- x]
Trong phép cộng hai ma trận, chúng ta cần cộng từng hàng với nhau. Do đó, chúng ta sẽ có hàm cộng hàng:
rowadd [] _ = []
rowadd _ [] = []
rowadd (x:xs) (y:ys) = (x + y) : rowadd xs ys
Và sau đó, thực hiện trên toàn ma trận:
matadd [] _ = []
matadd _ [] = []
matadd (x:xs) (y:ys) = rowadd x y : matadd xs ys
Một cách nghĩ khác cho phép cộng hai ma trận là sử dụng zipWith và (+):
matadd = zipWith (zipWith (+))
Tương tự, với phép nhân element-wise, chúng ta chỉ cần thay (+) thành (*):
matmul = zipWith (zipWith (*))
Tiếp theo là phép tích dot, trong đó ô i, j của ma trận kết quả sẽ là tích vô hướng của hàng i của ma trận đầu tiên với cột j của ma trận thứ hai. Với cách tính toán này, ta có công thức như sau:
dot x y = [[vecmul xr yc | yc <- transpose y] | xr <- x]
Với các phép tính toán đơn giản như vậy, ta có thể viết các hàm tính toán ma trận cơ bản một cách dễ dàng. Điều quan trọng là viết mã dựa trên mô tả của hàm, không phụ thuộc vào các bước tính toán chi tiết.
Một số thuật toán sắp xếp
Hãy viết các thuật toán sắp xếp bằng Haskell. Đầu tiên, hãy viết thuật toán Quick Sort. Theo mô tả, Quick Sort sẽ chia ra 3 giai đoạn:
- Chọn một phần tử bất kỳ làm pivot.
- Chia mảng thành hai phần, một phần chỉ chứa các phần tử nhỏ hơn pivot và phần còn lại chứa các phần tử lớn hơn hoặc bằng pivot.
- Sắp xếp các phần tử nhỏ hơn, pivot và các phần tử lớn hơn theo thứ tự.
Chúng ta có thể chọn pivot ở bất kỳ vị trí nào, vì vậy ta chọn vị trí đầu tiên của danh sách làm pivot, sau đó chúng ta chỉ cần lọc các phần tử nhỏ hơn hoặc lớn hơn pivot:
quickSort [] = []
quickSort (x:xs) = quickSort [a | a <- xs, a < x] ++ [x] ++ quickSort [a | a <- xs, a >= x]
Xem thêm : Học viết code cho người mới bắt đầu
Chúng ta hãy nhìn vào phương pháp mô tả thuật toán, không cần quan tâm đến cách mã thực hiện từng bước như thế nào. Và kết quả, chúng ta có một hàm được viết một cách gọn gàng.
Tiếp theo, hãy đến với Bubble Sort. Mô tả của nó như sau: Đổi chỗ hai phần tử kề nhau nếu chúng không đúng thứ tự.
bubbleSort = foldr go []
where go x [] = [x]
go x (y:ys) = min x y : go (max x y) ys
Tương tự, chúng ta có thể viết thuật toán Insertion Sort như sau: Đưa một phần tử vào đúng vị trí của nó trong dãy đã được sắp xếp.
insertionSort [] = []
insertionSort (x:xs) = go x (insertionSort xs)
where go x [] = []
go x (y:ys) = if x < y then x : y : ys else y : go x ys
Đến bài toán tìm đường đi ngắn nhất
Haskell là một ngôn ngữ lập trình tương tác tốt với toán học, vì vậy các giải thuật có tính toán học sẽ được viết một cách hiệu quả nhất. Chúng ta sẽ chọn phương pháp min-plus để giải quyết bài toán tìm đường đi ngắn nhất.
Trên tập số R∪{+∞}, ta định nghĩa a⊕b=min{a,b} và a⊗b=a+b, trong đó +∞ và 0 là phần tử trung hòa đối với ⊕ và ⊗.
Với một ma trận G trên một đồ thị gồm n đỉnh, ta có thể tính giá trị ⨁i=1nGibigoplus{i=1}^{n} G^{i}, trong đó Gk=⨂i=1kGG^k = bigotimes{i=1}^{k} GGk=i=1⨂kG.
Để tiện lợi, chúng ta chỉ xét trường hợp đồ thị trọng số không âm, với −1 tương ứng với dương vô cùng. Phép cộng và nhân trong min-plus được định nghĩa lại như sau:
oplus x y = if x == -1 || y == -1 then x + y + 1 else min x y
otimes x y = if x == -1 || y == -1 then -1 else x + y
Phép cộng hai ma trận sẽ có mã như sau:
matadd = zipWith (zipWith oplus)
Phép nhân ma trận sẽ có mã như sau:
matmul x y = [[vecmul a b | b <- transpose y] | a <- x]
Công cụ cuối cùng cần là phép tính 1 + x + … + x^n, và hàm foldl sẽ giúp chúng ta hoàn thành các mô tả còn lại:
calc x y = matadd (matmul x y) y
shortestPath g = foldl calc g (take (length g - 1) (repeat g))
Đó là một cách rất ngắn gọn để mô tả thuật toán tìm đường đi ngắn nhất.
Nguồn: https://laptrinhc.edu.vn
Danh mục: Tài liệu IT