Hàm Fix và Định Nghĩa Không Rời Khỏi

Trong bộ thư viện chuẩn của Haskell, module Data.Function cung cấp hàm fix. Đây là công cụ cơ bản dùng để đóng gói các phép tính đệ quy mà không cần dùng đến từ khóa rec hay định nghĩa tên hàm trước. Về mặt toán học, nó hoạt động như một tổ hợp tử điểm bất động (fixed-point combinator).

Định nghĩa của fix được diễn đạt rất ngắn gọn qua biểu thức sau:

fix :: (a -> a) -> a
fix f = let x = f x in x

Mặc dù cú pháp trông có vẻ mâu thuẫn do x được định nghĩa bằng chính nó, điều này trở nên khả thi nhờ tính chất đánh giá trễ (lazy evaluation) của Haskell. Khi khai triển biểu thức, ta sẽ thấy chuỗi ứng dụng của hàm f kéo dài vô tận:

fix f
= let x = f x in x
= let x = f x in f x
= let x = f x in f (f x)
= ... 
= f . f . f . ... $ x

Vòng lặp này chỉ thực sự kết thúc khi kết quả trả về đã hội tụ hoặc khi hàm f trả về một cấu trúc dữ liệu hoàn chỉnh dựa trên tham số đầu vào chưa được tính toán.

Dưới đây là ví dụ minh họa cách fix hoạt động với hằng và danh sách vô hạn:

-- Trả về ngay lập tức vì const không quan tâm đối số
Prelude> fix (const "Done")
"Done"

-- Tạo danh sách [1, 1, 1, ...]
Prelude> fix (1:)
[1, 1, 1, ...

Tương ứng với sự rút gọn:

fix (const "Done") 
= let x = const "Done" x in x 
= let x = "Done" in x 
= "Done"

Chuyển Đổi Đệ Quy Sang Phi Đệ Quy

Sức mạnh lớn nhất của fix nằm ở khả năng biến đổi các hàm tự gọi (recursive) thành dạng không chứa tên hàm gọi lại trong thân hàm, thay vào đó sử dụng tham số truyền vào. Điều này hữu ích cho việc tối ưu hóa hoặc phân tích luồng dữ liệu.

Xét bài toán tính giai thừa. Phiên bản đệ quy truyền thống:

tinhGiaiThua kieuSo 
  | kieuSo == 0 = 1
  | otherwise   = kieuSo * tinhGiaiThua (kieuSo - 1)

Sử dụng fix, phiên bản phi đệ quy tương đương như sau:

tinhGiaiThuaNonRec = fix (\funcSelf num -> 
    if num == 0 
    then 1 
    else num * funcSelf (num - 1)
)

So sánh kiểu dữ liệu (type signature) giữa hai cách:

-- Dạng đệ quy thường
:tinhGiaiThua :: (Num p, Eq p) => p -> p

-- Dùng fix
:tinhGiaiThuaNonRec :: (Num p, Eq p) => p -> p
:t (\funcSelf num -> ...) :: (Eq p, Num p) => (p -> p) -> p -> p

Tiếp tục phân tích quy trình chuyển đổi thủ công cho thấy vai trò của tham số funcSelf. Nó đóng vai trò là chính hàm tinhGiaiThua nhưng được truyền xuống dưới dạng đối số. Quá trình tính toán vẫn đảm bảo đúng nguyên lý đệ quy:

fix (\funcSelf num -> ...) 3
= (\funcSelf num -> ...) (fix ...) 3
= 3 * (\funcSelf num -> ...) (fix ...) 2
= 3 * 2 * (\funcSelf num -> ...) (fix ...) 1
= 6

Lộ Trình Biến Đổi Hàm Đệ Quy

Để áp dụng kỹ thuật này một cách có hệ thống, bạn có thể tuân theo quy tắc viết tắt (short-hand) hoặc quy tắc đặt tên (named function).

Quy tắc Lambda (ẩn danh):

1. Tổng hợp mọi nhánh của hàm về một khối duy nhất (sử dụng if/else hoặc case).
2. Di chuyển tất cả tham số của hàm gốc sang phần thân (trái sang phải).
3. Thêm một tham số mới (ví dụ: selfFunc) đứng trước danh sách tham số gốc.
4. Gọi lại chính hàm cũ bằng selfFunc trong phần thân.
5. Gán kết quả cho fix.

Áp Dụng Vào Hàm Xử Lý Danh Sách

Quy tắc trên cũng áp dụng hiệu quả cho các hàm xử lý cấu trúc dữ liệu, chẳng hạn như map. Dưới đây là cách tái cấu trúc hàm dongChuyenMang:

Phiên bản ban đầu:

dongChuyenMang :: (a -> b) -> [a] -> [b]
dongChuyenMang _ []     = []
dongChuyenMang f (x:xs) = f x : dongChuyenMang f xs

Phiên bản dùng Fix (cách 1 - Lambda đơn giản):

dongChuyenMangV2 = fix $ \selfFunc f list ->
    case list of
        []       -> []
        (x:xs)   -> f x : selfFunc f xs

Phiên bản dùng Fix (cách 2 - Tham số con trỏ):

Bạn có thể coi f là phần cố định, chỉ lấy list làm tham số đệ quy. Lúc này selfFunc nhận vào danh sách con:

dongChuyenMangV3 f = fix $ \selfFunc list ->
    case list of
        []       -> []
        (x:xs)   -> f x : selfFunc xs

Mối Liên Hệ Giữa Điểm Bất Động và Đệ Quy

Ở góc độ lý thuyết tổ hợp tử (combinator), fix tìm kiếm nghiệm y sao cho f y = y. Đối với hàm bậc 1, điểm bất động là một hằng số; với hàm bậc cao hơn (higher-order), điểm bất động là chính hàm số đó.

Tính chất cốt lõi là:

fix f = f (fix f)

Nếu coi hàm \funcSelf n -> ... là một tác nhân (operator) sinh ra hành vi đệ quy, thì hàm đệ quy gốc chính là điểm bất động của tác nhân này.

Ví dụ thực tế trong tính toán số học bao gồm việc tìm nghiệm của phương trình cos y = y. Thay vì viết hàm dò tìm lặp thủ công, ta dùng fix để mô tả quá trình hội tụ tự nhiên.

-- Tìm nghiệm của cos(x) == x
timNghiemCos :: Double -> Double
timNghiemCos start = 
    fix (\f val -> 
            if abs (cos val - val) < 1e-6 
            then val 
            else f (cos val)
         ) start

Thực thi trên GHCi sẽ cho kết quả hội tụ về 0.739085... bất kể bắt đầu từ giá trị nào.

*Main> timNghiemCos 3
0.7390851332151607
*Main> cos it == it
True

Tóm Tắt Cơ Chế Toán Học

Việc chuyển đổi giữa đệ quy quy ước và dùng fix không thay đổi hành vi thực thi mà chỉ thay đổi biểu diễn ngữ nghĩa. Khi viết factorial = fix factorial', ta đang khẳng định rằng factorial là điểm bất động của hàm factorial'.

factorial = \n -> if n==0 then 1 else n * factorial (n-1)
-- Tương đương với
factorial = fix (\f n -> if n==0 then 1 else n * f (n-1))

Điều này chứng tỏ mọi hàm đệ quy đều là trường hợp đặc biệt của điểm bất động, nơi hàm số được gọi lại bởi chính hàm sinh ra nó thông qua cơ chế đánh giá trễ và mở rộng vô hạn của fix.