Lập trình bằng Google

Trước khi viết KTMT, công việc hàng ngày của chúng tôi đã từng theo một vòng lặp như sau:

1
2
3
4
5
6
7
8

while (còn vấn đề kỹ thuật cần giải quyết) {
  while (chưa biết cách giải quyết) {
    Google   # Google trả lời bằng rất nhiều lời giải...
    foreach(kết quả) {
      Thử từng kết quả
    }
  }
}

Chúng tôi nhận ra có rất nhiều vấn đề ở vòng lặp này: vấn đề tìm kiếm cũng như lời giải hoàn toàn vụn vặt và thiếu tính khái quát, cùng một vấn đề hoặc vấn đề tương tự nhau nhưng nhiều khi phải google rất nhiều, nhiều khi giải quyết được vấn đề nhưng đấy lại không phải là cách giải quyết tốt nhất, cách giải quyết tốt nhất nhiều khi lại đến từ bạn bè xung quanh mình.

Chúng tôi nhận thấy nếu như không tổng hợp lại những điều mình đã tìm hiểu thì sẽ không có cách nào nhớ được cách giải quyết. Cách đơn giản nhất mà chúng tôi đã nhận thấy là viết và chia sẻ cho bạn bè. Viết giúp tổng hợp các cách giải quyết vấn đề, giúp lưu lại cách giải quyết đó cho những lần sau. Viết cũng chính là giải thích lại vấn đề cho chính bản thân sau này. Chia sẻ giúp nhận được góp ý từ những người giỏi hơn mình. Do vậy chúng tôi đã bắt đầu blog KTMT. Giống như đã viết ở KTMT blog nguồn mở, chúng tôi nhận thấy chúng tôi dần dần thoát khỏi vòng lặp nói trên.

“Viết” có chắc chắn là cách giải quyết vấn đề?

• Albert Einstein đã từng nói:

Để hiểu rõ một điều gì đó, hãy thử giải thích điều đó một cách đơn giản nhất.

• Leslie B. Lamport đã từng nói:

If you’re thinking without writing, you only think you’re thinking.

Khi chúng ta không viết ra, chúng ta chỉ tưởng là chúng ta đã biết thôi. Thực sự là chúng ta là chưa biết gì cả.

Hãy giải thích một cách đơn giản và hãy viết ra là thông điệp của 2 vĩ nhân trên. Do vậy chúng tôi tin tưởng viết chính là cách giải quyết cho vấn đề của chúng tôi.

Viết liệu có khó khăn?

Bắt đầu viết không hề đơn giản. Chúng tôi đã từng thử khảo sát và nhận ra viết lách thật sự không hề dễ. Các bạn trả lời cho điều tra trên gặp những vấn đề sau đây:

Suy nghĩ: “Chỉ chuyên gia mới viết được bài viết kĩ thuật?”

Tôi không phải là một chuyên gia về một vấn đề gì cả, vậy nên chả biết viết về cái gì cả!!

Đây có lẽ là một lý do thiếu thuyết phục nhất. Bạn không cần phải là chuyên gia mới viết được blog. Trong 85 bài viết của KTMT blog, có những chủ đề mà chúng tôi hoàn toàn chưa hiểu rõ cho đến khi bắt tay vào tìm hiểu và viết lại. Và chính nhờ việc nghiên cứu rất nhiều để viết đã giúp chúng tôi hiểu ra nhiều điều.

Viết sai làm tôi trông như một đứa ngớ ngẩn?

Nếu tôi viết một thứ gì đó không đúng, hay viết sai, tôi sẽ bị nhìn như một thằng đần trên internet

Đây có lẽ là một lý do làm nhiều bạn “sợ” viết nhất. Chúng tôi cũng như bạn, chúng tôi cũng dễ mắc phải các sai lầm. Không phải 100% kiến thức chúng tôi viết ra ngay lần đầu tiên là chính xác. Và chính các bạn, những người đọc là những người giúp chúng tôi nhận ra điều đó, trách nhiệm của chúng tôi là sửa lại cho đúng. Vậy ai là người có lợi ở đây: người viết ra, hay người không viết ra? Chắc các bạn có thể tự trả lời được câu hỏi này.

