Làm cách nào tôi có thể hiểu "(.). (.)"?

Question

Tôi tin rằng tôi hiểu được fmap . fmap đối với Functors, nhưng về chức năng nó đã làm tổn thương đầu của tôi trong nhiều tháng nay.

Tôi đã thấy rằng bạn chỉ có thể áp dụng định nghĩa của (.) đến (.) . (.), nhưng tôi đã quên cách thực hiện điều đó.
Khi tôi thử bản thân mình nó luôn luôn quay ra sai:

(.) f g = \x -> f (g x) 
(.) (.) (.) = \x -> (.) ((.) x) 
\x f -> (.) ((.) x) f 
\x f y -> (((.)(f y)) x) 
\x f y g-> (((.)(f y) g) x) 
\x f y g-> ((f (g y)) x) 
\x f y g-> ((f (g y)) x):: t2 -> (t1 -> t2 -> t) -> t3 -> (t3 -> t1) -> t 

Nếu "chỉ áp dụng định nghĩa" là cách duy nhất để làm việc đó, làm thế nào ai đưa ra (.) . (.)?
Phải có một số hiểu biết sâu sắc hơn hoặc trực giác tôi đang thiếu.

Answer 1

Bạn cũng có thể sử dụng hiểu biết của bạn fmap . fmap.

Nếu bạn có hai Functor s foo và bar, sau đó

fmap . fmap :: (a -> b) -> foo (bar a) -> foo (bar b) 

fmap . fmap mất một chức năng và tạo ra một chức năng gây ra cho các thành phần của hai Functor s.

Bây giờ, đối với bất kỳ loại t, (->) t là một Functor, và fmap cho rằng Functor là (.).

Vì vậy (.) . (.) là fmap . fmap cho trường hợp hai Functor s là (->) s và (->) t, và do đó

(.) . (.) :: (a -> b) -> ((->) s) ((->) t a) -> ((->) s) ((->) t b) 
      = (a -> b) -> (s -> (t -> a))  -> (s -> (t -> b)) 
      = (a -> b) -> (s -> t -> a)  -> (s -> t -> b) 

nó "sáng tác" một hàm f :: a -> b với một chức năng của hai đối số, g :: s -> t -> a,

((.) . (.)) f g = \x y -> f (g x y) 

Chế độ xem đó cũng làm rõ rằng, và cách thức, mẫu mở rộng đến các hàm lấy nhiều đối số hơn,

(.) . (.) . (.) :: (a -> b) -> (s -> t -> u -> a) -> (s -> t -> u -> b) 

, vv

Answer 2

Vì vậy, đây là những gì tôi nhận được khi tôi làm một mở rộng một chút gia tăng hơn

(.) f g = \x -> f (g x) 
(.) . g = \x -> (.) (g x) 
      = \x -> \y -> (.) (g x) y 
      = \x -> \y -> \z -> (g x) (y z) 
      = \x y z -> (g x) (y z) 
(.) . (.) = \x y z -> ((.) x) (y z) 
      = \x y z -> \k -> x (y z k) 
      = \x y z k -> x (y z k) 

nào, theo ghci có đúng loại

Prelude> :t (.) . (.) 
(.) . (.) :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c 
Prelude> :t \x y z k -> x (y z k) 
\x y z k -> x (y z k) 
    :: (t1 -> t) -> (t2 -> t3 -> t1) -> t2 -> t3 -> t 
Prelude> 

Trong khi tôi không biết nguồn gốc của combinator này, có khả năng là được phát triển để sử dụng trong logic kết hợp, nơi bạn làm việc chặt chẽ với các bộ tổ hợp, để bạn không thể xác định mọi thứ bằng cách sử dụng các biểu thức lambda tiện lợi hơn. Có thể có một số trực giác đi kèm với việc tìm ra những điều này, nhưng tôi đã không tìm thấy nó. Rất có thể, bạn sẽ phát triển một số mức trực giác nếu bạn phải làm điều đó đủ.

