[Functional Programming + Elm] Bài 5 – Monad & Monoid

Tổng kết từ bài viết trước đó thì chúng ta mới có thêm các công cụ là: class Functor để triển khai hàm điều khiển map cho một kiểu dữ liệu bất kỳ bao gồm cả các kiểu primitive và các kiểu có cấu trúc, và class Applicative để áp dụng các cấu trúc dữ liệu tổ hợp đang lưu trữ cục bộ một hàm f lên một giá trị khác cùng kiểu cấu trúc giống như đang trực tiếp sử dụng hàm f đó.

Trong bài viết này chúng ta sẽ tìm hiểu về các pattern có tên là Monad và Monid cũng rất phổ biến trong môi trường Functional. Chúng ta hãy đầu với Monad, tiếp tục là một class mở rộng từ dòng Functor -> Applicative.

Monad

Ở đây chúng ta sẽ nhắc lại một chút về các class đã biết trước đó. Đầu tiên chúng ta có class Functor được sử dụng để tạo ràng buộc triển khai hàm map để làm trình điều khiển HOF cho một kiểu dữ liệu bất kỳ.

Sau đó thì Applicative mở rộng từ Functor với ràng buộc bổ sung là yêu cầu viết code triển khai cho hàm apply, và điểm đặc biệt của apply là cho phép chúng ta áp dụng tính năng của một hàm đang được lưu trữ bên trong một cấu trúc dữ liệu vỏ bọc lên một cấu trúc dữ liệu khác cùng kiểu.

Và bây giờ chúng ta có thêm Monad tiếp tục mở rộng từ Applicative với ràng buộc bổ sung là yêu cầu viết code triển khai cho hàm bind, để có thể truyền một giá trị Wrapped a vào một hàm func : (a -> Wrapped b). Điểm lưu ý ở đây là chúng ta đang có một hàm bất kỳ func được thiết kế để nhận vào một giá trị a và trả về giá trị b được đặt trong vỏ bọc Wrapped so với kiểu của a.

Điều đó có nghĩa là thao tác bind sẽ phải phân tích cấu trúc của Wrapped a để tách lấy a và truyền vào hàm func. Như vậy chúng ta có định nghĩa class Monad như sau.

moduleClassexposing(YesNo,Functor,Applicative,Monad)typealiasMonadabcdexy={bind:a->(b->c)->d,apply:e->a->c,map:(x->y)->a->c}typealiasApplicativeabcde={apply:a->b->c,map:(d->e)->b->c}typealiasFunctorabcd={map:(a->b)->c->d}-- type alias YesNo ...

Do không được hỗ trợ ở cấp độ cú pháp của ngôn ngữ nên chúng ta vẫn phải viết định nghĩa kèm theo các hàm apply và map được kế thừa từ các class trước đó; Và mốc xuất phát để đặt tên các Type Variable sẽ ưu tiên từ hàm bind mới xuất hiện.

Sau đó ở phần code triển khai chúng ta sử dụng lại code của module MaybeExt của bài viết trước. Chúng ta đã có các hàm apply và map hoạt động tốt khi triển khai class Applicative. Bây giờ chúng ta sẽ thay bước khai báo class từ Applicative thành Monad.

moduleMaybeExtexposing(map,apply,bind)import Class exposing(..)instanceMonad:MonadabcdexyinstanceMonad=Monadbindapplymap-- bind : Not Implemented ...-- apply : Done ...-- map : Done ...

Hàm bind mà chúng ta cần triển khai đầu tiên sẽ nhận vào một giá trị a trong kiểu vỏ bọc Wrapped, và như vậy chúng ta có thông tin định kiểu là Maybe a. Tham số tiếp theo là hàm func : (a -> Wrapped b) sẽ có thông tin định kiểu tương ứng là (a -> Maybe b).

bind:Maybea->(a->Maybeb)->Maybeb

Logic xử lý trong hàm là chúng ta có trường hợp Maybe a có thể là Nothing hoặc Just a. Trong trường hợp hàm bindnhận được Nothing thì sẽ không áp dụng hàm func mà trả về luôn Nothing, và trường hợp còn lại thì chúng ta tách lấy giá trị a trong pattern và truyền vào func.

bind:Maybea->(a->Maybeb)->MaybebbindmaybeAnyfunc=casemaybeAnyofNothing->NothingJustany->funcany

Và từ thông tin định kiểu của các hàm chúng ta có thể đối chiếu ngược lại để đặt thông tin định kiểu cụ thể cho các Type Variable trong phần khai báo instanceMonad

instanceMonad:Monad(Maybea)a(Maybeb)(Maybeb)(Maybe(a->b))abinstanceMonad=Monadbindapplymap

Tổng kết code của module MaybeExt:

