(f.). g có nghĩa là trong Haskell?

Question

Tôi đã thấy nhiều chức năng được xác định theo mẫu (f .) . g. Ví dụ:

countWhere = (length .) . filter 
duplicate = (concat .) . replicate 
concatMap = (concat .) . map 

Điều này có nghĩa là gì?

Answer 1

Toán tử dấu chấm (ví dụ: (.)) là toán tử function composition. Nó được định nghĩa như sau:

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

Như bạn có thể nhìn thấy nó mất một chức năng của loại b -> c và một chức năng của loại a -> b và trả về một chức năng của loại a -> c (tức là áp dụng các kết quả của hàm thứ hai để là người đầu tiên chức năng).

Toán tử thành phần hàm rất hữu ích. Nó cho phép bạn đường ống đầu ra của một hàm vào đầu vào của một hàm khác. Ví dụ: bạn có thể viết chương trình tac trong Haskell như sau:

main = interact (\x -> unlines (reverse (lines x))) 

Không thể đọc được. Sử dụng hàm hợp tuy nhiên bạn có thể viết nó như sau:

main = interact (unlines . reverse . lines) 

Như bạn có thể nhìn thấy hàm hợp là rất hữu ích nhưng bạn không thể sử dụng nó ở khắp mọi nơi. Ví dụ, bạn có thể không ống đầu ra của filter vào length sử dụng hàm hợp:

countWhere = length . filter -- this is not allowed 

Lý do này không được phép là vì filter là loại (a -> Bool) -> [a] -> [a]. So sánh nó với a -> b chúng tôi thấy rằng a là loại (a -> Bool) và b là loại [a] -> [a]. Điều này dẫn đến một loại không khớp vì Haskell mong đợi length là loại b -> c (ví dụ: ([a] -> [a]) -> c). Tuy nhiên nó thực sự thuộc loại [a] -> Int.

Giải pháp là khá đơn giản:

countWhere f = length . filter f 

Tuy nhiên một số người không thích điều đó thêm lủng lẳng f. Họ thích viết countWhere trong pointfree phong cách như sau:

countWhere = (length .) . filter 

Làm thế nào để họ có được điều này? Xem xét:

countWhere f xs = length (filter f xs) 

-- But `f x y` is `(f x) y`. Hence: 

countWhere f xs = length ((filter f) xs) 

-- But `\x -> f (g x)` is `f . g`. Hence: 

countWhere f = length . (filter f) 

-- But `f . g` is `(f .) g`. Hence: 

countWhere f = (length .) (filter f) 

-- But `\x -> f (g x)` is `f . g`. Hence: 

countWhere = (length .) . filter 

Như bạn thấy (f .) . g chỉ đơn giản là \x y -> f (g x y). Khái niệm này thực sự có thể được lặp lại:

f . g    --> \x -> f (g x) 
(f .) . g   --> \x y -> f (g x y) 
((f .) .) . g  --> \x y z -> f (g x y z) 
(((f .) .) .) . g --> \w x y z -> f (g w x y z) 

Nó không đẹp nhưng nó hoàn thành công việc.Với hai chức năng bạn cũng có thể viết các nhà khai thác hàm hợp của riêng bạn:

f .: g = (f .) . g 
f .:: g = ((f .) .) . g 
f .::: g = (((f .) .) .) . g 

Sử dụng các nhà điều hành (.:) bạn có thể viết countWhere như sau thay vì:

countWhere = length .: filter 

Điều thú vị là mặc dù bạn có thể viết (.:) tại điểm theo phong cách tự do như well:

f .: g = (f .) . g 

-- But `f . g` is `(.) f g`. Hence: 

f .: g = (.) (f .) g 

-- But `\x -> f x` is `f`. Hence: 

(f .:) = (.) (f .) 

-- But `(f .)` is `((.) f)`. Hence: 

(f .:) = (.) ((.) f) 

-- But `\x -> f (g x)` is `f . g`. Hence: 

(.:) = (.) . (.) 

Tương tự chúng tôi nhận được:

(.::) = (.) . (.) . (.) 
(.:::) = (.) . (.) . (.) . (.) 

Như bạn thấy (.:), (.::) và (.:::) chỉ là quyền hạn của (.) (ví dụ: chúng là iterated functions trong số (.)). Đối với các số trong Toán học:

x^0 = 1 
x^n = x * x^(n - 1) 

Tương tự như vậy cho các chức năng trong Toán học:

f .^ 0 = id 
f .^ n = f . (f .^ (n - 1)) 

Nếu f là (.) thì:

(.) .^ 1 = (.) 
(.) .^ 2 = (.:) 
(.) .^ 3 = (.::) 
(.) .^ 4 = (.:::) 

đó đưa chúng ta gần cuối bài viết này. Đối với một thử thách cuối cùng chúng ta hãy viết hàm sau trong phong cách pointfree:

mf a b c = filter a (map b c) 

mf a b c = filter a ((map b) c) 

mf a b = filter a . (map b) 

mf a b = (filter a .) (map b) 

mf a = (filter a .) . map 

mf a = (. map) (filter a .) 

mf a = (. map) ((filter a) .) 

mf a = (. map) ((.) (filter a)) 

mf a = ((. map) . (.)) (filter a) 

mf = ((. map) . (.)) . filter 

mf = (. map) . (.) . filter 

Chúng tôi có thể tiếp tục đơn giản hóa này như sau:

compose f g = (. f) . (.) . g 

compose f g = ((. f) . (.)) . g 

compose f g = (.) ((. f) . (.)) g 

compose f = (.) ((. f) . (.)) 

compose f = (.) ((. (.)) (. f)) 

compose f = ((.) . (. (.))) (. f) 

compose f = ((.) . (. (.))) (flip (.) f) 

compose f = ((.) . (. (.))) ((flip (.)) f) 

compose = ((.) . (. (.))) . (flip (.)) 

Sử dụng compose bây giờ bạn có thể viết mf như:

mf = compose map filter 

Có một chút xấu xí nhưng nó cũng là một khái niệm boggling thực sự tuyệt vời. Bây giờ bạn có thể viết bất kỳ chức năng nào của biểu mẫu \x y z -> f x (g y z) dưới dạng compose f g và điều đó rất gọn gàng.

Answer 2

Đây là vấn đề về hương vị, nhưng tôi thấy kiểu như vậy khó chịu. Đầu tiên tôi sẽ mô tả ý nghĩa của nó, và sau đó tôi đề nghị một phương án mà tôi thích.

Bạn cần biết rằng (f . g) x = f (g x) và (f ?) x = f ? x cho bất kỳ nhà điều hành nào ?. Từ đó chúng ta có thể suy luận rằng

countWhere p = ((length .) . filter) p 
       = (length .) (filter p) 
       = length . filter p 

nên

countWhere p xs = length (filter p xs) 

Tôi thích sử dụng một chức năng gọi là .:

(.:) :: (r -> z) -> (a -> b -> r) -> a -> b -> z 
(f .: g) x y = f (g x y) 

Sau đó countWhere = length .: filter. Cá nhân tôi thấy điều này rõ ràng hơn rất nhiều.

(.: được định nghĩa trong Data.Composition và có lẽ những nơi khác nữa.)