Answer 3

Giải pháp của bạn phân biệt khi bạn giới thiệu y. Nó phải là

\x f y -> ((.) ((.) x) f) y  :: (c -> d) -> (a -> b -> c) -> a -> b -> d 
\x f y z -> ((.) ((.) x) f) y z :: (c -> d) -> (a -> b -> c) -> a -> b -> d 
\x f y z -> ((.) x (f y)) z  :: (c -> d) -> (a -> b -> c) -> a -> b -> d 
-- Or alternately: 
\x f y z -> (x . f y) z   :: (c -> d) -> (a -> b -> c) -> a -> b -> d 
\x f y z -> (x (f y z))   :: (c -> d) -> (a -> b -> c) -> a -> b -> d 

nào phù hợp với loại chữ ký gốc: (.) . (.) :: (c -> d) -> (a -> b -> c) -> a -> b -> d

(Đó là dễ nhất để làm việc mở rộng trong ghci, nơi bạn có thể kiểm tra từng bước với :t expression)

Edit:

Cảnh báo sâu hơn là:

(.) chỉ đơn giản được định nghĩa là

\f g -> \x -> f (g x) 

nào chúng ta có thể đơn giản hóa để

\f g x -> f (g x) 

Vì vậy, khi bạn cung cấp cho nó hai đối số, đó là cà ri và vẫn cần một lập luận để giải quyết. Mỗi khi bạn sử dụng (.) với 2 đối số, bạn tạo một "nhu cầu" cho một đối số khác.

(.) . (.) là tất nhiên chỉ (.) (.) (.), vì vậy chúng ta hãy mở rộng nó:

(\f0 g0 x0 -> f0 (g0 x0)) (\f1 g1 x1 -> f1 (g1 x1)) (\f2 g2 x2 -> f2 (g2 x2)) 

Chúng ta có thể beta-giảm trên f0 và g0 (nhưng chúng tôi không có một x0!):

\x0 -> (\f1 g1 x1 -> f1 (g1 x1)) ((\f2 g2 x2 -> f2 (g2 x2)) x0) 

thay thế biểu thức thứ 2 cho f1 ...

\x0 -> \g1 x1 -> ((\f2 g2 x2 -> f2 (g2 x2)) x0) (g1 x1) 

Bây giờ nó "flips trở lại"! (beta-giảm trên f2):
Đây là bước thú vị - x0 được thay thế cho f2 - Điều này có nghĩa là x, có thể là dữ liệu, thay vào đó là một hàm.
Điều này là những gì (.) . (.) cung cấp - "nhu cầu" cho đối số bổ sung.

\x0 -> \g1 x1 -> (\g2 x2 -> x0 (g2 x2)) (g1 x1) 

này được bắt đầu nhìn bình thường ... Hãy beta-giảm một lần cuối cùng (trên g2):

\x0 -> \g1 x1 -> (\x2 -> x0 ((g1 x1) x2)) 

Vì vậy, chúng tôi đang trái với chỉ đơn giản

\x0 g1 x1 x2 -> x0 ((g1 x1) x2) 

, nơi các đối số là độc đáo vẫn còn theo thứ tự.

Answer 4

Đó là đơn giản nhất để viết phương trình , combinators-style, thay vì lambda-biểu: a b c = (\x -> ... body ...) tương đương với a b c x = ... body ..., và ngược lại, với điều kiện x không xuất hiện trong số {a,b,c}. Vì vậy,

-- _B = (.) 

_B f g x = f (g x) 
_B _B _B f g x y = _B (_B f) g x y 
       = (_B f) (g x) y 
       = _B f (g x) y 
       = f ((g x) y) 
       = f (g x y) 

Bạn khám phá này nếu, do f (g x y), bạn muốn chuyển đổi nó into a combinatory form (thoát khỏi tất cả các dấu ngoặc đơn và lặp đi lặp lại biến). Sau đó, bạn áp dụng các mẫu tương ứng với các định nghĩa của combinators, hy vọng truy tìm nguồn gốc này ngược trở lại. Điều này là ít cơ khí/tự động mặc dù.