Điều quan trọng nhất tự việc nhầm lẫn (make mistake) là việc thu dọn những nhầm lẫn đó, và học những điều mới từ nó.

Viết tốt quá khó!

Tôi có thể code tốt, nhưng viết thì chịu, viết câu cú đúng ngữ pháp, có nội dung hợp lý với tôi như một cực hình.

Điều này chúng tôi hoàn toàn đông ý với bạn. Viết tốt là một trong những điều khó nhất mà tôi từng biết. Viết để cho mình hiểu đã khó, cho người khác, đặc biệt là cho những người không cùng kĩ năng với bạn hiểu được còn khó hơn. Tuy nhiên trong công việc hàng ngày, 50% việc bạn phải làm là giao tiếp, là nói cái mình hiểu cho người khác hiểu. Việc tập luyện kĩ năng viết cho người khác hiểu chính là giúp tăng kĩ năng giao tiếp của bạn lên. Hãy kiên trì và sẽ đến một lúc các bạn nhận ra rằng việc viết tốt giúp bạn nhiều đến thế nào.

Hy vọng bài viết đến đây đã truyền tải được phần nào những gì chúng tôi đang suy nghĩ về việc chia sẻ các vấn đề kĩ thuật bằng cách viết ra. Chính vì tầm quan trọng của việc chia sẻ các kiến thức kĩ thuật, và muốn phủ rộng hơn văn hoá viết ra và chia sẻ với cộng đồng kĩ thuật tại Việt Nam nói chung, chúng tôi đã quyết định làm một điều lớn hơn là chỉ open blog.

Ngôi nhà mới kipalog.com

Chúng tôi đã quyết định xây dựng một nền tảng, mà ở đó ai cũng có thể viết để chia sẻ kiến thức của mình một cách dễ dàng, có thể tìm kiếm và học hỏi kiến thức có chất lượng từ những người cùng làm kĩ thuật chuyện nghiệp khác. Bạn hãy tưởng tượng đó là một kho kiến thức chất lượng cao, một môi trường cởi mở và tôn trọng lẫn nhau của những người có cùng niềm đam mê về kĩ thuật.

Nền tảng được đặt tên là Kipalog và đặt tại trang web: http://kipalog.com

Kipalog là cách gọi tắt của “keep a log”, cũng chính là khái niệm chủ đạo của nền tảng này, coi trọng việc “log” hay là giữ lại các kiến thức của bạn bằng cách “viết ra”.

Vậy bạn có thể làm gì với Kipalog:

• Bạn có thể viết để chia sẻ kiến thức kĩ thuật của bạn với người khác. Chúng tôi cung cấp cho bạn trình soạn thảo markdown với khả năng hiển thị trực quan theo 2 cột, kéo thả / cắt dán ảnh trực tiếp và nhiều tiện ích khác, giúp bạn cảm thấy thoải mái khi viết một tài liệu kĩ thuật.
• Bạn có thể đọc, học hỏi và kipalog kiến thức của người khác. Việc kipalog giúp bạn giữ lại những kiến thức cần thiết cho bản thân để có thể tìm lại dễ dàng về sau.
• Bạn có thể trao đổi, cung cấp phản hồi cho các bạn khác. Nếu bạn có cách giải quyết tốt hơn, hãy đóng góp thông qua bình luận. Bản thân bình luận cũng có thể viết bằng markdown.
• Các công ty và tổ chức chia sẻ công nghệ cũng như kinh nghiệm của bản thân công ty mình, đồng thời thu lợi được công nghệ và kinh nghiệm từ các công ty và tổ chức khác.

Tại sao bạn nên bắt tay vào đăng ký và viết bài trên Kipalog:

• Tại Kipalog, chúng tôi đảm bảo việc chia sẻ và phản hồi đều dựa trên tinh thần tôn trọng lẫn nhau.
• Năng lực của bạn sẽ được thể hiện qua những gì bạn viết. Những bài viết tốt chứ không phải là số năm kinh nghiệm thể hiện bạn là một kĩ sư chuyên nghiệp và có trình độ cao.
• Bạn sẽ có cơ hội kết bạn và giao lưu với những người cùng đam mê kĩ thuật khác (trong đó có những người viết của chính blog KTMT).

Vậy KTMT sẽ ra sao?

Chúng tôi sẽ chuyển blog KTMT thành một tổ chức trên Kipalog.

http://kipalog.com/organizations/KTMT

Blog KTMT sẽ vẫn được giữ ở trạng thái hoạt động, nhưng sẽ không cập nhật các bài viết mới. Các bài viết mới sẽ được viết dưới tổ chức KTMT. Bạn nào muốn viết blog cho KTMT có thể tham gia tổ chức KTMT trên Kipalog cùng chúng tôi.

Kết luận

Chúng tôi hy vọng bạn sẽ thích Kipalog. Trên hơn cả, chúng tôi hy vọng các bạn xem Kipalog không chỉ là nơi để đọc, mà còn là nơi các bạn tích cực chia sẻ vốn kiến thức của bản thân.

Cám ơn các bạn. Đón đọc những tri thức của bạn tại kipalog.com :)

“If you’re thinking without writing, you only think you’re thinking.” – Lessie Lamport

Giới thiệu

Mình rất thích câu nói trên của Lamport. Đối với mình câu nói trên hay ở chỗ: vế sau của câu là một cách nói đệ quy. “Bạn chỉ nghĩ rằng là bạn đang suy nghĩ”. Suy nghĩ là để tìm ra câu trả lời cho một câu hỏi nào đó. Nhưng nếu không có việc viết lách, đối tượng của suy nghĩ sẽ chỉ đơn thuần là “sự suy nghĩ” - và chúc mừng bạn, bạn rơi vào vòng lặp đệ quy vô hạn. Cách duy nhất để bạn thoát khỏi vòng lặp đệ quy vô hạn của suy nghĩ là phải định nghĩa một điểm khởi đầu trong tư duy. Viết lách chính là điểm khởi đầu đó.

Blog ktmt cũng bắt đầu với một ý tuởng đơn giản như ở trên: một chỗ để các thành viên viết và chia sẻ cho những thành viên khác điều mình học đuợc. Bài viết không cần phức tạp, chỉ cần có nội dung liên quan đến kỹ thuật là được chấp nhận. “Muốn chia sẻ điều mình học đuợc?” - Hãy viết một bài về chủ đề đó và các thành viên khác sẽ đọc. Ý tuởng thì là vậy nhưng thực hiện đuợc nó thật sự rất gian nan. Khi thực sự viết ra, bọn mình mới thấy để viết đuợc một bài cần đầu tư rất nhiều thời gian, từ nghiên cứu cho đến viết code mẫu để demo cho bài viết. Tuy vậy nhờ việc viết ra những điều mình tuởng là biết bọn mình khám phá ra có rất nhiều chỗ bọn mình chưa thực sự biết như mình tuởng. Mỗi câu văn khó hiểu cho người đọc thật sự không chỉ do cách viết mà còn do sự thiếu tuờng tận và am hiểu về chủ đề đuợc viết. Cứ mỗi bài viết, bọn mình là đọc rất kỹ, kiểm tra cho nhau và đưa ra những góp ý sửa chữa cho nhau. Nhờ vậy am hiểu của ngưòi viết về chủ đề đang viết cũng như nguời đọc trở nên sâu sắc hơn.

