Câu hỏi thắc mắc mới về việc các ngôn ngữ Functional
sử dụng List
làm cấu trúc chủ đạo để lưu trữ tập giá trị có phần hơi lạc đề so với dự định ban đầu mà mình bắt đầu cái mini project
này. Tuy nhiên đó là điểm đặc biệt của phương thức học theo vết dầu loang, cứ biết tới đâu thì tò mò tới đó, và cứ như vậy thì mới có động lực để tiếp tục mầy mò kiến thức mới.
Câu chuyện lúc này quay trở lại với tư tưởng lập trình hàm Functional
vốn đậm chất Toán Học và mọi thứ xuất phát từ biểu thức f(x) = ... x
. Một hàm luôn được biểu thị ở dạng biểu thức chứ không phải là một chuỗi các chỉ thị trình tự, và vì vậy các ngôn ngữ Functional
chủ đạo thì hầu hết là đều có cú pháp thuần Declarative
.
; Chỉ có các định nghĩa và các cấu trúc gắn kèm để giải thích bổ nghĩa cho các yếu tố đã sử dụng của định nghĩa trước đó; Không có các chỉ thị trình tự và cũng vì vậy nên sẽ không có các vòng lặp, bởi như chúng ta đã biết thì bản chất của vòng lặp chính là một chuỗi chỉ thị trình tự được điều hướng xoay vòng lặp lại bởi các nhãn gắn tên label :
.
Recursion
Hệ quả tiếp theo là không có công cụ để lặp thao tác trên các tập dữ liệu và lúc này chúng ta lại quay lại với chủ đề Đệ Quy recursion
. Và nếu bạn để ý thì bản thân định nghĩa struct item
mà chúng ta đã viết cũng là một định nghĩa Đệ Quy với các trường dữ liệu bên trong trỏ về các giá trị của chính kiểu dữ kiệu struct item
đang định nghĩa.
Và trong môi trường thuần Declarative
thì lối tư duy Đệ Quy cũng lại là phương thức chủ đạo để giải quyết tất cả mọi vấn đề logic chứ không chỉ các tác vụ tính toán tập hợp. Có lẽ đây chính là lý do khiến List
được sử dụng làm container
chính cho các tập dữ liệu trong các môi trường Functional
.
list_populate
Nhân tiện thì chúng ta đang còn thiếu phương thức khởi tạo List
cho phép liệt kê các phần tử đã biết với một dạng cú pháp thu gọn nào đó. Chúng ta sẽ mượn cú pháp khởi tạo mảng sẵn có của C
, và trình khởi tạo list_from
sẽ nhận vào một mảng thuần literal array
đang chứa sẵn nội dung để chuyển đổi thành List
.
// --- typedef ...
// --- constructors Item item_new (void);
List list_new (void); void list_populate (List $list, void* $literal_array, int $length);
Trình khởi tạo list_populate
ở đây vẫn sẽ được xây dựng trên logic biến đổi List
ban đầu sau đó trả về kết quả thông qua tham số $list
; Tuy nhiên thao tác nạp dữ liệu từ mảng sẽ được xử lý theo phương cách Đệ Quy.
#include "../list.h" void list_populate ( List $list , void* $literal_array , int $length ) { val* $val_pointer = $literal_array; Item $item; if ($length == 0) { /* do nothing */ ; } else { $item = item_new (); *((val*) $item->data) = $val_pointer[0]; list_unshift ($list, $item); $val_pointer += 1; $length -= 1; list_populate ($list, $val_pointer, $length); } }
Sau đó tại code chạy thử main
, chúng ta đã có thể mượn cú pháp khởi tạo mảng sẵn có của C
.
#include <stdio.h>
#include <stddef.h>
#include "list.h" int main ( int $argc , char** $argv ) { val $number_array[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; List $list = list_new (); list_populate ($list, $number_array, 10); Item $cursor = $list->first; loop : if ($cursor != NULL) { printf ("%f \n", *((val*) $cursor->data)); $cursor = $cursor->next; goto loop; } return 0; }
Và kiểm tra kết quả tại cửa sổ dòng lệnh..
gcc src\main.c src\list\*.c src\list\item\*.c -o bin\main
bin\main 9.000000 8.000000
7.000000
6.000000
5.000000
4.000000
3.000000
2.000000
1.000000
0.000000
List Variants
Ok.. như vậy là kết quả tìm hiểu về cấu trúc lưu trữ List
đã giúp mình trả lời được khá nhiều câu hỏi mà bản thân vẫn luôn thắc mắc từ khi bắt đầu học JavaScript
và cả những câu hỏi mới phát sinh khi biết tới Functional
.
Thực tế thì trong tài liệu DSA
mà mình đọc tham khảo có một vài biến thể của List
và biến thể mà chúng ta đã sử dụng ở đây được gọi là Danh Sách Hai Chiều Doubly Linked List
. Biến thể này cho phép thực hiện thao tác lặp từ cả hai đầu của List
tùy vào bối cảnh áp dụng và loại dễ triển khai hơn thì chỉ hỗ trợ một chiều di chuyển next
hoặc prev
.
Như vậy là sau khi tìm hiểu về Array
và List
, và sau đó là một lý thuyết bỏ ngỏ về Vector
, chúng ta đã biết rằng khi nói về một cấu trúc dữ liệu thì thực ra chúng ta đang có các khía cạnh quan tâm là:
- Cách tổ chức và sắp xếp dữ liệu trong bộ nhớ theo kiểu liên tiếp hoặc rời rạc.
- Giao diện lập trình cung cấp ra bên ngoài và giới hạn.
*
Các thuật toán xử lý liên quan.
Trong số đó thì yếu tố cuối cùng mang tính chất tối ưu hiệu năng là điểm mà mình tạm thời lược bỏ trong cái mini project
này bởi chưa có điểm ứng dụng phù hợp; Và yếu tố giao diện lập trình kèm theo giới hạn thao tác lại là điểm rất quan trọng mà mình muốn tìm hiểu để có thể lựa chọn kiểu cấu trúc dữ liệu phù hợp hơn khi viết code.
Và vì vậy nên trong những bài viết tiếp theo, chúng ta sẽ tìm hiểu về các cấu trúc dữ liệu mang ý nghĩa trọng tâm nhấn vào việc cung cấp giao diện lập trình để giới hạn thao tác trên tập dữ liệu. Điều này sẽ giúp cho chúng ta có thể lược bỏ bớt một phần logic sàng lọc các trường hợp ngoại lệ exception
nhờ giới hạn thao tác của cấu trúc dữ liệu và giảm thiểu khả năng phát sinh lỗi vận hành phần mềm.
(chưa đăng tải) [Imperative Programming + C] Bài 20 - Simplicity DSA Stack (mở đầu)