Chương 6: Hàm cấp cao

Trở về Mục lục cuốn sách

Các hàm trong Haskell có thể nhận các tham số là các hàm rồi trả lại giá trị cũng là các hàm. Một hàm thực hiện một trong hai công việc trên được gọi là hàm cấp cao. Hàm cấp cao không chỉ là một phần kinh nghiệm lập trình Haskell, mà còn có thể nói chính là kinh nghiệm dùng ngôn ngữ này. Bạn sẽ nhận thấy rằng nếu muốn định nghĩa quy trình tính toán bằng cách định nghĩa cần tính thứ gì chứ không phải định nghĩa các bước thay đổi trạng thái hoặc có thể là tính lặp, thì trong những trường hợp như vậy hàm cấp cao là không thể thay thế. Chúng là công cụ mạnh giúp ta giải quyết bài toán và suy nghĩ về chương trình.

sun

Hàm curry

Trong Haskell, mỗi hàm chính thức chỉ nhận một tham số. Vậy bằng cách nào mà đến giờ ta đã có thể định nghĩa và dùng một số hàm nhận nhiều tham số? À, đó là một mẹo khéo léo! Đến giờ, tất cả các hàm mà chấp nhận nhiều tham số đều là hàm curry. Đó là cái gì? Bạn sẽ hiểu rõ nhất qua ví dụ sau. Hãy xét một bạn tốt, hàm max của ta. Có vẻ như nó nhận hai tham số rồi trả về thứ lớn hơn. Khi viết max 4 5, đầu tiên ta đã tạo một hàm để nhận vào một tham số rồi trả lại, hoặc là 4 hoặc là tham số đó, tùy theo số nào lớn hơn. Tiếp theo, 5 được áp dụng cho hàm này và hàm này trả cho ta kết quả mong muốn. Điều này nghe hơi rườm rà nhưng thực ra lại là một khái niệm rất hay. Hai cách gọi hàm sau là tương đương:

ghci> max 4 5
5
ghci> (max 4) 5
5

haskell curry

Việc đặt một dấu cách giữa hai thứ chỉ đơn giản là áp dụng hàm. Dấu cách là một kiểu toán tử và nó có độ ưu tiên cao nhất. Ta hãy kiểm tra kiểu của max. Nó là max :: (Ord a) => a -> a -> a. Cũng có thể viết dưới dạng max :: (Ord a) => a -> (a -> a). Cũng có thể diễn đạt là: max nhận vào một a rồi trả lại (tức là dấu ->) một hàm, mà hàm này nhận một a rồi trả lại một a. Đó là lý do tại sao kiểu được trả lại cũng như các tham số của hàm chỉ đơn giản được ngăn cách bởi dấu mũi tên.

Vậy thì điều này có gì lợi cho ta? Nói nôm na, nếu ta gọi một hàm mà đưa thiếu tham số, ta sẽ thu được một hàm áp dụng từng phần, nghĩa là một hàm nhận vào tất cả bao nhiêu tham số mà ta để thừa lại. Bằng cách áp dụng từng phần (gọi hàm với ít tham số, nếu bạn muốn) bạn có thể tiện tay tạo ra các hàm mỗi khi cần đến, để từ đó truyền chúng vào các hàm khác hoặc ghép số liệu cho chúng.

Hãy xem một hàm đơn giản bất ngờ sau đây:

multThree :: (Num a) => a -> a -> a -> a
multThree x y z = x * y * z

Điều gì thực ra đã xảy đến khi ta viết multThree 3 5 9 hay ((multThree 3) 5) 9? Trước tiên, 3 được áp dụng cho multThree, vì chúng được ngăn giữa bởi một dấu cách. Kết quả là tạo ra một hàm mà hàm này nhận vào một tham số rồi trả lại một hàm khác. Vì vậy khi 5 được âp dụng cho hàm đó, một hàm mới được tạo ra, hàm này nhận một tham số rồi nhân nó với 15. 9 được áp dụng cho hàm mới này và kết quả là 135 gì đó. Hãy nhớ rằng kiểu của hàm trên cũng có thể được viết là multThree :: (Num a) => a -> (a -> (a -> a)). Thứ đứng đằng trước dấu -> là một tham số mà hàm nhận vào và thứ đứng đằng sau dấu này là cái mà hàm trả lại. Vì vậy hàm của ta nhận vào một a rồi trả lại một hàm có kiểu (Num a) => a -> (a -> a). Tương tự, hàm này nhận vào một a rồi trả lại một hàm có kiểu (Num a) => a -> a. Và hàm này, cuối cùng, sẽ chỉ nhận một a và trả lại một a. Hãy nhìn này:

ghci> let multTwoWithNine = multThree 9
ghci> multTwoWithNine 2 3
54
ghci> let multWithEighteen = multTwoWithNine 2
ghci> multWithEighteen 10
180

Bằng cách gọi hàm và đưa thiếu tham số, nói nôm na là ta đang tạo ra hàm mới khi cần đến. Ta sẽ làm gì nếu muốn tạo ra một hàm nhận vào một con số rồi so sánh nó với 100? Ta có thể viết như sau:

compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred x = compare 100 x

Nếu ta gọi nó với 99, nó sẽ trả lại GT. Đơn giản. Lưu ý rằng x đứng bên tay phải trong cả hai vế của phương trình. Bây giờ ta hãy hình dung xem compare 100 trả lại thứ gì. Nó trả lại một hàm mà hàm này nhận vào một con số rồi so sánh số đó với 100. Wow! Chẳng phải đó là hàm ta mong muốn đó sao? Ta có thể viết lại như sau:

compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred = compare 100

Lời khai báo kiểu vẫn giữ nguyên như vậy, vì compare 100 trả về một hàm. Hàm compare có kiểu (Ord a) => a -> (a -> Ordering) và khi được gọi với 100 thì trả lại một (Num a, Ord a) => a -> Ordering. Ràng buộc về lớp kèm thêm đã xuất hiện ở đây vì 100 cũng thuộc về lớp Num.

Yo! Hãy chắc chắn rằng bạn hiểu được cách hoạt động của hàm curry và hàm từng phần vì chúng rất quan trọng!

Các hàm trung tố cũng có thể được áp dụng từng phần bằng cách dùng lát cắt.. Để cắt một hàm trung tố, ta chỉ cần kẹp chúng giữa cặp ngoặc đơn sau khi cấp cho một vế tham số. Bằng cách này ta sẽ tạo ra một hàm; hàm này nhận vào một tham số rồi sau đó áp dụng cho vế đang bị thiếu. Một ví dụ về một hàm rất nhỏ như sau:

divideByTen :: (Floating a) => a -> a
divideByTen = (/10)

Việc gọi, chẳng hạn, divideByTen 200 là tương đương với việc viết 200 / 10, và cũng giống như (/10) 200. Một hàm có nhiệm vụ kiểm tra xem kí tự nhập vào có phải là chữ cái viết in hay không:

isUpperAlphanum :: Char -> Bool
isUpperAlphanum = (`elem` ['A'..'Z'])

Điều đặc biệt duy nhất về các lát cắt là việc dùng -. Theo định nghĩa về lát cắt thì lẽ ra (-4) sẽ tạo ra một hàm để nhận vào một số rồi trừ số đó đi 4. Tuy nhiên, để cho tiện, (-4) có nghĩa là âm 4. Vì vậy nếu bạn muốn tạo một hàm để bớt 4 đi từ tham số nhận vào, thì hãy áp dụng từng phần hàm subtract như sau: (subtract 4).

Điều gì sẽ xảy ra nếu ta thử viết mỗi multThree 3 4 trong GHCI thay vì gắn nó với một tên bằng let hay truyền nó vào một hàm khác?