Bọn mình đưa bài lên một blog chỉ đơn giản với mục đích cho các thành viên khác đọc và góp ý. Thế nhưng dần dần bọn mình nhân ra rằng không chỉ cá nhân nhóm tác giả mà còn rất nhiều bạn đọc khác cũng đọc và góp ý. Bài viết của bọn mình một phần nào đó đã đem lại ích lợi cho cho cộng đồng. Ngoài ra bọn mình cũng nhận được nhiều đóng góp cũng như câu hỏi từ bạn đọc. Những đóng góp và câu hỏi giúp bọn mình rất nhiều trong việc hiểu sâu sắc hơn chủ đề mỗi bài viết. Bọn mình nhận thấy bọn mình không những học đuợc lẫn nhau mà còn học đuợc từ rất nhiều bạn đọc khác - điều bọn mình rất vui.

Gần đây bọn mình nhận đuợc nhiều ý kiến đề xuất đóng góp bài viết. “Sao không!” là câu nói đầu tiên xuất hiện trong đầu của tất cả các thành viên blog ktmt. Đối với bọn mình đây là điều không gì vui hơn. Blog sẽ có nhiều bài viết mới từ nhiều góc độ suy nghĩ cũng như kiến thức hơn (và bọn mình sẽ có cơ hội học được từ nhiều ngưòi hơn). Các bạn tác giả sẽ có nơi để luyện tập viết lách. Độc giả sẽ có nhiều bài viết để đọc hơn. Sau khi cân nhắc nhiều yếu tố - hầu hết chỉ có lợi - bọn mình đi đến quyết định:

Biến ktmt trở thành một blog cộng đồng!

Mở rộng blog KTMT

Blog ktmt sẽ không chỉ bao gồm bài viết của nhóm tác giả hiện tại mà sẽ nhận bài viết từ tất cả các bạn nào muốn đóng góp. Mỗi bài viết của KTMT đều đuợc viết bằng ngữ pháp Markdown, sử dụng Octopress để biên tập và chia sẻ trên máy chủ của github. Về cách sử dụng các tool này các bạn có thể tham khảo: Blogging With Github and Octopress. Để giữ blog không thay đổi quá nhiều ở giai đoạn đầu, bọn mình quyết định quy trình đóng góp bài viết như sau:

• Fork https://github.com/ktmt/ktmtblog-octopress/
• Viết bài mới.
• Tạo Pull Request đến repository của KTMT.
• “Ban biên tập” sẽ tiến hành biên tập và góp ý công khai trên Pull Request.
• Các bài viết đáp ứng đuợc yêu cầu sẽ được merge và đưa lên blog KTMT.

Tiêu chí biên tập là điều bọn mình đã suy nghĩ nhưng vẫn chưa tìm ra đuợc những tiêu chí xác đáng. Vì vậy truớc mắt bọn mình tạm đề ra các tiêu chí biên tập như duới đây:

• Bài viết phải có nội dung về kỹ thuật và máy tính.
• Bài viết nên đuợc viết bằng tiếng Việt và có bố cục rõ ràng.
• Bài viết nên viết về chủ đề mà tác giả đã hoặc đang nghiên cứu.
• Bài viết nên đuợc đầu tư thời gian về ý tuởng và cách diễn đạt.
• Bài viết có tính mới mẻ và sáng tạo là hoàn hảo!
• Bài viết nếu có mã nguồn demo thì càng tốt. Linux Torvalds đã từng nói: “Talk is cheap. Show me the code”. Mã nguồn chuơng trình chạy được sẽ như một bức tranh đáng giá hàng ngàn từ ngữ.

Ngoài ra bọn mình cũng đã thiết lập một trang Facebook group của blog. Các thảo luận xung quanh bài viết sẽ đuợc thực hiện thông qua page này.

Ban biên tập

Trước mắt ban biên tập sẽ chỉ bao gốm những thành viên đóng góp thuờng xuyên của KTMT:

• dtvd
• huydx
• kiennt
• viethnguyen
• telescreen

Trong tuơng lai bọn mình muốn sẽ có những thành viên xuất sắc trong biên tập. Vì vậy bọn mình tạm đề ra một tiêu chí để tham gia ban biên tập như sau:

“Là một thành viên đóng góp thuờng xuyên và có nhiều bài viết tốt cho blog KTMT”.

Thành viên nào đóng góp đuợc 5 bài viết sẽ đuợc tính là thành viên thường xuyên. Về tiêu chí bài viết tốt, bọn mình hiện đang trong quá trình xây dựng cách đánh giá cho tiêu chí này.

Kết thúc

Bọn mình mong chờ nhiều bài viết tốt hơn nữa từ các bạn!

Tham khảo

1. Bài phát biểu của Lessie Lamport
2. Những câu nói của Linus Torvalds

Trong bài viết này, tôi sẽ trình bày về một đặc tính của Haskell khá khác biệt so với các ngôn ngữ lập trình khác, đó là laziness (dịch tiếng việt nôm na là “luời biếng”, nhưng tôi xin đuợc giữ nguyên từ gốc tiếng anh).

Chúng ta hiểu laziness như thế naò? Lazy evaluation nghĩa là, việc evaluate các đối số của hàm sẽ đuợc trì hoãn càng lâu càng tốt, chúng sẽ không đuợc evaluate cho đến khi biểu thức thực sự cần đến gía trị của chúng. Khi một biểu thức đuợc đưa làm đối số cho một hàm, nó chỉ đuợc đóng gọn lại thành một biểu thức chưa đuợc đánh gía (unevaluated expression), mà chưa đuợc tính toán gì cả.

Chúng ta sẽ sử dụng Lecture 7 của course CIS 194 (Link) để minh họa cho việc tìm hiểu Laziness. Bên cạnh đó, tôi sẽ trình bày qua những syntax cơ bản của Haskell theo bài viết.

Tính số Fibonacci

Trong bài tập thứ nhất, chúng ta sẽ viết một hàm fib để tính ra số Fibonacci thứ n

1
2
3
4
5

-- Exercise 1 
fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Bên trên là điển hình của cách viết một hàm (function) trong Haskell. Truớc tiên, chúng ta có tên hàm nằm truớc dấu ::, trong truờng hợp này là hàm fib. Tiếp theo, nằm sau dấu ::, chúng ta có Integer -> Integer, đây chính là nơi khai báo đối số và giá trị trả về của Haskell. Trong truờng hợp này, hàm fib nhận đối số là Integer (số Fibonacci thứ mấy) và trả về Integer (số Fibonacci cần tìm). Tài liệu sau đây nói một cách khá đầy đủ về syntax viết function, bạn nên đọc thêm: Syntax in Functions

Sau dòng khai báo tên hàm và nguyên mẫu hàm là định nghĩa của một loạt pattern matching. Haskell sẽ match từ trên xuống duới, do vậy truớc tiên ta khai báo base case cho số Fibonacci thứ 0 và thứ 1. Các số Fibonacci tiếp theo, vì không match các base pattern nên sẽ sử dụng pattern thứ ba, cộng hai số Fibonacci phía truớc.

Chúng ta thấy cách khai báo pattern matching khá gần gũi vớí định nghiã dãy Fibonacci chúng ta đã học. Tiếp theo, ta định nghiã một dãy Fibonacci vô hạn như sau:

1
2

fibs1 :: [Integer]
fibs1 = map fib [0..]

map là một function trong Haskell, nhận vaò hai đối số là một hàm f và một danh sách. Nó sẽ trả về một danh sách mới mà các phần từ là kết qủa trả về tuơng ứng khi áp dụng hàm f với từng phần tử trong danh sách cũ. [0..] là cách viết danh sách tất cả các số nguyên duơng. Như vậy, ta có fibs1 là danh sách tất cả các số Fibonacci.

1
2
3
4
5
6

$ ghci
Prelude> :l HW07.hs
[1 of 1] Compiling HW07             ( HW07.hs, interpreted )
Ok, modules loaded: HW07.
*HW07> fibs1
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,

