Ensembles, foncteurs et confusion Eq

Question

Une discussion a eu jusqu'à récemment, sur les Jeux, qui, à la Scala de soutien de l' zip méthode et comment cela peut conduire à des bugs, par exemple

scala> val words = Set("one", "two", "three")
scala> words zip (words map (_.length))
res1: Set[(java.lang.String, Int)] = Set((one,3), (two,5))

Je pense qu'il est assez clair que l' Sets ne prennent pas en charge l' zip de l'opération, puisque les éléments ne sont pas commandés. Cependant, il a été suggéré que le problème est qu' Set n'est pas vraiment un foncteur, et ne devrait pas avoir un map méthode. Certainement, vous pouvez avoir des ennuis par la cartographie sur un jeu. Commutation de Haskell maintenant,

data AlwaysEqual a = Wrap { unWrap :: a }

instance Eq (AlwaysEqual a) where
    _ == _ = True

instance Ord (AlwaysEqual a) where
    compare _ _ = EQ

et maintenant, dans ghci

ghci> import Data.Set as Set
ghci> let nums = Set.fromList [1, 2, 3]
ghci> Set.map unWrap $ Set.map Wrap $ nums
fromList [3]
ghci> Set.map (unWrap . Wrap) nums
fromList [1, 2, 3]

Donc, Set ne parvient pas à satisfaire le foncteur de la loi

    fmap f . fmap g = fmap (f . g)

Il peut être soutenu que ce n'est pas un défaut de l' map opération sur Sets, mais un défaut de l' Eq exemple que nous avons défini, parce qu'il ne respecte pas la substitution de la loi, à savoir que, pour les deux instances de l' Eq sur A et B et une correspondance f : A -> B alors

    if x == y (on A) then f x == f y (on B)

qui ne tient pas pour AlwaysEqual (p. ex. examiner f = unWrap).

Est la substition droit raisonnable de la loi pour l' Eq type que nous devrions essayer de respecter? Certes, d'autres lois sur l'égalité sont respectés par nos AlwaysEqual type (symétrie, transitivité et la réflexivité sont trivialement satisfaites) si la substitution est le seul endroit que nous pouvons avoir des ennuis.

Pour moi, substition semble comme une propriété souhaitable pour l' Eq classe. D'autre part, certains commentaires sur une récente discussion Reddit inclure

"La Substitution semble plus fort que nécessaire, et il est essentiel de quotienting le type, mettant exigences sur chaque fonction à l'aide du type."

-- godofpumpkins

"Je ne veux vraiment pas de substitution/congruence car il existe de nombreuses utilisations légitimes des valeurs que nous voulons assimiler, mais sont en quelque sorte de se distinguer."

-- sclv

"La Substitution ne détient pour l'égalité structurelle, mais rien n'insiste Eq est structurelle."

-- edwardkmett

Ces trois-là sont tous assez bien connu dans le Haskell communauté, donc, j'avais hésiter à aller à leur encontre et d'insister sur substitability pour ma Eq types!

Un autre argument contre l' Set être Functor - il est largement admis que le fait d'être un Functor permet de transformer les "éléments" d'une "collection" tout en préservant la forme. Par exemple, cette citation sur le Haskell wiki (à noter qu' Traversable est une généralisation de l' Functor)

"Où Foldable vous donne la possibilité de passer par la transformation de la structure des éléments, mais de jeter la forme, Traversable vous permet de le faire tout en préservant la forme et, par exemple, l'instauration de nouvelles valeurs."

"Traversable est sur la préservation de la structure exactement comme elle est."

et dans le Monde Réel Haskell

"...[Un] foncteur doit conserver la forme. La structure d'une collection ne devrait pas être affectée par un foncteur; seules les valeurs qu'il contient doivent changer."

De toute évidence, toute instance de functor pour Set a la possibilité de changer la forme, en réduisant le nombre d'éléments de l'ensemble.

Mais il semble que l' Sets doit être vraiment foncteurs (en ignorant l' Ord exigence pour l'instant - je vois que comme une restriction artificielle imposée par notre désir de travailler efficacement avec les jeux, pas une exigence absolue pour n'importe quel jeu. Par exemple, des ensembles de fonctions sont parfaitement sensée chose à considérer. En tout cas, Oleg a montré comment écrire efficace Foncteur et Monade instances pour Set qui ne nécessitent pas un Ord contrainte). Il y a juste trop de nice utilise pour eux (la même chose est vraie pour la non-existantes Monad exemple).

Quelqu'un peut-il éclaircir ce gâchis? Devrait - Set être Functor? Si oui, que fait-on faire à propos du risque de casser le Foncteur lois? Ce qui devrait lois sur le droit d' Eq , et comment interagissent-ils avec les lois sur le droit d' Functor et de la Set instance en particulier?

