Wie kann ich "(.). (.)" Verstehen?

Question

Ich glaube, ich verstehe fmap . fmap für Funktoren, aber auf Funktionen tut es mir seit Monaten Kopfschmerzen.

Ich habe gesehen, dass Sie einfach die Definition von (.) auf (.) . (.) anwenden können, aber ich habe vergessen, wie das geht.
Wenn ich versuche es selbst es stellt sich heraus, immer falsch:

(.) 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 

Wenn „nur die Definition der Anwendung“ ist der einzige Weg, es zu tun, wie jemand mit (.) . (.) kommen hat?
Es muss etwas tieferes Verständnis oder Intuition fehlen, die ich vermisse.

Answer 1

Sie auch Ihr Verständnis von fmap . fmap nutzen können.

Wenn Sie zwei Functor haben s foo und bar, dann

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

fmap . fmap nimmt eine Funktion und erzeugt eine induzierte Funktion für die Zusammensetzung der beiden Functor s.

nun für jede Art t ist (->) t ein Functor und die fmap für das Functor ist (.).

So (.) . (.) ist fmap . fmap für den Fall, dass die beiden Functor s sind (->) s und (->) t und damit

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

es "komponiert" eine Funktion f :: a -> b mit einer Funktion von zwei Argumenten, g :: s -> t -> a,

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

Diese Ansicht macht auch deutlich, dass und wie sich das Muster auf Funktionen erstreckt, die mehr Argumente benötigen,

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

usw.

Answer 2

Also, das ist, was ich, wenn ich eine etwas inkrementelle Expansion tun

(.) 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) 

Which, hat nach GHCI den richtigen Typ

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> 

Während ich weiß nicht, die Ursprünge dieser combinator, ist es wahrscheinlich, dass es für den Einsatz in kombinatorischer Logik entwickelt wurde, wo man streng mit combinators arbeiten, so können Sie nicht Dinge definieren bequemen Lambda-Ausdrücke verwenden. Es mag sein, dass es eine Intuition gibt, die mit dem Errechnen dieser Dinge zusammenhängt, aber ich habe sie nicht gefunden. Wahrscheinlich würden Sie ein gewisses Maß an Intuition entwickeln, wenn Sie es genug tun müssten.

Answer 3

Ihre Lösung divergiert, wenn Sie y einzuführen. Es sollte

\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 

, die die ursprüngliche Art Signatur übereinstimmt: (.) . (.) :: (c -> d) -> (a -> b -> c) -> a -> b -> d

(Es ist am einfachsten, die Expansion in GHCI zu tun, in dem Sie jeden Schritt mit :t expression überprüfen)

Edit:

Je tiefer Intuition ist dies:

(.) einfach als

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

definiert, die wir also zu

\f g x -> f (g x) 

vereinfachen können, wenn Sie es zwei Argumente liefern, es ist curried und muss noch ein weiteres Argument zu lösen. Jedes Mal, wenn Sie (.) mit 2 Argumenten verwenden, erstellen Sie eine "Notwendigkeit" für ein weiteres Argument.

(.) . (.) natürlich nur (.) (.) (.), dann ist es so lassen erweitern:

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

Wir können auf f0 und g0 Beta-verringern (aber wir haben keine x0!):

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

Ersatz der 2. Ausdruck für f1 ...

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

Jetzt ist es "blättert zurück"! (beta-reduction on f2):
Dies ist der interessante Schritt - x0 ersetzt f2 - Dies bedeutet, dass x, die Daten hätte sein können, ist stattdessen eine Funktion.
Diese ist, was (.) . (.) bietet - die "Notwendigkeit" für das zusätzliche Argument.

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

Dies beginnt normal aussehen ... Lassen Sie uns ein letztes Mal Beta-reduzieren (auf g2):

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

So sind wir mit einfach links

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

, wo die Argumente noch schön geordnet sind.

Answer 4

Es ist am einfachsten Gleichungen, combinators-style, anstelle von Lambda-Ausdrücke zu schreiben: a b c = (\x -> ... body ...)-a b c x = ... body ... gleichwertig ist und umgekehrt, sofern x nicht unter {a,b,c} erscheint. So

-- _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) 

Sie entdecken diese, wenn f (g x y) gegeben, die Sie konvertieren möchten es into a combinatory form (loszuwerden aller Klammern und variable Wiederholungen). Dann wenden Sie Muster an, die den Definitionen der Kombinatoren entsprechen, und verfolgen diese Ableitung hoffentlich rückwärts. Dies ist jedoch viel weniger mechanisch/automatisch.

Answer 5

Es ist eigentlich ziemlich einfach, mit (.) . (.) zu kommen, es ist die Intuition dahinter, was es ziemlich schwierig zu verstehen ist.

(.) bekommen Sie sehr weit beim Umschreiben Ausdruck in die "Rohr" Stil Berechnungen (denke an | in Shell). Es wird jedoch schwierig zu verwenden, wenn Sie versuchen, eine Funktion zu erstellen, die mehrere Argumente mit einer Funktion benötigt, die nur eine benötigt. Als Beispiel nehmen wir eine Definition von concatMap haben:

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

Erste von xs loszuwerden, ist nur ein Standard-Betrieb:

concatMap f = concat . map f 

Allerdings gibt es keine „schöne“ Weg, um sich von f befreien. Dies wird durch die Tatsache verursacht, dass map zwei Argumente benötigt und wir möchten concat auf sein Endergebnis anwenden.

Sie können einige pointfree Tricks natürlich anzuwenden und weg mit nur (.):

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

Aber ach, die Lesbarkeit des Codes ist meist verschwunden.Stattdessen führen wir einen neuen Kombinator ein, der genau das tut, was wir brauchen: Wenden Sie die zweite Funktion auf das Endergebnis des ersten an.

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

Gut, das ist es für die Motivation. Kommen wir zum Point-Free-Business.

(.:) = \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 

Jetzt kommt hier der interessante Teil. Dies ist eine weitere der pointfree Tricks, die normalerweise hilft, wenn Sie stecken bleiben: Wir schreiben . in seine Präfixform und versuchen, von dort fortzusetzen.

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

Wie für Intuition, gibt es diese very nice article, die Sie lesen sollten. Ich werde den Teil über (.) paraphrasieren:

Denken sie noch einmal über das, was unser combinator tun sollte: es f zum Ergebnis von Ergebnis von g gelten soll (ich habe Endergebnis wurde mit in der Teil vor absichtlich, es ist wirklich, was Sie erhalten, wenn Sie vollständig anwenden - Modulo vereinheitlichen Typ Variablen mit einem anderen Funktionstyp - die g Funktion, Ergebnis hier ist nur Anwendung g x für einige x).

Was bedeutet es für uns, f auf das Ergebnis von g anzuwenden? Nun, sobald wir g auf einen Wert anwenden, nehmen wir das Ergebnis und wenden f darauf an. Hört sich bekannt an: das macht (.).

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

Nun stellt sich heraus, dass die Zusammensetzung (unser von Wort) dieser combinators ist nur eine Funktion Zusammensetzung, das heißt:

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