Answer 5

Đến với (.) . (.) thực sự là khá đơn giản, đó là trực giác đằng sau những gì nó làm đó là khá khó hiểu.

(.) giúp bạn rất xa khi viết lại biểu thức thành các tính toán kiểu "đường ống" (nghĩ về | trong vỏ). Tuy nhiên, nó trở nên khó xử khi sử dụng khi bạn cố gắng soạn một hàm nhận nhiều đối số với hàm chỉ mất một đối số. Như một ví dụ, chúng ta hãy có một định nghĩa về concatMap:

concatMap :: (a -> [b]) -> [a] -> [b] 
concatMap f xs = concat (map f xs) 

Bắt thoát khỏi xs chỉ là một hoạt động tiêu chuẩn:

concatMap f = concat . map f 

Tuy nhiên, không có "đẹp" cách loại bỏ f. Điều này là do thực tế, rằng map có hai đối số và chúng tôi muốn áp dụng concat về kết quả cuối cùng của nó.

Bạn có thể dĩ nhiên áp dụng một số thủ thuật pointfree và nhận được ngay với chỉ (.):

concatMap f = (.) concat (map f) 
concatMap f = (.) concat . map $ f 
concatMap = (.) concat . map 
concatMap = (concat .) . map 

Nhưng than ôi, khả năng đọc của mã này chủ yếu đi.Thay vào đó, chúng tôi giới thiệu một bộ kết hợp mới, thực hiện chính xác những gì chúng tôi cần: áp dụng hàm thứ hai cho kết quả cuối cùng kết quả cuối cùng của kết quả đầu tiên.

-- .: is fairly standard name for this combinator 
(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d 
(f .: g) x y = f (g x y) 

concatMap = concat .: map 

Tốt, đó là động lực. Hãy đến với công việc kinh doanh vô cùng đơn giản.

(.:) = \f g x y -> f (g x y) 
    = \f g x y -> f ((g x) y) 
    = \f g x y -> f . g x $ y 
    = \f g x -> f . g x 

Bây giờ, đây là phần thú vị. Đây là một thủ thuật vô nghĩa khác thường hữu ích khi bạn gặp khó khăn: chúng tôi viết lại . vào mẫu tiền tố của nó và cố gắng tiếp tục từ đó.

 = \f g x -> (.) f (g x) 
    = \f g x -> (.) f . g $ x 
    = \f g  -> (.) f . g 
    = \f g  -> (.) ((.) f) g 
    = \f  -> (.) ((.) f) 
    = \f  -> (.) . (.) $ f 
    =    (.) . (.) 

Đối với trực giác, có very nice article mà bạn nên đọc. Tôi sẽ diễn giải một phần về (.):

Hãy suy nghĩ lại về những gì combinator của chúng tôi nên làm gì: nó nên áp dụng f đến kết quả của kết quả của g (Tôi đã sử dụng kết quả cuối cùng trong một phần trước khi có mục đích, nó thực sự là những gì bạn nhận được khi bạn áp dụng đầy đủ - modulo hợp nhất các biến kiểu với một kiểu hàm khác - hàm g, kết quả ở đây chỉ là ứng dụng g x cho một số x).

Điều gì có nghĩa là chúng tôi áp dụng f cho kết quả của g? Vâng, khi chúng tôi áp dụng g cho một số giá trị, chúng tôi sẽ lấy kết quả và áp dụng f cho nó. Nghe có vẻ quen thuộc: đó là những gì (.) làm.

result :: (b -> c) -> ((a -> b) -> (a -> c)) 
result = (.) 

Bây giờ, nó chỉ ra rằng thành phần (của chúng tôi của từ) của những combinators chỉ là một hàm hợp, đó là:

(.:) = result . result -- the result of result