4.7K 198 181

Published Jan 4th, 12:08 a.m. 8 min read

[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; Sau đó là class Applicative để áp dụng apply logic của các hàm f đang được lưu trữ cục bộ trong một Functor lên một giá trị khác cùng kiểu.

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à Monoid cũng rất phổ biến trong môi trường Functional. Chúng ta hãy bắt đầ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ị đơn giản a và trả về giá trị b được đặt trong vỏ bọc Wrapped, trong khi đó đối số sẽ được truyền vào hàm lại là một giá trị a được đặt trong vỏ bọc Wrapped.

Đ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.

module Class exposing (YesNo, Functor, Applicative, Monad)

type alias Monad a b c d x y =
   { bind  : a -> (b -> c) -> c
   , apply : d -> a -> c
   , map   : (x -> y) -> a -> c
   }

type alias Applicative a b c d e =
   { apply : a -> b -> c
   , map   : (d -> e) -> b -> c
   }

type alias Functor a b c d =
   { 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ẽ sử dụng lại code của module MaybeExt của bài viết trước đã 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.

module MaybeExt exposing (map, apply, bind)
import Class exposing (..)

instanceMonad : Monad a b c d x y
instanceMonad = Monad bind apply map

-- 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 tham số đầu vào là Maybe a; Và 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 : Maybe a -> (a -> Maybe b) -> Maybe b

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 Just và truyền vào func.

bind : Maybe a -> (a -> Maybe b) -> Maybe b
bind maybeAny func =
   case maybeAny of
      Nothing  -> Nothing
      Just any -> func any

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 như sau:

instanceMonad : Monad (Maybe a) a (Maybe b) (Maybe (a -> b)) a b
instanceMonad = Monad bind apply map

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

module MaybeExt exposing (map, apply, bind)
import Class exposing (..)

instanceMonad : Monad (Maybe a) a (Maybe b) (Maybe (a -> b)) a b
instanceMonad = Monad bind apply map

bind : Maybe a -> (a -> Maybe b) -> Maybe b
bind maybeAny func =
   case maybeAny of
      Nothing  -> Nothing
      Just any -> func any

apply : Maybe (a -> b) -> Maybe a -> Maybe b
apply maybeFunc maybeAny =
   case maybeFunc of
      Nothing   -> Nothing
      Just func -> map func maybeAny

map : (a -> b) -> Maybe a -> Maybe b
map func maybeAny =
   case maybeAny of
      Nothing  -> Nothing
      Just any -> Just (func any)

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

Trong môi trường Functional nói riêng, sau khi thực hiện một thao tác nhập/xuất I/O ví dụ như gửi yêu cầu truy vấn dữ liệu tới máy chủ web - hiển nhiên chúng ta sẽ thu được kết quả là một giá trị được đặt trong một cấu trúc dữ liệu vỏ bọc. Sau đó, để nối tiếp việc sử dụng kết quả này cho một hàm callback sẽ yêu cầu một trong hai khả năng:

Hoặc là callback đã được định nghĩa từ trước đó với dự định sẽ làm việc trực tiếp với kiểu cấu trúc vỏ bọc và có tên định danh rõ ràng.
Hoặc là callback là một hàm vô danh được tạo ra ngay tại vị trí viết code thực hiện thao tác I/O.

Tuy nhiên, thông thường thì khi thiết kế một cấu trúc dữ liệu vỏ bọc - ví dụ như Maybe hay List - chúng ta thường sẽ viết code tổng quát generic chứ không biết trước được kiểu dữ liệu sẽ được đặt vào trong cấu trúc này. Còn khi thiết kế một kiểu dữ liệu biểu thị giá trị bản ghi data record, thì chúng ta lại thiết kế các hàm đi kèm không biết trước tới kiểu cấu trúc vỏ bọc nào sẽ được sử dụng trong những tình huống cụ thể khác nhau.

Chính vì vậy nên callback sau mỗi thao tác I/O thường là sẽ không quan tâm tới cấu trúc của lớp vỏ bọc, bất kể là đã được định nghĩa trước trong module của data record hay được định nghĩa ở dạng lambda ngay tại vị trí nhận kết quả I/O. Và như vậy thì ý 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 vỏ bọc 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 thì lamda sẽ chỉ cần 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 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. Ví dụ:

arrayFunc.bind (arrayValue)
hoặc Array.bind (arrayValue, arrayFunc)

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 là:

Một hàm liên kết Associative để kết hợp các giá trị cùng kiểu dữ liệu.
Một giá trị đặc trưng Identity vô nghĩa đối với logic kết hợp của hàm Associative kể trên.
Và một hàm tập hợp concat 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 và Identity.

Đầ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.

module Class exposing (..)

type alias Monoid a =
   { append : a -> a -> a
   , empty  : a
   , concat : List a -> 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 tập hợp concat để liên kết danh sách các giá trị.

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ụ, thay vì chỉ tạo ra một module NumberExt cho hai giao diện monoid kể trên, thì chúng ta có thể có module Sum và module Product.

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.

module Sum exposing (..)
import Class exposing (..)

instanceMonoid : Class.Monoid number
instanceMonoid = Monoid append empty concat

append : number -> number -> number
append x y = x + y

empty : number
empty = 0

concat : List number -> number
concat numberList =
   case numberList of
      (firstValue :: restList) -> append firstValue (concat restList)
      [] -> 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 recursion là phương thức duy nhất để thực hiện công việc chuyển đổi một danh sách thành một giá trị biểu trưng duy nhất. Và 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 Sum 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 trong logic rẽ nhánh kết thúc đệ quy; Hoặc, khi tính tích Product 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, array.reduceRight; Và hàm concat của Monoid 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.

concat dataList = List.foldr append empty dataList

Elm Translate: Việc kết hợp concat một tập dữ liệu dataList có thể được xử lý bằng cách = thu gọn tập dữ liệu dataList bắt đầu từ phía bên phải List.foldr sử dụng logic kết hợp các giá trị của append vào giá trị đích khởi tạo là empty.

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 HOF ở 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à các trình điều khiển Browser.element và Browser.application, 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.

[Declarative Programming + Elm] Bài 16 - URL Parser Module

Monad

Monoid

Table of contents