Bạn sẽ thấy một vài số Fibonacci đầu tiên hiện ra rất nhanh, nhưng đến một lúc nào đó, sẽ rất lâu để tính đuợc số Fibonacci tiếp theo. Lý do là vì mỗi số Fibonacci bị tính đi tính lại quá nhiều lần!

Và đây là lúc chúng ta áp dụng Laziness của Haskell.

1
2
3

-- Exercise 2 
fibs2 :: [Integer]
fibs2 = [0,1] ++ zipWith (+) fibs2 (tail fibs2)

Chúng ta đã biết dãy Fibonacci bắt đầu từ hai số 0, 1, nên ta khởi đầu khai baó dãy bằng 0,1.

Giả sử ta đã có một dãy Fibonacci vô hạn:

1

[0, 1, 1, 2, 3, 5, 8, 13, ...]

tail là phép toán bỏ đi phần tử đầu tiên của một dãy:

1

[1, 1, 2, 3, 5, 8, 13, ...]

zipWith kết hợp 2 dãy trên theo từng cặp phần tử sử dụng một phép toán naò đó (ở đây là phép cộng):

1
2
3
4
5

[0, 1, 1, 2, 3, 5, 8, 13, ...]
+
[1, 1, 2, 3, 5, 8, 13, ...]
=
[1, 2, 3, 5, 8, 13, ...]

Như vậy, dãy vô hạn Fibonacci có thể đuợc tính bằng cách thêm hai phần tử đầu tiên (0, 1) vào kết quả sau khi zip dãy Fibonacci vô hạn với tail của nó!

Và đây chính là sức mạnh của laziness! fibs2 là kết quả trả về mà chúng ta lại có thể để xuất hiện ở bên vế phải! Haskell chỉ evaluate vế phải khi naò thực sự cần thiết, cho nên mỗi khi cần tính một phần tử mới cho dãy fibs2, nó mới quay ra tìm lại những phần tử đằng truớc (đã đuợc tính).

1

*HW07> take 100 fibs2

100 số Fibonacci đầu tiên xuất hiện trong chớp mắt!

Streams

Trong phần này, chúng ta định nghĩa kiểu dữ liệu (data type) Stream, gần giống với list nhưng bị ràng buộc là phải vô hạn

1

data Stream a = Cons a (Stream a)

Bên trên là cách khai baó một kiểu dữ liệu, bắt đầu bằng từ khoá data. Stream là tên kiểu dữ liệu, tiếp sau đó đến truớc dấu = là type variable, tức là a có thể thay cho Integer, String, … và ta có kiểu dữ liệu Stream Integer hoặc Stream String tuơng ứng. Phiá sau dấu = là constructor của kiểu dữ liệu này: Cons, với 2 đối số thuộc kiểu a và Stream a. Bạn hãy tham khaỏ về cách taọ kiểu dữ liệu tại Link này

Hàm sau convert một stream thành list:

1
2

streamToList :: Stream a -> [a]
streamToList (Cons x s) = x : streamToList s

Trong exercise 4, chúng ta phải viết một instance của Show cho kiểu dữ liệu Stream. đến đây, chúng ta cần biết thêm về khái niệm Typeclass của Haskell. Typeclass có thể coi là một loại “giao diện”, nó định nghĩa một số loại hành vi, và các kiểu dữ liệu mà có cùng hành vi đó có thể được khai báo là instance của typeclass đó. Lấy ví dụ, Eq typeclass định nghĩa một giao diện cho những thứ có thể so sánh được. Cụ thể các hành vi mà nó định nghĩa như sau:

1
2
3
4
5

class Eq a where
    (==) :: a -> a -> Bool
    (/=) :: a -> a -> Bool
    x == y = not (x /= y)
    x /= y = not (x == y)

Theo đó, bất cứ type nào muốn được là một instance của Eq typeclass sẽ phải khai báo các hàm (==), (/=) (trên thực tế, chỉ cần khai báo một hàm, vì hàm còn lại được định nghĩa là phủ định của hàm kia).

