Bons exemples de Pas un Functor / Functor / Applicative / Monad?

Tout en expliquant à quelqu’un ce qu’est une classe de type X, j’ai du mal à trouver de bons exemples de structures de données qui sont exactement X.

Donc, je demande des exemples pour:

  • Un constructeur de type qui n’est pas un foncteur.
  • Un constructeur de type qui est un foncteur, mais pas applicatif.
  • Un constructeur de type qui est un applicatif, mais n’est pas une monade.
  • Un constructeur de type qui est une monade.

Je pense qu’il y a beaucoup d’exemples de Monad partout, mais un bon exemple de Monad avec des exemples précédents pourrait compléter le tableau.

Je cherche des exemples qui seraient similaires les uns des autres, ne différant que par des aspects importants pour l’appartenance à une classe de type particulière.

Si on pouvait arriver à trouver un exemple de Arrow quelque part dans cette hiérarchie (est-ce entre Applicative et Monad?), Ce serait bien aussi!

    Un constructeur de type qui n’est pas un foncteur:

     newtype T a = T (a -> Int) 

    Vous pouvez en faire un foncteur contravariant, mais pas un foncteur (covariant). Essayez d’écrire fmap et vous fmap . Notez que la version du foncteur contravariant est inversée:

     fmap :: Functor f => (a -> b) -> fa -> fb contramap :: Contravariant f => (a -> b) -> fb -> fa 

    Un constructeur de type qui est un foncteur, mais pas applicatif:

    Je n’ai pas un bon exemple. Il y a Const , mais idéalement, je voudrais un non-monoïde concret et je ne peux pas en penser. Tous les types sont essentiellement numériques, énumérés, produits, sums ou fonctions lorsque vous y arrivez. Vous pouvez voir ci-dessous pigworker et je ne suis pas d’accord sur le fait de savoir si Data.Void est un Monoid ;

     instance Monoid Data.Void where mempty = undefined mappend _ _ = undefined mconcat _ = undefined 

    Puisque _|_ est une valeur légale dans Haskell, et en fait la seule valeur légale de Data.Void , cela répond aux règles de Data.Void . Je ne sais pas ce que unsafeCoerce a à faire avec cela, car votre programme n’est plus garanti de ne pas violer la sémantique Haskell dès que vous utilisez une fonction unsafe .

    Voir le wiki Haskell pour un article sur le bas ( lien ) ou des fonctions dangereuses ( lien ).

    Je me demande s’il est possible de créer un tel constructeur de type en utilisant un système de type plus riche, tel qu’Agda ou Haskell avec différentes extensions.

    Un constructeur de type qui est une application, mais pas une monade:

     newtype T a = T {multidimensional array of a} 

    Vous pouvez en faire une application, avec quelque chose comme:

     mkarray [(+10), (+100), id] < *> mkarray [1, 2] == mkarray [[11, 101, 1], [12, 102, 2]] 

    Mais si vous en faites une monade, vous risquez d’obtenir une incohérence de dimension. Je soupçonne que de tels exemples sont rares dans la pratique.

    Un constructeur de type qui est une monade:

     [] 

    A propos des flèches:

    Demander où se trouve une flèche sur cette hiérarchie revient à demander quel type de forme est “rouge”. Notez le manque de correspondance:

     Functor :: * -> * Applicative :: * -> * Monad :: * -> * 

    mais,

     Arrow :: * -> * -> * 

    Mon style peut être à l’étroit avec mon téléphone, mais voilà.

     newtype Not x = Kill {kill :: x -> Void} 

    ne peut pas être un foncteur. Si c’était le cas, nous aurions

     kill (fmap (const ()) (Kill id)) () :: Void 

    et la lune serait faite de fromage vert.

    pendant ce temps

     newtype Dead x = Oops {oops :: Void} 

    est un foncteur

     instance Functor Dead where fmap f (Oops corpse) = Oops corpse 

    mais ne peut pas être applicable, ou nous aurions

     oops (pure ()) :: Void 

    et Green serait fait de fromage de lune (ce qui peut effectivement se produire, mais seulement plus tard dans la soirée).

    (Remarque supplémentaire: Data.Void , car Data.Void est un type de données vide. Si vous essayez d’utiliser undefined pour prouver qu’il s’agit d’un monoïde, j’utiliserai unsafeCoerce pour prouver que ce n’est pas le cas.)

    Joyeusement,

     newtype Boo x = Boo {boo :: Bool} 

    est applicable à bien des égards, par exemple, comme le voudrait Dijkstra,

     instance Applicative Boo where pure _ = Boo True Boo b1 < *> Boo b2 = Boo (b1 == b2) 

    mais ça ne peut pas être une Monade. Pour voir pourquoi pas, observez que le retour doit être constamment Boo True ou Boo False , et par conséquent que

     join . return == id 

    ne peut pas tenir

    Oh oui, j’ai presque oublié

     newtype Thud x = The {only :: ()} 

    est une monade. Rouler le vôtre

    Avion à attraper …

    Je crois que les autres réponses ont manqué des exemples simples et communs:

    Un constructeur de type qui est un foncteur mais pas un applicatif. Un exemple simple est une paire:

     instance Functor ((,) r) where fmap f (x,y) = (x, fy) 

    Mais il n’y a aucun moyen de définir son instance Applicative sans imposer de ressortingctions supplémentaires sur r . En particulier, il n’y a aucun moyen de définir pure :: a -> (r, a) pour un r arbitraire.

    Un constructeur de type qui est un applicatif, mais n’est pas une monade. Un exemple bien connu est ZipList . (C’est un newtype qui encapsule les listes et fournit des instances Applicative différentes pour eux.)

    fmap est défini de la manière habituelle. Mais pure et < *> sont définis comme

     pure x = ZipList (repeat x) ZipList fs < *> ZipList xs = ZipList (zipWith id fs xs) 

    si pure crée une liste infinie en répétant la valeur donnée, et < *> zippe une liste de fonctions avec une liste de valeurs – applique la iième fonction au iième élément. (Le standard < *> sur [] produit toutes les combinaisons possibles d’application de la ième fonction à j


    Comment les flèches s’intègrent-elles dans la hiérarchie foncteur / applicatif / monade? Voir les idiomes sont inconscients, les flèches sont méticuleuses, les monades sont prometteuses par Sam Lindley, Philip Wadler, Jeremy Yallop. MSFP 2008. (Ils appellent idiomes de foncteurs applicatifs.) Le résumé:

    Nous revenons sur le lien entre trois notions de calcul: les monades de Moggi, les flèches de Hughes et les idiomes de McBride et Paterson (également appelés foncteurs applicatifs). Nous montrons que les idiomes sont équivalents aux flèches qui satisfont au type isomorphisme A ~> B = 1 ~> (A -> B) et que les monades sont équivalentes aux flèches qui satisfont au type isomorphisme A ~> B = A -> (1 ~ > B). De plus, les idiomes s’enfoncent dans des flèches et des flèches incorporées dans des monades.

    Un bon exemple pour un constructeur de type qui n’est pas un foncteur est Set : Vous ne pouvez pas implémenter fmap :: (a -> b) -> fa -> fb , car sans une contrainte supplémentaire Ord b vous ne pouvez pas construire fb .

    Je voudrais proposer une approche plus systématique pour répondre à cette question, et aussi montrer des exemples qui n’utilisent pas de trucs spéciaux comme les valeurs “bas” ou les types de données infinis ou quelque chose du genre.

    Quand les constructeurs de types ne parviennent-ils pas à avoir des instances de classe de type?

    En général, un constructeur de type peut échouer à avoir une instance d’une certaine classe de type pour deux raisons:

    1. Impossible d’implémenter les signatures de type des méthodes requirejses à partir de la classe de type.
    2. Peut implémenter les signatures de type mais ne peut pas satisfaire les lois requirejses.

    Les exemples du premier type sont plus faciles que ceux du second type car pour le premier type, il suffit de vérifier si on peut implémenter une fonction avec une signature de type donnée, alors que pour le second, il faut prouver qu’aucune implémentation pourrait éventuellement satisfaire aux lois.

    Exemples spécifiques

    • Un constructeur de type qui ne peut pas avoir d’instance de foncteur car le type ne peut pas être implémenté:

    data F a = F (a -> Int)

    Ceci est un contrafunctor, pas un foncteur, car il utilise le paramètre de type a dans une position contravariante. Il est impossible d’implémenter une fonction avec signature de type (a -> b) -> F a -> F b .

    • Un constructeur de type qui n’est pas un foncteur légal même si la signature de type de fmap peut être implémentée:

    data Q a = Q(a -> Int, a) fmap :: (a -> b) -> Q a -> Q b fmap f (Q(g, x)) = Q(\_ -> gx, fx) -- this fails the functor laws!

    L’aspect curieux de cet exemple est que nous pouvons implémenter fmap du type correct, même si F ne peut pas être un foncteur, car il utilise a position contravariante. Donc, cette implémentation de fmap présentée ci-dessus est trompeuse – même si elle a la signature de type correcte (je crois que c’est la seule implémentation possible de cette signature de type), les lois de foncteur ne sont pas satisfaites (cela nécessite des calculs simples).

    En fait, F n’est qu’une source, ce n’est ni un foncteur ni un contrefoncteur.

    • Un foncteur licite qui n’est pas applicatif car la signature de type de pure ne peut être implémentée: prenez la monade Writer (a, w) et supprimez la contrainte que w devrait être un monoïde. Il est alors impossible de construire une valeur de type (a, w) sur a .

    • Un foncteur non applicatif car la signature de type de < *> ne peut pas être implémentée: data F a = Either (Int -> a) (Ssortingng -> a) .

    • Un foncteur qui n’est pas applicatif légal même si les méthodes de classe de type peuvent être implémentées:

    data P a = P ((a -> Int) -> Maybe a)

    Le constructeur de type P est un foncteur car il utilise uniquement des positions covariantes.

     instance Functor P where fmap :: (a -> b) -> P a -> P b fmap fab (P pa) = P (\q -> fmap fab $ pa (q . fab)) 

    La seule implémentation possible de la signature de type de < *> est une fonction qui renvoie toujours Nothing :

      (< *>) :: P (a -> b) -> P a -> P b (P pfab) < *> (P pa) = \_ -> Nothing -- fails the laws! 

    Mais cette implémentation ne satisfait pas la loi d’identité pour les foncteurs applicatifs.

    • Un foncteur qui est Applicative mais pas une Monad car la signature de type de bind ne peut pas être implémentée.

    Je ne connais pas de tels exemples!

    • Un foncteur qui est Applicative mais pas une Monad car les lois ne peuvent pas être satisfaites même si la signature de type de bind peut être implémentée.

    Cet exemple a suscité pas mal de discussions, donc il est prudent de dire que prouver que cet exemple est correct n’est pas facile. Mais plusieurs personnes l’ont vérifié indépendamment par différentes méthodes. Voir Is `data PoE a = vide | Paire aa une monade? pour une discussion supplémentaire.

      data B a = Maybe (a, a) deriving Functor instance Applicative B where pure x = Just (x, x) b1 < *> b2 = case (b1, b2) of (Just (x1, y1), Just (x2, y2)) -> Just((x1, x2), (y1, y2)) _ -> Nothing 

    Il est un peu lourd de prouver qu’il n’y a pas d’instance légitime de Monad . La raison de ce comportement non monadique est qu’il n’ya pas de moyen naturel d’implémenter bind quand une fonction f :: a -> B b pourrait renvoyer Nothing ou Just pour différentes valeurs de a .

    Il est peut-être plus clair de considérer Maybe (a, a, a) , qui n’est pas non plus une monade, et d’essayer d’implémenter la join pour cela. On trouvera qu’il n’y a pas de moyen intuitivement raisonnable d’implémenter la join .

      join :: Maybe (Maybe (a, a, a), Maybe (a, a, a), Maybe (a, a, a)) -> Maybe (a, a, a) join Nothing = Nothing join Just (Nothing, Just (x1,x2,x3), Just (y1,y2,y3)) = ??? join Just (Just (x1,x2,x3), Nothing, Just (y1,y2,y3)) = ??? -- etc. 

    Dans les cas indiqués par ??? , il semble clair que nous ne pouvons pas produire Just (z1, z2, z3) de manière raisonnable et symésortingque sur six valeurs différentes de type a . Nous pourrions certainement choisir un sous-ensemble arbitraire de ces six valeurs – par exemple, toujours prendre le premier non vide – MaybeMaybe – mais cela ne satisferait pas les lois de la monade. Retour Nothing ne satisfera également les lois.

    • Une structure de données arborescente qui n’est pas une monade même si elle est associative pour bind – mais ne respecte pas les lois d’identité.

    La monade habituelle en forme d’arbre (ou “un arbre avec des twigs en forme de foncteur”) est définie comme

      data Tr fa = Leaf a | Branch (f (Tr fa)) 

    Ceci est une monade libre sur le foncteur f . La forme des données est un arbre où chaque sharepoint twigment est un “foncteur-ful” de sous-arborescence. L’arbre binary standard serait obtenu avec le type fa = (a, a) .

    Si nous modifions cette structure de données en faisant aussi les feuilles dans la forme du foncteur f , nous obtenons ce que j’appelle une “semimonad” – elle a bind qui satisfait les lois de naturalité et d’associativité, mais sa méthode pure échoue. lois. “Les semimonades sont des semigroupes dans la catégorie des endofuncteurs, quel est le problème?” C’est la classe de type Bind .

    Pour simplifier, je définis la méthode de join au lieu de bind :

      data Trs fa = Leaf (fa) | Branch (f (Trs fa)) join :: Trs f (Trs fa) -> Trs fa join (Leaf ftrs) = Branch ftrs join (Branch ftrstrs) = Branch (fmap @f join ftrstrs) 

    La greffe de twig est standard, mais la greffe de feuilles est non standard et produit une Branch . Ce n’est pas un problème pour la loi sur l’associativité mais enfreint l’une des lois sur l’identité.

    Quand les types polynomiaux ont-ils des instances de monade?

    Aucun des foncteurs Maybe (a, a) et Maybe (a, a, a) ne peut recevoir une instance Monad légitime, bien qu’ils soient évidemment Applicative .

    Ces foncteurs n’ont aucune astuce – pas de Void ou de bottom nulle part, pas de paresse / sévérité délicate, pas de structures infinies et pas de contraintes de classe de type. L’instance Applicative est complètement standard. Les fonctions return et bind peuvent être implémentées pour ces foncteurs mais ne satisferont pas les lois de la monade. En d’autres termes, ces foncteurs ne sont pas des monades car une structure spécifique est manquante (mais il n’est pas facile de comprendre ce qui manque exactement). Par exemple, un petit changement dans le foncteur peut en faire un monad: data Maybe a = Nothing | Just a data Maybe a = Nothing | Just a est une monade. Un autre foncteur similaire data P12 a = Either a (a, a) est aussi une monade.

    Constructions pour les monades polynomiales

    En général, voici quelques constructions qui produisent des Monad légales à partir de types polynomiaux. Dans toutes ces constructions, M est une monade:

    1. type M a = Either c (w, a)w est un monoïde
    2. type M a = m (Either c (w, a))m est une monade et w un monoïde
    3. type M a = (m1 a, m2 a)m1 et m2 sont des monades
    4. type M a = Either a (ma)m est une monade

    La première construction est WriterT w (Either c) , la deuxième construction est WriterT w (EitherT cm) . La troisième construction est un produit de type monades pure @M sur les composants: pure @M est défini comme le produit de pure @m1 et pure @m2 join @M , et join @M est défini en omettant les données inter-produits (par exemple, m1 (m1 a, m2 a) est mappé sur m1 (m1 a) en omettant la deuxième partie du tuple):

      join :: (m1 (m1 a, m2 a), m2 (m1 a, m2 a)) -> (m1 a, m2 a) join (m1x, m2x) = (join @m1 (fmap fst m1x), join @m2 (fmap snd m2x)) 

    La quasortingème construction est définie comme

      data M ma = Either a (ma) instance Monad m => Monad M m where pure x = Left x join :: Either (M ma) (m (M ma)) -> M ma join (Left mma) = mma join (Right me) = Right $ join @m $ fmap @m squash me where squash :: M ma -> ma squash (Left x) = pure @mx squash (Right ma) = ma 

    J’ai vérifié que les quatre constructions produisent des monades légitimes.

    Je conjecture qu’il n’y a pas d’autres constructions pour les monades polynomiales. Par exemple, le foncteur Maybe (Either (a, a) (a, a, a, a)) n’est obtenu par aucune de ces constructions et n’est donc pas monadique. Cependant, Either (a, a) (a, a, a) est monadique car il est isomorphe au produit de trois monades a , a et Maybe a . De même, Either (a,a) (a,a,a,a) est monadique car il est isomorphe au produit de a et Either a (a, a, a) .

    Les quatre constructions présentées ci-dessus nous permettront d’obtenir toute sum d’un nombre quelconque de produits d’un nombre quelconque de a , par exemple Either (Either (a, a) (a, a, a, a)) (a, a, a, a, a)) et ainsi de suite. Tous les constructeurs de ce type auront (au moins un) instance de Monad .

    Il rest à voir, bien sûr, quels cas d’utilisation pourraient exister pour de telles monades. Un autre problème est que les instances Monad dérivées via les constructions 1-4 ne sont généralement pas uniques. Par exemple, le constructeur de type F a = Either a (a, a) peut être donné une instance de Monad de deux manières: par construction 4 en utilisant la monade (a, a) , et par construction 3 en utilisant le type isomorphisme Either a (a, a) = (a, Maybe a) . Encore une fois, trouver des cas d’utilisation pour ces implémentations n’est pas immédiatement évident.

    Une question rest posée: avec un type de données polynomial arbitraire, comment reconnaître si elle a une instance Monad . Je ne sais pas comment prouver qu’il n’y a pas d’autres constructions pour les monades polynomiales. Je pense qu’aucune théorie n’existe jusqu’à présent pour répondre à cette question.