ghci> multThree 3 4
<interactive>:1:0:
    No instance for (Show (t -> t))
      arising from a use of `print' at <interactive>:1:0-12
    Possible fix: add an instance declaration for (Show (t -> t))
    In the expression: print it
    In a 'do' expression: print it

GHCI báo cho ta biết rằng biểu thức vừa nhập đã tạo ra một hàm có kiểu a -> a nhưng không biết làm thế nào để in nó ra màn hình. Các hàm không phải là đối tượng của lớp Show, vì vậy ta không thể nhận được một chuỗi đẹp đẽ biểu diễn cho hàm. Còn khi ta gõ, chắng hạn như, 1 + 1từ dấu nhắc GHCI prompt, ban đầu nó sẽ tính được 2 rồi gọi show đối với 2 để thu được một dạng hiển thị con số đó. Và dạng hiển thị của 2 chính là chuỗi "2", và nó sẽ được in ra màn hình cho chúng ta thấy.

Một số cấp cao đang dưới lệnh của ta

Hàm có thể nhận các hàm khác làm tham số rồi trả lại các hàm khác nữa. Để minh họa cho điều này, ta sẽ tạo một hàm, hàm này nhận vào một hàm rồi áp dụng nó hai lần cho một đối tượng nào đó!

applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)

rocktopus

Trước tiên, hãy lưu ý khai báo kiểu. Trước đây, ta chưa cần dùng cặp ngoặc đơn vì -> bản thân nó đã gắn với đối tượng bên phải. Còn bây giờ, ngoặc đơn là bắt buộc; để chỉ rằng tham số thứ nhất là một hàm nhận vào một thứ gì dó rồi trả lại cũng thứ đó. Tham số thứ hai là một thứ cùng kiểu, và giá trị trả lại cũng cùng kiểu. Ta có thể đọc lời khai báo kiểu này theo cách curry, nhưng để tránh bị nhức đầu ta chỉ nói rằng hàm này nhận vào hai tham số rồi trả lại một thứ. Tham số đầu tiên là một hàm (có kiểu a -> a) và tham số thứ hai cũng là a đó. Hàm này có thể là Int -> Int hay String -> String hoặc thế nào cũng được.Nhưng rồi tham số thứ hai phải có cùng kiểu đó.

Lưu ý: Từ nay trở đi, ta sẽ nói rằng các hàm nhận vài tham số mặc dù mỗi hàm thật ra chỉ nhận một tham số rồi trả lại một hàm áp dụng từng phần cho đến tận khi ta đạt tới một hàm trả lại một giá trị cụ thể. Vì vậy, để đơn giản, ta sẽ nói rằng a -> a -> a nhận vào hai tham số, mặc dù ta đã biết rằng bên trong nó, chuyện gì đang diễn ra.

Phần thân hàm khá đơn giản. Ta chỉ việc dùng tham số f là một hàm, áp dụng x cho nó bằng việc lấy dấu cách để ngăn giữa chúng, rồi áp dụng kết quả thu được cho f một lần nữa. Dù sao, ta cứ nghịch hàm này đã:

ghci> applyTwice (+3) 10
16
ghci> applyTwice (++ " HAHA") "HEY"
"HEY HAHA HAHA"
ghci> applyTwice ("HAHA " ++) "HEY"
"HAHA HAHA HEY"
ghci> applyTwice (multThree 2 2) 9
144
ghci> applyTwice (3:) [1]
[3,3,1]

Sự kì diệu và tiện dụng của việc áp dụng hàm từng phần đã rõ ràng. Nếu hàm được viết yêu cầu chúng ta trả lại một hàm chỉ nhận một tham số, thì ta có thể đơn giản là áp dụng từng phần một hàm đến điểm mà nó chỉ còn nhận một tham số, rồi truyền hàm này đi.

Bây giờ ta sẽ dùng cách lập trình hàm cấp cao để lập một hàm rất hữu ích đã sẵn có trong thư viện tiêu chuẩn. Nó được gọi là zipWith. Hàm này nhận vào các tham số gồm có một hàm và hai danh sách rồi nối hai danh sách lại bằng cách áp dụng hàm giữa hai phần tử có thứ tự tương ứng. Sau đây là cách ta lập nó:

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

Hãy nhìn vào khai báo kiểu. Tham số thứ nhất là một hàm nhận vào hai đối tượng rồi trả lại một đối tượng thứ ba. Chúng không nhất thiết, nhưng có thể cùng kiểu với nhau. Các tham số thứ hai và thứ ba đều là danh sách. Kết quả cũng là một danh sách. Danh sách thứ nhất phải là một danh sách chứa a, vì hàm kết nối nhận vào các a làm đối số thứ nhất. Danh sách thứ hai phải chứa b, vì tham số thứ hai trong hàm kết nối có kiểu là b. Kết quả là một danh sách có chứa các c. Nếu lời khai báo kiểu của một hàm nói rằng nó chấp nhận một hàm a -> b -> c làm tham số, thì nó cũng sẽ chấp nhận một hàm a -> a -> a, nhưng ngược lại thì không! Hãy nhớ rằng khi bạn lập các hàm, đặc biệt là hàm cấp cao, mà chưa cảm thấ chắc chắn về kiểu, thì bạn có thể chỉ cần thử bỏ qua khai báo kiểu rồi kiểm tra xem Haskell suy luận nó thế nào bằng cách dùng :t.

Hành động trong hàm này khá giống với hàm zipthông thường. Điều kiện biên vẫn y như vậy, chỉ khác là có thêm một đối số, đó là hàm nối, nhưng đối số đó không có ý nghĩa gì trong điều kiện biên, vì vậy ta chỉ cần dùng dấu _ để kí hiệu nó. Và phần thân hàm ở dạng mẫu cuối cùng cũng tương tự với zip, song nó không phải (x,y), mà là f x y. Một hàm bậc cao có thể được dùng cho một loạt những nhiệm vụ khác nhau nếu nó đủ độ tổng quát. Sau đây là một màn biểu diễn cho thấy tất cả những việc mà hàm zipWith' vừa lập có thể thực hiện:

ghci> zipWith' (+) [4,2,5,6] [2,6,2,3]
[6,8,7,9]
ghci> zipWith' max [6,3,2,1] [7,3,1,5]
[7,3,2,5]
ghci> zipWith' (++) ["foo ", "bar ", "baz "] ["fighters", "hoppers", "aldrin"]
["foo fighters","bar hoppers","baz aldrin"]
ghci> zipWith' (*) (replicate 5 2) [1..]
[2,4,6,8,10]
ghci> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]]
[[3,4,6],[9,20,30],[10,12,12]]

Như bạn đã thấy, một hàm bậc cao có thể được dùng theo những cách rất linh hoạt. Lập trình mệnh lệnh thường dùng những thứ như vòng lặp for, vòng lặp while, gán một giá trị cho biến, kiểm tra trạng thái của nó, v.v. để đạt được một ddiefu gì đó, rồi bọc nó trong một giao diện, như một hàm. Lập trình hàm thì dùng các hàm bậc cao để đai diện cho các kiểu mẫu chung, như là xem xét hai danh sách theo từng cặp rồi thực hiện tính toán gì đó với những cặp đó, hoặc lấy ra một tập hợp đáp án rồi loại đi những cái không cần thiết.

Ta sẽ lập một hàm khác đã có sẵn trong thư viện chuẩn, hàm flip. Flip đơn giản là nhận vào một hàm rồi trả lại một hàm mới giống như hàm ban đầu, chỉ khác là hai đối số đã bị đổi chỗ. Ta có thể lập nó như sau:

flip' :: (a -> b -> c) -> (b -> a -> c)
flip' f = g
    where g x y = f y x

Dựa vào lời khai báo kiểu, ta nói rằng nó nhận một hàm, hàm này nhận một a và một b rồi trả về một hàm nhận một b và một a. Nhưng vì các hàm mặc định là được curry, nên cặp ngoặc tròn thứ hai thực sự không cần thiết, vì -> mặc định là gắn với đối tượng bên phải nó. (a -> b -> c) -> (b -> a -> c) cũng giống như (a -> b -> c) -> (b -> (a -> c)), và cũng giống như (a -> b -> c) -> b -> a -> c. Ta đã viết là g x y = f y x. Nếu điều này đúng, thì f y x = g x y cũng đúng, phải vậy không nhỉ? Ghi nhớ điều đó, ta có thể định nghĩa hàm này theo cách thậm chí còn đơn giản hơn.

flip' :: (a -> b -> c) -> b -> a -> c
flip' f y x = f x y

Ở đây, ta tận dụng được đặc điểm curry của hàm. Khi ta gọi flip' f không có tham số yx, nó sẽ trả lại một f nhận vào hai tham số, nhưng gọi các tham số này theo thứ tự lật lại. Mặc dù các hàm đã lật thường được truyền vào các hàm khác, ta vẫn có thể tận dụng curry khi lập các hàm cấp cao bằng cách nghĩ trước và viết ra kết quả sau cùng sẽ là gì nếu như hàm được gọi để áp dụng triệt để.

ghci> flip' zip [1,2,3,4,5] "hello"
[('h',1),('e',2),('l',3),('l',4),('o',5)]
ghci> zipWith (flip' div) [2,2..] [10,8,6,4,2]
[5,4,3,2,1]

Các hàm map và filter

map [“ánh xạ”] nhận vào một hàm và một danh sách rồi áp dụng hàm đó cho từng phần tử thuộc danh sách, để tạo ra một danh sách mới. Ta hãy xem dấu ấn kiểu của hàm map là gì và nó được định nghĩa thế nào.

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

Dấu ấn kiểu nói rằng nó nhận vào một hàm, hàm này nhận một a và trả lại một b, cùng một danh sách các a, rồi trả lại một danh sách các b. Điều hay là chỉ cần nhìn vào một dấu ấn kiểu hàm, đôi khi bạn có thể nói được rằng nó làm gì. map là một trong số các hàm cấp cao đa năng như vậy; nó có thể được dùng theo muôn vàn những cách khác nhau. Sau đây là màn trình diễn của hàm này:

ghci> map (+3) [1,5,3,1,6]
[4,8,6,4,9]
ghci> map (++ "!") ["BIFF", "BANG", "POW"]
["BIFF!","BANG!","POW!"]
ghci> map (replicate 3) [3..6]
[[3,3,3],[4,4,4],[5,5,5],[6,6,6]]
ghci> map (map (^2)) [[1,2],[3,4,5,6],[7,8]]
[[1,4],[9,16,25,36],[49,64]]
ghci> map fst [(1,2),(3,5),(6,3),(2,6),(2,5)]
[1,3,6,2,2]

Có thể bạn đã nhận ra mỗi phép tính này có thể thực hiện được bằng cách gộp danh sách. map (+3) [1,5,3,1,6] cũng giống như viết [x+3 | x <- [1,5,3,1,6]]. Tuy nhiên, dùng map thì dễ đọc hơn nhiều trong những trường hợp bạn chỉ áp dụng một hàm nào đó lên các phần tử của một danh sách, đặc biệt là khi bạn phải tính map của map, vì khi đó nếu viết gộp danh sách thì có quá nhiều ngoặc vuông sẽ gây rối tung lên.

filter [“lọc”] là một hàm nhận vào một vị ngữ (một hàm có nhiệm vụ thông báo một điều gì đó là đúng hay sai; trong trường hợp này là mọt hàm trả lại giá trị boole) và một danh sách rồi trả về danh sách các phần tử thỏa mãn vị ngữ này. Dấu ấn kiểu và cách thành lập hàm như sau:

filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs) 
    | p x       = x : filter p xs
    | otherwise = filter p xs

Khá đơn giản. Nếu p x được lượng giá là True, thì phần tử sẽ được đứng trong danh sách mới. Nếu không, nó phải đứng ngoài. Một vài ví dụ sử dụng:

ghci> filter (>3) [1,5,3,2,1,6,4,3,2,1]
[5,6,4]
ghci> filter (==3) [1,2,3,4,5]
[3]
ghci> filter even [1..10]
[2,4,6,8,10]
ghci> let notNull x = not (null x) in filter notNull [[1,2,3],[],[3,4,5],[2,2],[],[],[]]
[[1,2,3],[3,4,5],[2,2]]
ghci> filter (`elem` ['a'..'z']) "u LaUgH aT mE BeCaUsE I aM diFfeRent"
"uagameasadifeent"
ghci> filter (`elem` ['A'..'Z']) "i lauGh At You BecAuse u r aLL the Same"
"GAYBALLS"

Tất cả những điều này đều có thể làm bằng gộp danh sách có sử dụng vị ngữ. Chẳng có quy định cứng nhắc buộc bạn khi nào phải dùng mapfilter thay vì dạng gộp danh sách cả, bạn tự quyết định xem cách nào dễ đọc hơn tùy thuộc vào mã lệnh đang viết và hoàn cảnh cụ thể. Cách dùng filter tương đương với việc đưa nhiều vị ngữ vào trong dạng gộp danh sách là: lọc nhiều lần, hoặc nối các vị ngữ bằng hàm logic &&.

Bạn còn nhớ hàm quicksort từ chương trước chứ? Ta đã dùng một dạng gộp danh sách để lọc ra các phần tử danh sách nhỏ hơn (hoặc bằng), và các phần tử lớn hơn, phần tử chốt. Ta có thể thực hiện điều này với cách viết mã lệnh dễ đọc hơn bằng filter:

quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =   
    let smallerSorted = quicksort (filter (<=x) xs)
        biggerSorted = quicksort (filter (>x) xs) 
    in  smallerSorted ++ [x] ++ biggerSorted

map

Map và filter là nguyên liệu cốt yếu trong tay người lập trình hàm. Ừ. Sẽ chẳng sao nếu bạn thực hiện với các hàm mapfilter hay dạng gộp danh sách. Hãy nhớ lại cách ta giải bài toán tìm những tam giác vuông với chu vi cho trước. Nếu lập trình mệnh lệnh, ta có thể đã giải bằng cách lồng ba vòng lặp rồi kiểm tra xem nếu tổ hợp ba cạnh hiện thời có thỏa mãn điều kiện tam giác vuông và với chu vi đúng hay không. Nếu thỏa mãn, ta đã in kết quả ra màn hình hoặc ghi vào nơi khác. Trong lập trình hàm, dạng mẫu đó có thể thực hiện được với map và filter. Bạn tạo ra một hàm nhận vào một giá trị rồi trả lại kết quả nào đó. Ta đặt ánh xạ hàm này trên một danh sách các giá trị rồi lọc lấy danh sách cần tìm từ những kết quả thỏa mãn yêu cầu. Nhờ tính lười biếng của Haskell, ngay cả khi bạn ánh xạ thứ gì lên danh sachs nhiều lần và lọc nó nhiều lần đi nữa, nó cũng chỉ duyệt qua danh sách đúng một lần.

Ta hãy tìm số lớn nhất, nhỏ hơn 100000 và chia hết cho 3829. Để làm điều này, ta sẽ chỉ cần lọc một tập hợp các khả năng mà ta biết chắc rằng đáp số nằm đâu đó lẫn ở trong.

largestDivisible :: (Integral a) => a
largestDivisible = head (filter p [100000,99999..])
    where p x = x `mod` 3829 == 0

Trước hết, ta hãy tạo một danh sách tất cả số dưới 100000, theo chiều giảm dần. Sau đó ta lọc danh sách này bằng vị ngữ thích hợp và vì các số đã được xếp giảm dần, nên số đầu tiên thỏa mãn vị ngữ sẽ là phần tử thứ nhất trong danh sách sau khi lọc. Ta thậm chí còn không cần dùng một danh sách hữu hạn làm tập hợp khởi đầu nữa. Đó là vì đã có tính lười biếng của Haskell: sau này kết thúc ta chỉ lấy phần tử đầu của danh sách sau khi lọc, nên chẳng bận tâm xem danh sách đó là hữu hạn hay vô hạn nữa. Việc lượng giá kết thúc khi tìm được nghiệm số đầu tiên.

Tiếp theo, ta sẽ tìm tổng của tất cả bình phương lẻ nhỏ hơn 10000. Nhưng trước hết, vì sẽ dùng nó trong lời giải, nên ta giới thiệu hàm takeWhile. Hàm này nhận vào một vị ngữ và một danh sách rồi duyệt từ đầu danh sách, trả lại những phần tử nào mà vị ngữ vẫn còn được thỏa mãn. Một khi đạt tới phần tử không thỏa mãn vị ngữ thì hàm sẽ dừng lại. Nếu ta muốn lấy từ đầu tiên của chuỗi "elephants know how to party", ta có thể viết takeWhile (/=' ') "elephants know how to party" và nó sẽ trả lại "elephants". Được rồi. Tổng của tất cả những bình phương nhỏ hơn 10000 và là số lẻ. Trước hết, ta bắt đầu bằng cách ánh xạ hàm (^2) lên danh sách vô hạn [1..]. Sau đó ta lọc chúng để chỉ lấy những số lẻ. Rồi tiếp theo ta sẽ lấy những phần tử từ danh sách khi chúng còn nhỏ hơn 10000. Cuối cùng, ta tính tổng của danh sách đó. Thậm chí ta còn không phải định nghĩa một hàm cho toàn bộ công việc này, ta có thể gõ vào một dòng lệnh trong GHCI:

ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))
166650

Tuyệt vời! Bắt đầu bằng một số liệu ban đầu nào đó (danh sách vô hạn chứa tất cả những số tự nhiên), ta ánh xạ lên nó, lọc nó rồi cắt bớt nó đến khi được danh sách như ý, tiếp theo ta chỉ cần lấy tổng chúng. Ta cũng đã có thể viết bằng dạng gộp danh sách sau:

ghci> sum (takeWhile (<10000) [n^2 | n <- [1..], odd (n^2)])
166650

Việc chọn cách nào đẹp hơn chỉ là vấn đề ý thích cá nhân. Mọt lần nữa, tính lười biếng của Haskell đã giúp điều này khả thi. Ta có thể ánh xạ lên và lọc một danh sách vô hạn, vì thật ra nó sẽ chẳng được ánh xạ và lọc bỏ ngay, mà các hành động này sẽ được hoãn lại. Chỉ khi ta buộc Haskell phải tính tổng thì hàm sum mới báo cho hàm takeWhile rằng nó cần những con số đó. takeWhile lại buộc các công đoạn lọc và ánh xạ phải tiến hành, nhưng chỉ tiếp diễn đến khi đạt được con số bằng hoặc lớn hơn 10000.

Ở bài toán tiếp theo, ta sẽ tính các chuỗi Collatz. Ta nhận vào một số tự nhiên. Nếu nó chẵn, hãy chia cho 2. Nếu lẻ, hãy nhân lên 3 rồi cộng với 1. Đem số thu được và áp dụng lại cách tính như trên, và lại tạo ra số mới, rồi cứ tiếp tục như vậy. Tóm lại, ta sẽ được một dãy số. Người ta cho rằng dù bắt đầu với con số bất kì, chuỗi cũng sẽ kết thúc bằng số 1. Vì vậy, nếu ta bắt đầu bằng số 13, thì sẽ thu được dãy sau: 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. 13*3 + 1 bằng 40. 40 chia 2 bằng 20, v.v. Ta thấy rằng dãy này có 10 số.

Bây giờ điều ta muốn biết như sau:với tất cả các số khởi đầu, từ 1 đến 100, có bao nhiêu dãy số được tạo ra có độ dài hơn 15? Đầu tiên, ta hãy viết một hàm để tạo dãy số:

chain :: (Integral a) => a -> [a]
chain 1 = [1]
chain n
    | even n =  n:chain (n `div` 2)
    | odd n  =  n:chain (n*3 + 1)

Vì dãy kết thúc bằng 1, nên đó là điều kiện biên. Đây là một hàm đệ quy khá chuẩn mực.

ghci> chain 10
[10,5,16,8,4,2,1]
ghci> chain 1
[1]
ghci> chain 30
[30,15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]

A! Dường như nó hoạt động tốt. Và bây giờ, hàm sau sẽ trả lời ta câu hỏi vừa rồi:

numLongChains :: Int
numLongChains = length (filter isLong (map chain [1..100]))
    where isLong xs = length xs > 15

Ta ánh xạ hàm chain lên danh sách [1..100] để thu được một danh sách các dãy, mà mỗi dãy lại được biểu diễn dưới dạng danh sách. Sau đó, ta lọc chúng bằng một vị ngữ thực hiện kiểm tra xem chiều dài dãy có hơn 15 hay không. Một khi ta đã lọc xong, ta sẽ thấy có bao nhiêu dãy còn lại trong danh sách kết quả.

Lưu ý: Hàm này có kiểu là numLongChains :: Intlength trả lại một Int chứ không phải một Num a, điều này có lý do từ quá khứ. Nếu bạn muốn trả lại một Num a là dạng tổng quát hơn, ta có thể áp dụng fromIntegral lên con số chiều dài thu được.

Dùng map, ta có thể làm được những việc như map (*) [0..], nếu không cần có những lý do khác ngoài việc minh họa cách hoạt động của curry và cách mà các hàm (ấp dụng từng phần) cũng được truyền như giá trị vào các hàm khác, hoặc đưa và danh sách (bạn chỉ không thể biến chúng thành chuỗi). Đến giờ, ta mới chỉ ánh xạ các hàm nhận một tham số lên danh sách, như map (*2) [0..] để thu được một danh sách có kiểu (Num a) => [a], nhưng ta vẫn có thể viết map (*) [0..] mà không gặp phải vấn đề gì. Điều xảy ra ở đây là con số trong danh sách được áp dụng vào hàm *, có kiểu (Num a) => a -> a -> a. Việc chỉ áp dụng duy nhất một tham số cho hàm nhận hai tham số sẽ trả lại một hàm nhận một tham số. Nếu ta ánh xạ * lênh danh sách [0..], ta sẽ thu về một danh sách các hàm chỉ nhận một tham số, vì vậy (Num a) => [a -> a]. map (*) [0..] tạo ra một danh sách giống như điều ta thu được khi viết [(0*),(1*),(2*),(3*),(4*),(5*)...

ghci> let listOfFuns = map (*) [0..]
ghci> (listOfFuns !! 4) 5
20

Việc lấy phần tử có chỉ số 4 từ danh sách thu được sẽ trả lại một hàm tương đương với (4*). Và khi, ta chỉ việc áp dụng 5 cho hàm này. Nhự vậy cũng giống với viết (4*) 5 hoặc chỉ là 4 * 5.

Lambda

lambda

Lambda về cơ bản là các hàm khuyết danh; chúng được dùng đến khi ta cần một hàm nào đó dùng rồi bỏ đi ngay. Thông thường, ta tạo một lambda với mục đích duy nhất là truyền nó vào một hàm cấp cao. Để tạo một lambda, ta viết một dấu \ (vì nó trông giống như chữ lambda trong tiếng Hy Lạp nếu bạn nhìn thật chăm chú) tiếp theo là các tham số, được ngăn bởi dấu cách. Sau đó là dấu -> và rồi phần thân hàm. Ta thường khoanh chúng trong cặp ngoặc tròn, vì nếu không các hàm lambda sẽ kéo dài sang phải cho đến hết dòng.

Nếu bạn nhìn lên phía trên khoảng 5 inch (hay 13 cm), bạn sẽ thấy rằng ta đã dùng một cách gắn where trong hàm numLongChains để đạt mục đích duy nhất là truyền hàm isLong vào trong filter. Ồ, thay vì làm vậy, ta có thể dùng một lambda:

numLongChains :: Int
numLongChains = length (filter (\xs -> length xs > 15) (map chain [1..100]))

Lambda là biểu thức, vì vậy mà ta có thể truyền nó theo cách trên. Biểu thức (\xs -> length xs > 15) trả về một hàm, hàm này cho ta biết rằng liệu chiều dài của danh sách được truyền vào nó có hơn 15 hay không.

lamb

Những người chưa quen với cách hoạt động của curry và áp dụng từng phần thì hay dùng lambda những lúc thực ra không cần đến. Chẳng hạn, các biểu thức map (+3) [1,6,3,2]map (\x -> x + 3) [1,6,3,2] là tương đương vì cả (+3)(\x -> x + 3) đều là những hàm nhận vào một số rồi cộng 3 vào nó. Không cần nói thêm rằng việc tạo lambda trong trường hợp này là ngốc vì viết hàm từng phần thì dễ đọc hơn.

Cũng như hàm thông thường, lambda có thể nhận vào bất kì tham số nào:

ghci> zipWith (\a b -> (a * 30 + 3) / b) [5,4,3,2,1] [1,2,3,4,5]
[153.0,61.5,31.0,15.75,6.6]

Và cũng giống hàm thông thường, bạn có thể khớp mẫu với lambda. Khác biệt duy nhất là bạn không thể định nghĩa nhiều mẫu cho một tham số, chẳng hạn khiến cho các mẫu [](x:xs) cùng chung vào một tham số và rồi duyệt các giá trị qua chúng. Nếu một lần khớp mẫu thất bại trong lambda thì sẽ xuất hiện lỗi thực thi, vì vậy phải cẩn thận khi khớp mẫu bằng lambda!

ghci> map (\(a,b) -> a + b) [(1,2),(3,5),(6,3),(2,6),(2,5)]
[3,8,9,8,7]

Thông thường lambda được bao quanh bởi cặp ngoặc tròn, trừ khi chúng ta muốn chúng kéo dài đến hết dòng. Sau đây là một chi tiết thú vị: do việc các hàm được curry theo mặc định, hai điều sau là tương đương:

addThree :: (Num a) => a -> a -> a -> a
addThree x y z = x + y + z
addThree :: (Num a) => a -> a -> a -> a
addThree = \x -> \y -> \z -> x + y + z

Nếu ta định nghĩa một hàm như thế này, sẽ dễ thấy được tại sao lời khai báo kiểu lại như vậy. Có ba dấu -> trong cả lời khai báo kiểu và phương trình. Nhưng dĩ nhiên, cách viết hàm thứ nhất dễ đọc hơn nhiều; cách thứ hai chỉ là một mẹo để minh họa curry.

Tuy nhiên, cũng có lúc dùng cách viết này lại hay. Tôi nghĩ rằng hàm flip sẽ dễ đọc nhất khi ta định nghĩa như sau:

flip' :: (a -> b -> c) -> b -> a -> c
flip' f = \x y -> f y x

Mặc dù như vậy cũng giống với viết flip' f x y = f y x, ta đã làm rõ rằng, trong tuyệt đại đa số trường hợp, việc dùng hàm này đều nhằm để tạo nên hàm mới. Trường hợp thông dụng nhất với flip là gọi nó chỉ với tham số của hàm rồi truyền hàm tìm được vào trong một ánh xạ hoặc lọc. Vì vậy hãy dùng lambda theo cách này khi bạn muốn làm rõ rằng hàm được viết có ý nghĩa chủ yếu là để áp dụng từng phần và truyền đến một hàm khác như là tham số.

Chỉ có ngựa gấp giấy

folded bird

Hãy trở lại với đệ quy, ta phát hiện thấy một chủ đề xuyên suốt nhiều hàm đệ quy hoạt động trên danh sách. Thông thường, ta có điều kiện biên đối với danh sách rỗng. Ta đã giới thiệu mẫu x:xs và sau đó sẽ thực hiện thao tác nào đó liên quan đến một phần tử đơn lẻ và phần còn lại của danh sách. Hóa ra đây là một dạng mẫu rất thông dụng, vì vậy một số hàm rất tiện dụng đã được giới thiệu có kèm theo mẫu này. Những hàm này có tên là “gấp”. Chúng có dạng như hàm map, chỉ khác là thực hiện rút gọn danh sách thành một giá trị đơn lẻ.

Một hàm gấp nhận vào một hàm nhị phân, một giá trị khởi đầu (tôi thích gọi nó là giá trị tích lũy) và một danh sách để gấp. Hàm nhị phân này được gọi với giá trị tích lũy và phần tử đầu (hoặc cuối), rồi tạo ra một giá trị tích lũy mới. Sau đó, hàm nhị phân được gọi lại với giá trị tích lũy mới này và phần tử đầu/cuối mới, và cứ như vậy. Một khi ta đã đi qua toàn bộ danh sách, thì chỉ còn lại giá trị tích lũy, đó chính là giá trị mà danh sách đã được rút gọn về.

Trước hết, hãy xem hàm foldl, cũng được gọi là gấp trái. Nó gấp danh sách lại từ phía trái. Hàm nhị phân được áp dụng giữa giá trị đầu và phần tử đầu danh sách. Kết quả tạo ra một giá trị tích lũy mới, và hàm nhị phân được gọi với giá trị mới đó và phần tử kế tiếp, v.v.

Ta hãy lập lại hàm sum, nhưng trong lần này, ta sẽ dùng cách gấp fold thay vì đệ quy một cách minh bạch.

sum' :: (Num a) => [a] -> a
sum' xs = foldl (\acc x -> acc + x) 0 xs

Thử cái nào, một, hai, ba…:

ghci> sum' [3,5,2,1]
11

foldl

Ta hãy xét kĩ hơn cách làm việc của hàm fold này. \acc x -> acc + x là hàm nhị phân. 0 là giá trị khởi đầu còn xs là danh sách cần được gấp. Bây giờ, đầu tiên, 0 được dùng làm tham số acc cho hàm nhị phân và 3 được dùng làm tham số x (hoặc phần tử hiện thời). 0 + 3 cho ra 3 và nó trở thành giá trị tích lũy mới. Tiếp theo, 3 được dùng làm giá trị tích lũy và 8 trở thành giá trị tích lũy mới. Tiếp tục, 8 là giá trị tích lũy, 2 là phần tử hiện thời, giá trị tích lũy mới sẽ là 10. Sau cùng, số 10 đó được dùng làm giá trị tích lũy và 1 là phần tử hiện thời, cho ra số 11. Xin chúc mừng, bạn đã gấp xong!

Biểu đồ hình bên vẽ một cách chuyên nghiệp nhằm minh họa cho thấy từng bước một quá trình gấp xảy ra như thế nào. Con số màu nâu xanh là giá trị được tích lũy. Bạn có thể thấy danh sách kiểu như được “gặm” hết từ phía bên trái giá trị tích lũy. Om nom nom nom! Nếu tính đến việc các hàm được curry, thì ta còn có thể viết lại một cách ngắn gọn hơn như sau:

sum' :: (Num a) => [a] -> a
sum' = foldl (+) 0

Hàm lambda (\acc x -> acc + x) cũng hệt như (+). Ta có thể bỏ qua xs như là tham số vì việc gọi foldl (+) 0 sẽ trả lại một hàm nhận danh sách. Nói chung, nếu bạn có một hàm như foo a = bar b a, bạn có thể viết lại nó thành foo = bar b, vì tính curry.

Bây giờ ta hãy lập một hàm khác với cách gấp trái trước khi chuyển sang gấp phải. Tôi chắc là các bạn điều biết rằng elem kiểm tra xem một giá trị có phải là phần tử của danh sách, vì vậy tôi sẽ không giải thích nữa (ố, tôi lại vừa làm vậy rồi!). Ta hãy thực hiện nó bằng cách gấp trái.

elem' :: (Eq a) => a -> [a] -> Bool
elem' y ys = foldl (\acc x -> if x == y then True else acc) False ys

Nào nào nào, ta đã làm gì vậy? Giá trị đầu và tích lũy ở đây là một giá trị boole. Kiểu của giá trị tích lũy và kết quả cuối cùng luôn giống nhau khi ta thao tác với hàm gấp. Hãy nhớ rằng nếu bạn không biết rằng phải lấy giá trị khởi đầu là gì, thì điều nói trên sẽ gợi ý cho bạn. Ta xuất phát với False. Có lý khi dùng False làm giá trị khởi đầu. Ta giả sử rằng nó không có ở đó. Đồng thời, nếu ta gọi fold đối với danh sách rỗng, kết quả sẽ là giá trị khởi đầu. Sau đó ta kiểm tra phần tử hiện tại xem có phải là phần tử cần tìm không. Nếu đúng, ta đặt giá trị tích lũy là True. Nếu không, ta chỉ việc giữ nguyên giá trị tích lũy. Nếu trước đây nó là False, thì nó vẫn như vậy vì phần tử hiện thời không phải là thứ cần tìm. Nếu nó là True, thì ta cứ để như vậy.

Hàm gấp phải, foldr hoạt động tương tự như gấp trái, chỉ khác là giá trị tích lũy gặm dần từ phía phải. Ngoài ra, hàm nhị phân trong gấp trái thì có giá trị tích lũy đứng làm tham số thứ nhất và giá trị hiện thời làm tham số thứ hai (theo đó \acc x -> ...), còn hàm nhị phân trong gấp phải có giá trị hiện thời đứng làm tham số thứ nhất và giá trị tích lũy làm tham số thứ hai (theo đó \x acc -> ...). Có lý khi nhận thấy rằng hàm gấp phải có giá trị tích lũy bên phía phải, vì nó thực hiện gấp từ phía đó.

Giá trị gấp (và do đó, kết quả) của một hàm gấp có thể thuộc kiểu bất kì. Nó có thể là số, boole hoặc thậm chí cả một danh sách mới. Ta sẽ lập hàm ánh xạ bằng cách gấp phải. Giá trị tích lũy sẽ là một danh sách, ta sẽ tích lũy danh sách ánh xạ theo từng phần tử một. Theo đó, hiển nhiên phần tử đầu tiên phải là danh sách rỗng.

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x acc -> f x : acc) [] xs

Nếu ta ánh xạ (+3) lên [1,2,3], ta sẽ ánh xạ danh sách từ phía bên phải. Ta lấy phần tử cuối cùng, vốn là 3 rồi áp dụng hàm cho nó, kết quả là 6. Sau đó, ta đặt kết quả này vào trước giá trị tích lũy, []. Bây giờ 6:[] bằng [6] và đây là giá trị tích lũy mới. Ta áp dụng(+3) cho 2, nó bằng 5 và ta đặt trước (:) kết quả này đối với giá trị tích lũy, vì vậy bây giờ giá trị tích lũy sẽ là [5,6]. Ta áp dụng (+3) đối với 1 rồi đặt trước nó với giá trị tích lũy và vì vậy giá trị cuối cùng là [4,5,6].

Dĩ nhiên, ta có thể cũng đã áp dụng hàm này với gâ trái. Khi đó sẽ là map' f xs = foldl (\acc x -> acc ++ [f x]) [] xs, nhưng vấn đề là hàm ++ lại “đắt” (tốn thời gian) hơn nhiều so với :, vì vậy thường ta sẽ dùng gấp phải đối khi cần lập các danh sách mới từ một danh sách.

fold this up!

Nếu cần lật ngược một danh sách, bạn có thể gấp phải giống như đã làm với gấp trái và ngược lại. Thậm chí đôi khi bạn còn không phải làm như thế. Hàm sum có thể được thực hiện gấp trái hoặc phải đều khá giống nhau. Một điểm khác biệt lớn là cách gấp phải hoạt động được với các danh sách vô hạn, còn gấp trái thì không! Nói thẳng ra, nếu bạn lấy danh sách vô hạn từ một điểm nào đó rồi gấp từ bên phải, cuối cùng bạn sẽ đến được đầu trái. Nhưng nếu bạn nhận lấy danh sách vô hạn tại điểm nào đó rồi gấp trái, bạn sẽ không bao giờ đến chỗ kết thúc!


Gấp có thể được dùng để thực hiện bất kì hàm nào ở đó bạn duyệt danh sách một lần, từng phần tử một, rồi trả lại thứ gì đó dựa vào việc duyệt này. Mỗi khi bạn muốn duyệt danh sách để trả lại một thứ, thì nhiều khả năng là bạn muốn dùng một hàm gấp.
Đó là lý do tại sao, bên cạnh ánh xạ và lọc, gấp là một trong những loại hàm hữu dụng nhất trong lập trình hàm.

Các hàm foldl1foldr1 cũng hoạt động giống như foldlfoldr, chỉ khác là bạn không cần cung cấp cho chúng các giá trị khởi đầu cụ thể. Chúng sẽ giả sử phần tử đầu (hoặc cuối) của danh sách làm giá trị khởi đầu rồi bắt đầu việc gấp với phần tử kế cận. Lưu ý điều này, ta có thể viết hàm sum như sau: sum = foldl1 (+). Vì chúng phụ thuộc vào các danh sách phải có ít nhất là một phần tử, nên sẽ có lỗi thực thi nếu ta gọi chúng với danh sách rỗng. Nhưng foldlfoldr lại chạy được với danh sách rỗng. Khi bạn tự thực hiện việc gâp, hãy hình dung xem hàm sẽ hoạt động ra sao với danh sách rỗng. Nếu hàm không chạy hợp lý khi được cấp cho một danh sách rỗng, thì bạn có thể dùng một hàm foldl1 hàm foldr1 trong quá trình lập.

Để cho bạn thấy sức mạnh của các hàm gấp, ta sẽ thực hiện một loạt những hàm thư viện tiêu chuẩn bằng hàm gấp:

maximum' :: (Ord a) => [a] -> a
maximum' = foldr1 (\x acc -> if x > acc then x else acc)

reverse' :: [a] -> [a]
reverse' = foldl (\acc x -> x : acc) []

product' :: (Num a) => [a] -> a
product' = foldr1 (*)

filter' :: (a -> Bool) -> [a] -> [a]
filter' p = foldr (\x acc -> if p x then x : acc else acc) []

head' :: [a] -> a
head' = foldr1 (\x _ -> x)

last' :: [a] -> a
last' = foldl1 (\_ x -> x)

Dùng khớp mẫu để lập head sẽ tốt hơn, nhưng trên đây chỉ nhằm giới thiệu cho thấy bạn vẫn có thể thực hiện bằng hàm gấp. Tôi nghĩ rằng định nghĩa reverse' khá là khéo léo. Ta lấy một giá trị khởi đầu là danh sách rỗng rồi tiếp cận danh sách đối tượng từ phía trái và chỉ việc đặt nó trước giá trị tích lũy. Cuối cùng, ta lập nên được danh sách lật ngược. \acc x -> x : acc trông giống như kiểu hàm : chỉ khác là các tham số được đảo ngược. Đó là lý do tại sao ta đã có thể viết hàm lật ngược dưới dạng foldl (flip (:)) [].

Một cách khác để hình dùng các hàm gấp trái và phải như sau: chẳng hạn ta gấp với hàm nhị phân f cùng giá trị khới đầu z. Nếu ta gấp phải danh sách [3,4,5,6], thực chất là ta làm như sau: f 3 (f 4 (f 5 (f 6 z))). f được gọi với phần tử cuối cùng của danh sách và giá trị tích lũy, giá trị đó lại được đóng vai trò là giá trị tích lũy với giá trị áp chót, và cứ như vậy. Nếu ta chọn f+ và giá trị tích lũy khởi đầu là 0, thì kết quả sẽ là 3 + (4 + (5 + (6 + 0))). Hoặc nếu ta viết + dưới dạng hàm tiền tố, nó sẽ là (+) 3 ((+) 4 ((+) 5 ((+) 6 0))). Tương tự, thực hiện gấp trái đối với danh sách đó bằng hàm nhị phân g và giá trị tích lũy z sẽ tương đương với g (g (g (g z 3) 4) 5) 6. Nếu ta dùng flip (:) làm hàm nhị phân và [] làm giá trị tích lũy (để đảo ngược danh sách), thì nó sẽ tương đương với flip (:) (flip (:) (flip (:) (flip (:) [] 3) 4) 5) 6. Và chắc hẳn, nếu lượng giá biểu thức này, bạn sẽ thu được [6,5,4,3].

scanlscanr cũng như foldlfoldr, chỉ khác là chúng báo cáo tất cả những trạng thái trung gian của giá trị tích lũy dưới dạng một danh sách. Cũng có scanl1scanr1, vốn tương tự như foldl1foldr1.

ghci> scanl (+) 0 [3,5,2,1]
[0,3,8,10,11]
ghci> scanr (+) 0 [3,5,2,1]
[11,8,3,1,0]
ghci> scanl1 (\acc x -> if x > acc then x else acc) [3,4,5,3,7,9,2,1]
[3,4,5,5,7,9,9,9]
ghci> scanl (flip (:)) [] [3,2,1]
[[],[3],[2,3],[1,2,3]]

Khi dùng hàm scanl, kết quả sau cùng sẽ là phần tử cuối của danh sách, còn scanr sẽ đặt kết quả lên đầu danh sách.

Scan được dùng để theo dõi tiến trình của một hàm thực hiện dưới hình thức gấ. Hãy trả lời câu hỏi này: Cần lấy bao nhiêu phần tử để lập nên tổng của các căn bậc hai các số nguyên sao cho tổng này vượt quá 1000? Để lấy căn bậc hai của số tự nhiên, ta chỉ cần viết map sqrt [1..]. Bây giờ để lấy tổng, ta có thể gấp, nhưng vì ta quan tâm đến việc tổng này diễn tiến ra sao, nên ta sẽ phải scan. Một khi scan xong, ta sẽ thấy được có bao nhiêu tổng nhỏ hơn 1000. Bình thường thì tổng thứ nhất trong danh sách scan bằng 1. Tổng thứ hai sẽ bằng 1 cộng với căn [bậc hai] của 2. Tổng thứ ba thì bằng lượng đó cộng với căn của 3. Nếu có X tổng dưới 1000, thì sẽ có X+1 phần tử cần để tổng vượt 1000.

sqrtSums :: Int
sqrtSums = length (takeWhile (<1000) (scanl1 (+) (map sqrt [1..]))) + 1
ghci> sqrtSums
131
ghci> sum (map sqrt [1..131])
1005.0942035344083
ghci> sum (map sqrt [1..130])
993.6486803921487

Ở đây ta dùng takeWhile thay vì filter bởi lẽ filter không làm việc với danh sách vô hạn. Ngay cả khi ta biết rằng danh sách giảm dần, filter cũng không biết, vì vậy ta dùng takeWhile để cắt đứt danh sách scan ở chỗ xuất hiện tổng lớn hơn 1000.

Áp dụng hàm với $

Được rồi, tiếp theo ta sẽ xét đến hàm $, còn được gọi là áp dụng hàm. Trước hết, hãy kiểm tra xem nó được định nghĩa thế nào:

($) :: (a -> b) -> a -> b
f $ x = f x

dollar

Gì thế này? Cái toán tử vô dụng này là gì? Đó chỉ là việc áp dụng hàm! À, gần đúng như vậy, nhưng không hẳn! Nếu như cách áp dụng hàm thông thường (đặt một dấu cách giữa hai thứ) có độ ưu tiên rất cao, thì $ lại có độ ưu tiên thâ nhất. Việc áp dụng hàm bằng dấu cách thì có tính kết hợp trái (theo đó f a b c cũng giống như ((f a) b) c)), còn áp dụng hàm với $ lại có tính kết hợp phải.

Ừ, nghe vậy cũng ổn, nhưng điều đó giúp được gì cho ta? Trong hầu hết các tình huống, đó là một hàm rất tiện mà dùng nó thì ta không phải viết nhiều dấu ngoặc tròn nữa. Xét biểu thức sum (map sqrt [1..130]). Vì $ có độ ưu tiên thấp nên ta có thể viết lại biểu thức như sau: sum $ map sqrt [1..130], và đã tiết kiệm được những lần gõ phím quý giá! Khi gặp dấu $, biểu thức bên tay phải của nó được áp dụng như là tham số cho hàm bên tay trái. Thế còn sqrt 3 + 4 + 9 thì sao? Ở đây 9, 4 và căn [bậc hai] của 3 được cộng lại với nahu. Nếu ta muốn tính căn của tổng 3 + 4 + 9, ta phải viết sqrt (3 + 4 + 9) hoặc nếu dùng $, thì có thể viết sqrt $ 3 + 4 + 9$ có độ ưu tiên thấp hơn bất kì toán tử nào khác. Đó là lý do tại sao bạn có thể hình dùng dấu $ như là một dạng tương đương của viết dấu mở ngoặc tròn và rồi một dấu đóng ngoặc tròn nữa về hết phía bên phải của biểu thức.

Thế còn sum (filter (> 10) (map (*2) [2..10]))? À, vì $ có tính kết hợp phải, nên f (g (z x)) thì bằng với f $ g $ z x. Và do đó, ta có thể viết sum (filter (> 10) (map (*2) [2..10])) thành sum $ filter (> 10) $ map (*2) [2..10].

Nhưng ngoài việc giúp ta tránh dùng cặp ngoặc tròn, $ còn có nghĩa rằng việc áp dụng hàm có thể được coi như là một hàm khác. Bằng cách này, ta có thể, chẳng hạn, ánh xạ một áp dụng hàm đối với một danh sách các hàm.

ghci> map ($ 3) [(4+), (10*), (^2), sqrt]
[7.0,30.0,9.0,1.7320508075688772]

Hàm hợp

Trong toán học, hàm hợp được định nghĩa như sau:  (f . g)(x) = f(g(x)), hàm hợp của hai hàm có sẵn là một hàm mới, sao cho khi được gọi với một tham số, chẳng hạn x, thì cũng tương đương với việc gọi g với tham số x rồi sau đó gọi f với kết quả đó.

Trong Haskell, hàm hợp cũng giống như vậy. Ta viết hàm hợp bằng hàm .; hàm này được định nghĩa như sau:

(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)

notes

Hãy để ý khai báo kiểu. f phải nhận tham số có kiểu giống nhiêu kiểu của giá trị trả lại từ g. Như vậy hàm kết quả nhận vào một tham số có cùng kiểu mà g nhận rồi trả lại giá trị có cùng kiểu với kiểu mà f trả lại. Biểu thức negate . (* 3) trả lại một hàm nhận vào một số, nhân nó với 3 rồi đảo dấu của nó.

Một trong số những tác dụng của hàm hợp là tạo ra các hàm khi cần để truyền đến hàm khác. DĨ nhiên bạn có thể dùng lambda, nhưng nhiều khi, dùng hàm hợp thì rõ ràng hơn và gọn hơn. Chẳng hạn ta có một danh sách các số và muốn chuyển tất cả chúng thành số âm. Một cách làm là lấy giá trị tuyệt đối của từng số rồi đảo dấu đi, như sau:

ghci> map (\x -> negate (abs x)) [5,-3,-6,7,-3,2,-19,24]
[-5,-3,-6,-7,-3,-2,-19,-24]

Lưu ý kí hiệu lambda và cách mà nó đóng vai trò kết quả của hàm hợp. Dùng hàm hợp, ta có thể viết lại như sau:

ghci> map (negate . abs) [5,-3,-6,7,-3,2,-19,24]
[-5,-3,-6,-7,-3,-2,-19,-24]

Tuyệt! Hàm hợp có tính kết hợp phải, vì vậy ta có thể hợp nhiều hàm cùng lúc. Biểu thức f (g (z x)) là tương đương với (f . g . z) x. Ghi nhớ điều này, ta có thể viết lại

ghci> map (\xs -> negate (sum (tail xs))) [[1..5],[3..6],[1..7]]
[-14,-15,-27]

thành

ghci> map (negate . sum . tail) [[1..5],[3..6],[1..7]]
[-14,-15,-27]

Nhưng còn hàm nhận nhiều tham số thì sao? À, nếu ta muốn dùng chúng trong hàm hợp, thường ta phải áp dụng từng phần nhiều đến mức mỗi hàm chỉ được nhận một tham số. sum (replicate 5 (max 6.7 8.9)) có thể được viết lại thành (sum . replicate 5 . max 6.7) 8.9 hoặc sum . replicate 5 . max 6.7 $ 8.9. Cách viết này được giải thích là: một hàm nhận vào thứ mà max 6.7 nhận vào rồi áp dụng replicate 5 cho số vừa tìm ra. Tiếp theo, một hàm nhận kết quả này và tính tổng. Cuối cùng, hàm đó được gọi với tham số 8.9. Nhưng thông thường bạn chỉ cần đọc như sau: áp dụng 8.9 vào cho max 6.7, rồi áp dụng replicate 5 cho kết quả thu được, tiếp theo áp dụng sum cho kết quả vừa rồi. Nếu bạn phải viết lại một biểu thức với rất nhiều dấu ngoặc tròn bằng việc dùng hàm hợp, bạn có thể bắt đầu bằng cách đặt tham số cuối cùng của hàm trong cùng sau một dấu $ rồi chỉ cần hợp tất cả lời gọi hàm khác, viết chúng mà không có tham số cuối cùng rồi đặt dấu chấm giữa chúng. Nếu bạn có replicate 100 (product (map (*3) (zipWith max [1,2,3,4,5] [4,5,6,7,8]))), bạn có thể viết lại thành: replicate 100 . product . map (*3) . zipWith max [1,2,3,4,5] $ [4,5,6,7,8]. Nếu biểu thức kết thúc với ba dấu ngoặc tròn, thì nhiều khả năng là khi chuyển thành dạng hàm hợp, nó sẽ chứa ba toán tử trong hàm hợp.

Một cách dùng hàm hợp thường gặp là định nghĩa các hàm theo cách được gọi là không có dấu chấm (point-free style, hay pointless style). Lấy ví dụ hàm mà ta đã viết từ trước:

sum' :: (Num a) => [a] -> a   
sum' xs = foldl (+) 0 xs

Ở cả hai vế, xs đều có mặt. Do tính curry, ta có thể lược bỏ xs ở hai vế, vì việc gọi foldl (+) 0 tạo ra một hàm nhận vào một danh sách. Viết hàm này dưới dạng sum' = foldl (+) 0 được gọi là viết theo kiểu không có dấu chấm. Ta sẽ viết hàm sau theo kiểu không dấu chấm như thế nào?

fn x = ceiling (negate (tan (cos (max 50 x))))

Ở đây, ta không thể lược bỏ x ở cả hai vế. Chữ x trong thân hàm có dấu ngoặc tròn ngay sau nó. cos (max 50) sẽ không có nghĩa lý gì. Bạn không thể lấy cosin của một hàm. Điều ta có thể làm là biểu diễn fn theo kiểu hàm hợp.

fn = ceiling . negate . tan . cos . max 50

Tuyệt vời! Nhiều khi, kiểu viết không dấu chấm thì dễ đọc và gọn hơn, vì nó khiến bạn nghĩ về các hàm và các hình thức kết hợp hàm thay vì nghĩ về dữ liệu và cách mà nó vận chuyển lung tung. Bạn có thể nhặt các hàm đơn giản và dính chúng lại để tạo thành các hàm phức tạp hơn. Tuy vậy, nhiều khi viết hàm theo kiểu không dấu chấm sẽ khó đọc hơn nếu hàm quá phức tạp. Đó là lý do tại sao hàm hợp quá dài không được khuyến khích, mặc dù đôi lúc tôi cảm thấy có lỗi khi quá lạm dụng hàm hợp. Cách viết được ưa chuộng là dùng let để gắn các nhãn cho những kết quả trung gian hoặc chia nhỏ bài toán thành những vấn đề con rồi sau đó gộp lại, để cho hàm có ý nghĩa đối với người đọc, hơn là tạo ra một chuỗi hàm hợp dài lòng thòng.

Trong mục viết về ánh xạ và lọc, ta đã giải quyết bài toán tính tổng của tất cả những bình phương nhỏ hơn 10000 của các số lẻ. Sau đây là lời giải khi ta đặt nó vào trong một hàm.

oddSquareSum :: Integer
oddSquareSum = sum (takeWhile (<10000) (filter odd (map (^2) [1..])))

Là người hâm mộ hàm hợp, lẽ ra tôi đã có thể viết như sau:

oddSquareSum :: Integer
oddSquareSum = sum . takeWhile (<10000) . filter odd . map (^2) $ [1..]

Nhưng nếu có cơ hội được người nào đó đọc mã lệnh mình viết, thì tôi sẽ viết lại nó thành:

oddSquareSum :: Integer
oddSquareSum = 
    let oddSquares = filter odd $ map (^2) [1..]
        belowLimit = takeWhile (<10000) oddSquares
    in  sum belowLimit

Cách viết mới này chẳng nhằm mục đích ganh đua với ai, mà chỉ giúp người đọc hàm có thể sẽ dễ hiểu hơn so với đọc hàm hợp.

Advertisements

3 phản hồi

Filed under Haskell, Tin học

3 responses to “Chương 6: Hàm cấp cao

  1. Pingback: Tự học lấy Haskell | Blog của Chiến

  2. Pingback: Chương 10: Giải bài toán theo phong cách lập trình hàm | Blog của Chiến

  3. Pingback: Chương 11: Functor, Functor áp dụng và Monoid | Blog của Chiến

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s