Ví dụ, ta có một type như sau:

1

data Coin = Head | Tail

Chúng ta muốn Coin type là một instance của Eq typeclass thì ta làm như sau:

1
2
3
4

instance Eq Coin where
  Head == Head = True
  Tail == Tail = True
  _ == _ = False

Ở đây, chúng ta vẫn dùng pattern matching để định nghĩa hàm (==) với từng trường hợp của 2 đối số.

Quay trở lại với exercise 4, chúng ta định nghĩa Stream a thành một instance của Show typeclass như sau:

1
2

instance Show a => Show (Stream a) where
    show s = show $ take 20 (streamToList s)

Chúng ta thấy sự xuất hiện của kí tự “lạ”: =>. Trong khai báo instance, những gì xuất hiện trước dấu => là những ràng buộc về type. Ở đây, chúng ta muốn Stream a là instance của Show thì bản thân a, một type variable, cũng phải là một instance của Show. Có như vậy, chúng ta mới định nghĩa được hàm show của Show typeclass cho Stream a dựa trên hàm show cho a.

Đến kí tự lạ tiếp theo: $. Đây chỉ đơn giản là một chỉ dẫn cho Haskell là tất cả những gì xuất hiện sau $ có độ ưu tiên phép toán cao hơn, tức là show $ take 20 (streamToList s) tương đương với show (take 20 (streamToList s)). Nhưng chúng ta không muốn dùng quá nhiều dấu ngoặc, phải không :)

Trong định nghĩa hàm show cho Stream a, chúng ta không muốn nó in hết ra vô hạn phần tử, mà chỉ muốn in ra 20 phần tử đầu tiên. Do đó chúng chuyển nó thành list bằng hàm streamToList, lấy 20 phần tử đầu tiên bằng take 20 và áp dụng hàm show cho List a type (khi a là instance của Show rồi thì [a] cũng là instance của Show )

Chúng ta phải có một vài Stream để test. Hãy định nghĩa chúng:

1
2
3
4
5
6
7
8

streamRepeat :: a -> Stream a
streamRepeat x = Cons x (streamRepeat x)

streamMap :: (a->b) -> Stream a -> Stream b
streamMap f (Cons x s) = Cons (f x) (streamMap f s)

streamFromSeed :: (a->a) -> a -> Stream a
streamFromSeed f x = Cons x (streamMap f (streamFromSeed f x))

streamRepeat tạo ra một stream chứa vô hạn các phần tử giống hệt nhau. streamMap áp dụng một hàm (a->b) lên tất cả các phần tử của một Stream a để nhận được một Stream mới: Stream b. Cuối cùng streamFromSeed là một cách khác để tạo ra một stream, bằng cách bắt đầu từ một “hạt giống” thuộc type a, cũng chính là phần tử đầu tiên của Stream, rồi liên tục sử dụng một hàm có kiểu a->a để tạo ra các phẩn tử tiếp theo.

Tôi sẽ để dành phần này cho độc giả chiêm nghiệm xem tại sao lại viết như vậy.

Bây giờ, chúng ta hãy cùng test thử những gì chúng ta đã viết trong GHCi

1
2
3
4
5
6
7
8

*HW07> show $ streamFromSeed ('x':) "o"
"[\"o\",\"xo\",\"xxo\",\"xxxo\",\"xxxxo\",\"xxxxxo\",\"xxxxxxo\",\"xxxxxxxo\",\"xxxxxxxxo\",\"xxxxxxxxxo\",\"xxxxxxxxxxo
\",\"xxxxxxxxxxxo\",\"xxxxxxxxxxxxo\",\"xxxxxxxxxxxxxo\",\"xxxxxxxxxxxxxxo\",\"xxxxxxxxxxxxxxxo\",\"xxxxxxxxxxxxxxxxo\",
\"xxxxxxxxxxxxxxxxxo\",\"xxxxxxxxxxxxxxxxxxo\",\"xxxxxxxxxxxxxxxxxxxo\"]"
*HW07> show $ streamRepeat "o"
"[\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\",\"o\"]"
*HW07> show $ streamMap (+ 1) (streamRepeat 0)
"[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]"

