En Haskell, comment "appliquer" des fonctions en contexte imbriqué à une valeur en contexte ?

Question

nestedApply :: (Applicative f, Applicative g) => g (f (a -> b)) -> f a -> g (f b)

Comme le type l'indique, comment obtenir ce (a->b) appliqué à cette a dans le cadre f ?

Merci pour votre aide.

Answer 1

C'est un de ces cas où il est utile de se concentrer sur les types. Je vais essayer de rester simple et d'expliquer le raisonnement.

Commençons par décrire la tâche. Nous avons gfab :: g(f(a->b)) y fa :: f a et nous voulons avoir g(f b) .

gfab :: g (f (a -> b))
fa   :: f a
??1  :: g (f b)

Desde g est un foncteur, pour obtenir le type g T nous pouvons commencer par une valeur ??2 de type g U et appliquer fmap a ??3 :: U -> T . Dans notre cas, nous avons T = f b Nous sommes donc à la recherche de :

gfab :: g (f (a -> b))
fa   :: f a
??2  :: g U
??3  :: U -> f b
??1 = fmap ??3 ??2  :: g (f b)

Maintenant, on dirait qu'on devrait choisir ??2 = gfab . Après tout, c'est la seule valeur du type g Something nous avons. Nous obtenons U = f (a -> b) .

gfab :: g (f (a -> b))
fa   :: f a
??3  :: f (a -> b) -> f b
??1 = fmap ??3 gfab :: g (f b)

Faisons ??3 en un lambda, \ (x :: f (a->b)) -> ??4 con ??4 :: f b . (Le type de x peut être omis, mais j'ai décidé de l'ajouter pour expliquer ce qui se passe)

gfab :: g (f (a -> b))
fa   :: f a
??4  :: f b
??1 = fmap (\ (x :: f (a->b)) -> ??4) gfab :: g (f b)

Comment créer ??4 . Nous avons des valeurs de type f (a->b) y f a donc on peut <*> ceux pour obtenir f b . Nous obtenons finalement :

gfab :: g (f (a -> b))
fa   :: f a
??1 = fmap (\ (x :: f (a->b)) -> x <*> fa) gfab :: g (f b)

On peut simplement dire que :

nestedApply gfab fa = fmap (<*> fa) gfab

Certes, ce n'est pas la façon la plus élégante de procéder, mais il est important de comprendre le processus.

Answer 2

Avec

nestedApply :: (Applicative f, Applicative g) 
            => g (f (a -> b))  
            ->    f  a 
            -> g (f       b )

pour obtenir ce (a->b) appliqué à cette a dans le cadre f nous devons opérer dans le cadre g .

Et c'est juste fmap .

C'est plus clair avec la signature inversée, en se concentrant sur sa dernière partie.

flip nestedApply :: (Applicative f, Applicative g) 
            =>    f  a 
            -> g (f (a -> b))     --- from here
            -> g (f       b )     --- to here

Donc ce que nous avons ici est

nestedApply gffun fx = fmap (bar fx) gffun

avec bar fx en cours d'application en vertu de la g enveloppes par fmap pour nous. Ce qui est

bar fx ::         f (a -> b)
            ->    f       b   

es decir

bar ::            f  a
            ->    f (a -> b)
            ->    f       b   

et c'est juste <*> n'est-ce pas, encore une fois inversé. Ainsi nous obtenons la réponse,

nestedApply gffun fx  =  fmap (<*> fx) gffun

---

Comme on peut le voir, seulement fmap capacités de g sont utilisés, nous n'avons donc besoin que de

nestedApply :: (Applicative f, Functor g) => ...

dans la signature du type.

---

C'est facile en l'écrivant sur une feuille de papier, en 2D . Que nous imitons ici avec l'indentation sauvage pour obtenir cet alignement vertical.

_{Oui, nous, les humains, avons appris à <em>écrire </em>d'abord, sur papier, et à taper sur une machine à écrire, beaucoup plus tard. La dernière ou les deux dernières générations ont été forcées de taper linéairement sur les appareils contemporains dès leur plus jeune âge, mais <em>maintenant </em>le gribouillage et la parole (et les gestes et le pointage) prendront, on l'espère, une nouvelle fois le dessus. Les modes de saisie inventifs incluront éventuellement des flux de travail en 3D et <em>que </em>sera un progrès certain. 1D mauvais, 2D bon, 3D meilleur. Par exemple, de nombreux diagrammes de la théorie des catégories sont beaucoup plus faciles à suivre (et au moins à imaginer) lorsqu'ils sont dessinés en 3D. La règle de base est la suivante <em>facile </em>pas difficile. Si elle est trop chargée, elle a probablement besoin d'une autre dimension.}

Je joue juste connecter les fils sous le manteau. Quelques schémas évidents, et c'est fait.

---

Voici quelques mandalas de type pour vous (encore une fois, retournés) :

-- <$>               -- <*>               -- =<<
f     a              f     a              f     a       
     (a -> b)        f    (a -> b)             (a -> f b)
f          b         f          b         f    (     f b)   -- fmapped, and
                                          f            b    -- joined

et bien sûr, la mère de toutes les applications,

--      $
      a
      a -> b
           b

alias. Modus Ponens _{(oui, également retourné)} .