moduleMaybeExtexposing(map,apply,bind)import Class exposing(..)instanceMonad:Monad(Maybea)a(Maybeb)(Maybeb)(Maybe(a->b))abinstanceMonad=Monadbindapplymapbind:Maybea->(a->Maybeb)->MaybebbindmaybeAnyfunc=casemaybeAnyofNothing->NothingJustany->funcanyapply:Maybe(a->b)->Maybea->MaybebapplymaybeFuncmaybeAny=casemaybeFuncofNothing->NothingJustfunc->mapfuncmaybeAnymap:(a->b)->Maybea->MaybebmapfuncmaybeAny=casemaybeAnyofNothing->NothingJustany->Just(funcany)

Bây giờ chúng ta lại mở Elm REPL để thử sử dụng MaybeExt.bind

cd learn-elm
elm repl

---- Elm 0.19.1 ----------------------------------------------------------------
Say :help for help and :exit to exit! More at <https://elm-lang.org/0.19.1/repl>
--------------------------------------------------------------------------------
> import MaybeExt exposing (..)

> MaybeExt.bind (Just 9) (n -> Just (n * 9))
Just 81 : Maybe number

Ý nghĩa căn bản của việc sử dụng Monad như chúng ta thấy ở đây là có thêm hàm bind để cho phép chúng ta gắn một cấu trúc dữ liệu có thể ở dạng phức tạp vào một hàm vô danh lamda với định nghĩa rất ngắn gọn; Bởi logic phân tích cấu trúc dữ liệu đã được tổng quát tại hàm bind và như vậy lamda sẽ chỉ thể hiện logic xử lý chính mà chúng ta mong muốn.

Đây là điểm mà chúng ta có thể suy nghĩ tới trong việc áp dụng sang một môi trường khác như JavaScript, các logic rẽ nhánh dựa trên trạng thái của các cấu trúc dữ liệu thực ra lặp lại rất nhiều và có thể được tổng quát vào các HOF như đã thấy.

Trong số các kiểu dữ liệu có cấu trúc của JavaScript thì mới chỉ có duy nhất Array được định nghĩa nhiều HOF có bao gồm cả map, tuy nhiên vẫn chưa có apply như code JavaScript ví dụ ở cuối bài viết trước và bind với logic tổng quát như Monad ở đây.

Bạn có thể thử code bổ sung các HOF này cho class Set và class Map trong JavaScript để sử dụng. Chắc chắn là các HOF sẽ rất hữu ích và giảm thiểu được rất nhiều các thao tác chuyển đổi dữ liệu về mảng Array để sử dụng các HOF sẵn có, đặc biệt là đối với trường hợp của class Set.

Để tránh nhầm lẫn thì apply và bind của class Function trong JavaScript không có ý nghĩa tương đương với các hàm cùng tên của Applicative và Monad ở đây; Bởi đó chỉ là các phương thức thay thế cho cú pháp gọi hàm thông thường hoặc gắn kèm địa chỉ tham chiếu của object vào hàm có nội dung cần sử dụng con trỏ this.

Các HOF mà chúng ta đang nói tới thuộc về các module của các cấu trúc dữ liệu, và sẽ có logic triển khai chi tiết khác nhau tùy vào cấu trúc của mỗi kiểu dữ liệu. Nếu như chúng ta triển khai các HOF trong JavaScript thì sẽ ở dạng các phương thức của các object dữ liệu giống như funcArray.apply(valueArray) hoặc các phương thức static của các class để có cú pháp sử dụng giống như Elm ở đây.

Monoid

Khái niệmMonoid khá đơn giản, nhưng bản thân mình không còn vốn từ vựng của môn Toán nên cũng không biết phải dịch tên gọi này thế nào. Tuy nhiên, để mô tả bản chất thì chúng ta có thể hiểu một giao diện Monoid sẽ bao gồm các thành phần có tên gọi là: một hàm liên kết Associative, một giá trị đặc trưng Identity, và một hàm điều khiển thực hiện liên kết một danh sách các giá trị bằng cách sử dụng Associative.

Đầu tiên chúng ta có Associative là một phép thực thi thỏa mãn điều kiện là các giá trị xoay quanh có được sắp xếp thế nào cũng sẽ không ảnh hưởng tới kết quả cuối cùng; Ví dụ như phép cộng +, phép nhân *, v.v… hoặc một phép thực thi mô tả tương tác trong phần mềm không nhất thiết phải liên quan tới Toán học.

(a + b) + c
a + (b + c)
(a + c) + b

hoặc

(a * b) * c
a * (b * c)
(a * c) * b

Yếu tố tiếp theo, Identity là một giá trị vô nghĩa đối với phép thực thi Associative. Ví dụ chúng ta có giá trị 0 vô nghĩa với phép tính + bởi x + 0 = x, hoặc giá trị 1 vô nghĩa với phép tính * bởi x * 1 = x.

