Quoi peux je comand?

Question

Je crois que je comprends fmap . fmap pour les Foncteurs, mais sur des fonctions de blesser ma tête depuis des mois maintenant.

J'ai vu que vous pouvez simplement appliquer la définition de l' (.) de (.) . (.), mais j'ai oublié comment faire.
Quand je l'ai essayer moi-même, il tourne toujours mal:

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

Si "tout simplement l'application de la définition de" est la seule façon de le faire, comment quelqu'un de venir avec (.) . (.)?
Il doit y avoir une compréhension plus approfondie ou une intuition, je suis absent.

Answer 1

Venir avec des (.) . (.) est en fait assez simple, c'est l'intuition derrière ce qu'il fait c'est assez difficile à comprendre.

(.) vous fait de très loin lors de la réécriture de l'expression dans le "pipe" style calculs (pensons | de la coquille). Cependant, il devient difficile de le faire lorsque vous essayez de composer une fonction qui prend plusieurs arguments d'une fonction qui ne prend qu'un seul. Comme exemple, nous allons avoir une définition de l' concatMap:

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

Se débarrasser de l' xs est juste une opération standard.

concatMap f = concat . map f

Cependant, il n'y a pas "gentil" la façon de se débarrasser d' f. Ceci est causé par le fait, que map prend deux arguments et nous aimerions appliquer concat sur son résultat final.

Bien sûr, vous pouvez appliquer un peu de pointfree astuces et de s'en tirer avec juste (.):

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

Mais hélas, la lisibilité de ce code est pour la plupart disparu. Au lieu de cela, nous introduisons une nouvelle combinator, qui fait exactement ce dont nous avons besoin: appliquer la deuxième fonction du résultat final de la première.

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

Fine, c'est pour la motivation. Mettons-nous à la pointfree d'affaires.

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

Maintenant, voici la partie intéressante. C'est encore un autre de la pointfree astuces qui permet généralement lorsque vous êtes coincé: nous réécrire . dans son préfixe de la forme et essayer de continuer à partir de là.

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

Comme pour l'intuition, il y a ce très bel article que vous devez lire. Je vais paraphraser la partie sur (.):

Nous allons réfléchir à nouveau sur ce qui devrait nos combinator faire: il doit s'appliquent f à la suite du résultat de l' g (j'ai été en utilisant résultat final de la partie avant sur le but, c'est vraiment ce que vous obtenez lorsque vous appliquer pleinement - modulo unifier les variables de type avec un autre type de fonction - l' g de la fonction, le résultat ici est juste application g x pour certains x).

Ce que cela signifie pour nous d'appliquer f à la suite de l' g? Eh bien, une fois que nous appliquons g de la valeur, nous allons prendre la suite et s'appliquent f pour elle. Semble familier: c'est ce qu' (.) n'.

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

Maintenant, il s'avère que la composition (nos de mot) de ces combinators est juste une fonction de la composition, qui est:

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

Answer 2

Vous pouvez également utiliser votre compréhension de l' fmap . fmap.

Si vous avez deux Functors foo et bar, alors

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

fmap . fmap prend une fonction et produit un induite par la fonction de la composition des deux Functors.

Maintenant, pour tout type t, (->) t est Functor, et l' fmap pour Functor est (.).

Donc, (.) . (.) est fmap . fmap pour le cas où les deux Functors (->) s et (->) t, et donc

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

il "compose" une fonction f :: a -> b avec une fonction de deux arguments, g :: s -> t -> a,

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

Ce point de vue aussi précise que, et comment, le modèle s'étend à des fonctions de la prise de plus d'arguments,

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

etc.

Answer 3

Votre solution diverge lorsque vous introduisez y. Il devrait être

\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

Qui correspond à l'original de la signature de type: (.) . (.) :: (c -> d) -> (a -> b -> c) -> a -> b -> d

(Il est plus facile de faire de l'expansion dans ghci, où vous pouvez vérifier chaque étape avec :t expression)

Edit:

Le plus profond intution est ceci:

(.) est simplement défini comme

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

Qui nous pouvons simplifier à

\f g x -> f (g x)

Ainsi, lorsque vous nous les fournissez de deux arguments, c'est au cari et a toujours besoin d'un autre argument à résoudre. Chaque fois que vous utilisez (.) avec 2 arguments, vous créez un "besoin" pour un argument de plus.

(.) . (.) n'est évidemment qu' (.) (.) (.), de sorte que nous allons développer:

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

Nous pouvons bêta-réduire les f0 et g0 (mais nous n'avons pas d' x0!):

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

Remplacer la 2ème expression pour f1...

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

Maintenant, il "revient"! (la bêta-réduction sur f2):
C'est l'étape intéressante - x0 est remplacé par f2 - Cela signifie qu' x, ce qui pourrait avoir été données, est plutôt une fonction.
C' est ce qu' (.) . (.) fournit -- la "nécessité" de l'argument supplémentaire.

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

Cela commence à sembler normal... Nous allons bêta-réduire une dernière fois (sur g2):

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

Donc, nous sommes la gauche tout simplement avec des

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

, où les arguments sont bien toujours dans l'ordre.

Answer 4

Donc, c'est ce que j'obtiens quand je fais un peu plus à l'augmentation incrémentielle

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

Qui, selon ghci a le bon type de

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> 

Alors que je ne connais pas les origines de cette combinator, il est probable que c'était développé pour une utilisation dans combinatoire logique, où vous travaillez exclusivement avec combinators, donc vous ne pouvez pas définir les choses à l'aide de plus pratique des expressions lambda. Il peut être une intuition qui va avec en pensant à ces choses, mais je n'ai pas trouvé. Très probablement, vous souhaitez développer un certain niveau de l'intuition si vous aviez à le faire.

Answer 5

Il est plus facile d'écrire des équations, combinators de style, au lieu de lambda-expressions: a b c = (\x -> ... body ...) est équivalent à a b c x = ... body ..., et vice versa, à condition qu' x ne figure pas au nombre {a,b,c}. Donc,

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

La découverte de cette si, compte tenu de f (g x y), vous voulez les convertir en une combinatoire forme (se débarrasser de tous les parenthèses et variable de répétitions). Ensuite, vous appliquez les modèles correspondant à la combinators " définitions, espérons-le traçage de cette dérivation vers l'arrière. C'est beaucoup moins mécanique/automatique si.