Như vậy ta đã có một số hàm để làm việc với Stream, ta sẽ thử định nghĩa dãy số tự nhiên bằng Stream như sau:

1
2

nats :: Stream Integer
nats = streamFromSeed (+ 1) 0

1
2

*HW07> show nats
"[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]"

Ví dụ tiếp theo: Tính ruler function f(n) = số mũ lớn nhất của 2 là ước số của n. Bình thuờng chúng ta sẽ nghĩ đến việc chia 2 cho đến khi lẻ thì thôi. Nhưng tôi sẽ trình bày một lời giải khác, sử dụng laziness và cấu trúc dữ liệu vô hạn của Haskell.

Thay vì tính từng f(n) một, chúng ta sẽ xây dựng hẳn cả dãy số ruler f(n) với n bắt đầu từ 1: 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4..., trong đó phần tử thứ n trong stream là số mũ lớn nhất của 2 là ước số của n.

Dễ thấy có thể coi dãy trên là trộn xen kẽ của hai dãy, một dãy toàn 0 (vì tuơng ưng với n lẻ nên số mũ lớn nhất của 2 chỉ là 0) và dãy còn lại tuơng ứng với n chẵn. điều kì diệu là dãy thứ hai bao gồm chính các phần tử của dãy ruler nhưng cộng thêm 1 (Bạn thử suy nghĩ xem tại sao). Vì thế mà ta có cách khai báo ruler là một Stream Integer rất đẹp như sau:

1
2
3
4
5

interleaveStreams :: Stream a -> Stream a -> Stream a
interleaveStreams (Cons x1 s1) ~(Cons x2 s2) = Cons x1 (Cons x2 (interleaveStreams s1 s2))

ruler :: Stream Integer
ruler = interleaveStreams (streamRepeat 0) (streamMap (+ 1) ruler)

Lại thêm một kí tự lạ: tilde sign ~! Tôi đã thêm nó vào truớc đối số thứ hai của interleaveStreams. Kí tự này dùng để báo hiệu compiler đừng evaluate đối số thứ hai này. Nếu không có kí tự ~, pattern matching của hàm interleaveStream sẽ phải evaluate đối số thứ hai để đảm bảo nó thuộc type Stream a. đó không phải là điều chúng ta muốn, vì hàm ruler gọi hàm interleaveStream với đối số thứ hai chứa ruler, tức là gọi đệ quy vô hạn lần. Nếu đối số thứ hai của interleaveStream không lazy, hàm này sẽ dừng mãi ở việc evaluate để phục vụ pattern matching.

Nói nôm na, thêm dấu ~ truớc một đối số là chúng ta đã bảo với compiler là: “đừng lo, tôi đảm bảo đối số này sẽ có kiểu Stream a, nên đừng evaluate làm gì” :)

Kết luận

Bài viết này đã trình bày một số ví dụ để minh họa lazy evaluation của Haskell. Nó cho phép ta làm việc với những kiểu cấu trúc dữ liệu vô hạn, một pattern khá thuờng gặp trong Haskell. Việc định nghiã một cấu trúc dữ liệu vô hạn thực chất chỉ taọ ra một biểu thức chưa đuợc evaluate, mà ta sử dụng nó để chỉ ra cấu trúc dữ liệu hoàn chỉnh “có thể” phát triển đến như thế naò, và chỉ phần naò cần thiết mới đuợc tính toán.

Tuy nhiên, chủ đề laziness là một chủ đề khá phức tạp, đặc biệt khi chúng ta muốn đánh giá time và space của program. Có khá nhiều bài viết trên mạng về vấn đề này, một trong số đó bạn có thể tham khảo thêm là:

• How Lazy Evaluation Works in Haskell