Đệ quy và Loop trong Haskell
TIL
497
@100daysTIL
42
Haskell
13
White

Huy Trần viết ngày 13/02/2018

#Day011

Haskell không có vòng lặp (for, while,...) nên cách duy nhất để thực hiện các thao tác có tính chất lặp là sử dụng đệ quy.

Ví dụ, để implement hàm nhân hai số n * m, ta thấy bản chất của phép nhân là phép cộng số n, thực hiện m lần.

$$
n \times m = \sum_{i=1}^{m} n = n + n + \dots + n
$$

Do you see what I see here? A sword! :trollface:

Như vậy, nếu chuyển thành dạng đệ quy, ta cần một hàm nhận vào một số n và một biến đếm m, rồi trừ dần số m này đi, và với các thuật toán đệ quy, ta có thể dễ dàng implement bằng pattern matching:

multiply :: Int -> Int -> Int
multiply _ 0 = 0
multiply n m = ( multiply n (m-1) ) + n

Các trường hợp làm việc với số đa phần rất dễ hình dung và viết đệ quy. Tuy nhiên đối với các dạng dữ liệu khác, ví dụ List, thì cần phải chú ý thêm.

Ví dụ ta viết một hàm len để tính độ dài của một List, việc cần làm vẫn là đệ quy, nhưng ở mỗi bước, chún ta không cần dùng biến đếm, mà thay vào đó là cắt bớt phần tử của List đó.

len :: [a] -> Int
len []     = 0
len (x:xs) = 1 + len xs

Cách viết (x:xs) dùng để lấy ra phần tử đầu của List, là x, và xs là một List khác chứa các phần tử còn lại. Ở đây có nghĩa là, sau mỗi bước đệ quy, ta bỏ bớt phần tử đầu của List đó rồi đưa phần còn lại vào gọi tiếp, cho đến khi chỉ còn List rỗng.

Bản thân Haskell có sẵn rất nhiều hàm để phục vụ việc xử lý mang tính chất lặp, ví dụ như map, iterate, forever,... hoặc xem thêm Control.Monad.Loops (chưa tìm hiểu sâu về Monad nên cũng chả rõ vì sao lại có cái này, và dùng trong trường hợp nào, để ít hôm nữa xong Monad rồi thì quay lại vụ này :D).

huytd 14-02-2018

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Huy Trần

100 bài viết.
1440 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
145 43
Tại sao phải viết blog kĩ thuật? Có rất nhiều bài viết trên mạng nói về vấn đề tại sao một lập trình viên nên thường xuyên viết các bài blog kĩ thu...
Huy Trần viết hơn 2 năm trước
145 43
White
143 37
(Ảnh) Tiếp tục sêri (Link) lần này, chúng ta sẽ cùng tìm hiểu và mô phỏng lại một chức năng mà mọi người đang bắt đầu sử dụng hằng ngày, đó là chứ...
Huy Trần viết hơn 1 năm trước
143 37
White
96 16
Phần 1: Tự truyện Tui và Toán đã từng là hai kẻ thù không đội trời chung trong suốt hơn mười lăm năm ròng rã. Ngay từ ánh nhìn đầu tiên đã ghét nh...
Huy Trần viết gần 2 năm trước
96 16
Bài viết liên quan
White
2 0
D3.js Biểu diễn dữ liệu dạng tree bằng việc trải nó ra trên bản đồ Series Today I Learn trong vòng 100 ngày thử thách bản thân ngày 15. Mỗi ngày 1...
ngminhtrung viết 15 ngày trước
2 0
White
2 2
Day016 Mấy nay đang phải làm Rust lại nên lại viết TIL về Rust. Một trường hợp lỗi mà ai cũng có thể mắc phải khi làm việc với vòng lặp for lồng ...
Huy Trần viết 1 ngày trước
2 2
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
100 bài viết.
1440 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!