Answer 1

Un autre argument contre l' Set être Functor - il est largement admis que le fait d'être un Functor permet de transformer les "éléments" d'une "collection" tout en préservant la forme. [...] Il est évident que tout foncteur exemple pour le Jeu a la possibilité de changer la forme, en réduisant le nombre d'éléments de l'ensemble.

Je crains que ce est un cas de prendre la "forme" de l'analogie comme une définition de l'état, quand il ne l'est pas. Mathématiquement parlant, il ya une chose telle que la puissance de foncteur. De Wikipedia:

Ensembles de pouvoirs: La puissance du foncteur P : Set → Set des cartes de chaque jeu à sa puissance et chaque fonction f : X → Y à la carte qui envoie U ⊆ X à son image f(U) ⊆ Y.

La fonction P(f) (fmap f de la puissance du foncteur) ne permet pas de conserver la taille de sa thèse, mais il s'agit néanmoins d'un foncteur.

Si vous souhaitez un mal intuitive analogie, nous pourrions dire ceci: dans une structure comme une liste, chaque élément de "soucis" à propos de sa relation avec les autres éléments, et qu'il serait "offensé" si un faux foncteur ont été de briser cette relation. Mais d'un ensemble est le cas limite: une structure dont les éléments sont indifférents les uns aux autres, donc il ya très peu que vous pouvez faire pour "offenser"; la seule chose est de savoir si un faux foncteur étaient à la carte d'un ensemble qui contient l'élément à un résultat qui ne comprend pas son "la voix."

(Ok, je vais me taire maintenant...)

---

EDIT: j'ai tronqué les bits suivants lorsque je vous ai cité en haut de ma réponse:

Par exemple, cette citation sur le Haskell wiki (à noter qu' Traversable est une généralisation de l' Functor)

"Où Foldable vous donne la possibilité de passer par la transformation de la structure des éléments, mais de jeter la forme, Traversable vous permet de le faire tout en préservant la forme et, par exemple, l'instauration de nouvelles valeurs."

"Traversable est sur la préservation de la structure exactement comme elle est."

Ici, j'ai remarque qu' Traversable est une sorte de spécialisée Functor, pas une "généralisation". L'un des principaux faits à propos de tout Traversable (ou, en fait, à propos de Foldable, Traversable s'étend), c'est qu'il exige que les éléments de la structure ont un ordre linéaire-vous pouvez transformer n'importe quel Traversable dans une liste de ses éléments ( Foldable.toList).

Un autre, moins évidente à propos de Traversable , c'est que les fonctions suivantes existent (adapté de Gibbons & Oliveira, "L'Essence de l'Itérateur Pattern"):

-- | A "shape" is a Traversable structure with "no content," 
-- i.e., () at all locations.
type Shape t = t ()

-- | "Contents" without a shape are lists of elements.
type Contents a = [a]

shape :: Traversable t => t a -> Shape t
shape = fmap (const ())

contents :: Traversable t => t a -> Contents a
contents = Foldable.toList

-- | This function reconstructs any Traversable from its Shape and
-- Contents.  Law:
--
-- > reassemble (shape xs) (contents xs) == Just xs
--
-- See Gibbons & Oliveira for implementation.  Or do it as an exercise.
-- Hint: use the State monad...
--
reassemble :: Traversable t => Shape t -> Contents a -> Maybe (t a)

Un Traversable exemple pour les jeux de contreviendrait à la proposition de loi, parce que tous les non-vide ensembles ont le même Shape-dont Contents est [()]. De ce fait, il devrait être facile de prouver que chaque fois que vous essayez d' reassemble un jeu que vous ne jamais obtenir l'ensemble vide ou un singleton en arrière.

Leçon? Traversable "conserve forme" dans un très spécifique, sentiment plus fort que Functor .

Answer 2

Set est "juste" un foncteur (pas un Functor ) de la sous-catégorie de Hask où Eq est "sympa" (c'est-à-dire la sous-catégorie où la congruence, la substitution, est vérifiée). Si les types de contraintes existaient déjà il y a longtemps, peut-être que défini serait un Functor quelconque.

Answer 3

Eh bien, Set peut être traité comme un foncteur covariant et comme un foncteur contravariant; c'est habituellement un foncteur covariant. Et pour qu’elle se comporte en matière d’égalité, il faut s’assurer que quelle que soit la mise en œuvre, elle le fait.

En ce qui concerne Set.zip - c'est un non-sens. Ainsi que Set.head (vous l'avez en Scala). Cela ne devrait pas exister.