Và yếu tố còn lại là hàm điều khiển thì không thuộc về định nghĩa Monoid trong Toán Học nên chúng ta sẽ nói đến ở phần code ví dụ sau đây. Trước hết chúng ta sẽ có định nghĩa tổng quát của giao diện Monoid với tên đại diện của các yếu tố được đặt theo quy ước chung trong môi trường Functional Programming và lần lượt là append, empty, và concat.

moduleClassexposing(..)typealiasMonoida={append:a->a->a,empty:a,concat:Lista->a}-- type alias Monad ...-- type alias Applicative ...-- type alias Functor ...

Với các ví dụ x + 0 = x và x * 1 = x thì chúng ta có thể thấy rằng kiểu dữ liệu number hay bất kỳ kiểu dữ liệu nào khác cũng đều có thể có nhiều giao diện Monoid; Cứ miễn sao chúng ta chỉ ra được một cặp Associative & Identity là chắc chắn sẽ có thể viết được hàm điều khiển liên kết danh sách các giá trị để sử dụng.

Như vậy chúng ta có thể tạo ra các module riêng dành cho mỗi Monoid để có cú pháp sử dụng ngắn gọn và trực quan, thay vì tập trung tất cả các Monoid vào một module ví dụ như Sum, Product thay vì NumberExt. Bây giờ chúng ta sẽ xem xét code ví dụ của module Sum với phép liên kết Associative là phép tính cộng + và giá trị đặc trưng Identity là 0.

moduleSumexposing(..)import Class exposing(..)instanceMonoid:Class.MonoidnumberinstanceMonoid=Monoidappendemptyconcatappend:number->number->numberappendab=a+bempty:numberempty=0concat:Listnumber->numberconcatnumberList=casenumberListoffirst::restList->appendfirst(concatrestList)[]->empty

Ở vị trí của hàm điều khiển concat chúng ta đang sử dụng Associative và Identity để tính tổng của một danh sách các giá trị số học. Đây chính là ứng dụng của Monoid để giải quyết bài toán tính gộp giá trị cho một tập hợp.

Do các môi trường thuần Declarative không có cú pháp vòng lặp nên giải thuật đệ quy là phương thức duy nhất để thực hiện công việc tính tổng của một danh sách, và trong tất cả những trường hợp khác nữa khi chúng ta cần chuyển đổi một danh sách thành một giá trị biểu trưng duy nhất.

Những yếu tố căn bản để sử dụng giải thuật đệ quy lại chính là các thành phần Associative và Identity của Monoid. Ví dụ như khi tính tổng thì chúng ta xem phép tính (+) là Associative và cần chỉ ra Identity tương ứng là 0 để làm điểm dừng edge case cho logic rẽ nhánh mỗi lần lặp; Hoặc khi tính tích thì chúng ta xem phép tính (*) là Associative và cần chỉ ra Identity là 1 tại edge case.

> import Sum exposing (..)

> Sum.empty
0 : number

> Sum.append 0 1
1 : number

> Sum.append 1 2
3 : number

> Sum.append 3 3
6 : number

> Sum.append 6 4
10 : number

> Sum.append 10 5
15 : number

> Sum.append 6 15
21 : number

> Sum.concat [9,8,7,6,5,4,3,2,1]
45 : number

Hiển nhiên là trong trường hợp xử lý dữ liệu thực tế thì chúng ta có thể sẽ muốn sử dụng các HOF có sẵn để thay cho việc định nghĩa hàm đệ quy dài dòng; Ví dụ như List.foldr hoặc List.foldl, hoặc trong JavaScript thì là array.reduce, _.reduceRight; Và hàm concant lúc này sẽ có thể được viết ở dạng tổng quát chung có thể copy/paste cho các module triển khai Monoid.

concatdataList=List.foldrappendemptydataList

Ok, như vậy là chúng ta đã điểm qua hết những khái niệm căn bản của Functional Programming. Bây giờ thì chúng ta đã có thể tiếp tục tìm hiểu cách sử dụng Elm để xây dựng ứng dụng trang đơn SPA - Single Page Application. Ở bài viết cuối cùng của Sub-Series Declarative thì chúng ta đã phải tạm dừng ở đoạn tìm hiểu về các công cụ hỗ trợ phân tích cấu trúc URL để chuyển qua tìm hiểu về các HOD ở Sub-Series này.

Để thuận tiện cho việc theo dõi và đọc lại các kiến thức liên quan về kiến trúc Elm Architecture và trình điều khiển Browser.Element thì mình sẽ viết bài mới nối tiếp ở phần đang tạm dừng của Sub-Series Declarative. Sau khi xây dựng xong một SPA đơn giản thì chúng ta sẽ xem xét việc có nên quay trở lại Sub-Series Functional này và khởi tạo thêm một project Elm Fullstack hay không.

(chưa đăng tải) [Declarative Programming + Elm] Bài 16 – URL Parser Module