scala - Sets, Functors y confusión Eq

haskell equality (3)

Otro argumento en contra de que Set sea un Functor - es ampliamente aceptado que ser un Functor te permite transformar los "elementos" de una "colección" mientras se preserva la forma. [...] Claramente, cualquier instancia de functor para Set tiene la posibilidad de cambiar la forma, al reducir el número de elementos en el conjunto.

Me temo que este es un caso de tomar la analogía de "forma" como una condición definitoria cuando no lo es. Matemáticamente hablando, existe algo así como el functor del conjunto de poder. De la Wikipedia :

Conjuntos de potencia: el funcionador de conjunto de potencias P: Establecer → Establecer asigna cada conjunto a su conjunto de potencia y cada función f: X → Y al mapa que envía U ⊆ X a su imagen f (U) ⊆ Y.

La función P (f) ( fmap f en el functor de conjunto de potencias) no conserva el tamaño de su conjunto de argumentos, sin embargo, este es un funtor.

Si quiere una analogía intuitiva mal considerada, podríamos decir esto: en una estructura como una lista, cada elemento "se preocupa" por su relación con los otros elementos, y se "ofendería" si un functor falso rompiera esa relación . Pero un conjunto es el caso límite: una estructura cuyos elementos son indiferentes entre sí, por lo que hay muy poco que puede hacer para "ofenderlos"; lo único es si un functor falso asigna un conjunto que contiene ese elemento a un resultado que no incluye su "voz".

(Ok, me callaré ahora ...)

EDIT: trunqué los siguientes bits cuando te cité en la parte superior de mi respuesta:

Por ejemplo, esta cita en la wiki de Haskell (tenga en cuenta que Traversable es una generalización de Functor )
"Donde Foldable te da la posibilidad de pasar por la estructura procesando los elementos pero descartando la forma, Traversable te permite hacer eso mientras conservas la forma y, por ejemplo, introduces nuevos valores".
" Traversable se trata de preservar la estructura exactamente como está".

Aquí estoy, comentaré que Traversable es un tipo de Functor especializado , no una "generalización" de él. Uno de los datos clave sobre cualquier Traversable (o, en realidad, sobre Foldable , que Traversable extiende) es que requiere que los elementos de cualquier estructura tengan un orden lineal: puede convertir cualquier Traversable en una lista de sus elementos (con Foldable.toList ).

Otro hecho menos obvio sobre Traversable es que existen las siguientes funciones (adaptado de Gibbons y Oliveira, "La esencia del patrón del iterador" ):

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

Una instancia de Traversable para conjuntos violaría la ley propuesta, porque todos los conjuntos no vacíos tendrían la misma Shape , el conjunto cuyo Contents es [()] . A partir de esto, debería ser fácil probar que cada vez que intente reassemble a armar un conjunto, solo obtendrá el conjunto vacío o un singleton.

¿Lección? Traversable "preserva la forma" en un sentido muy específico y más fuerte que Functor .

Hace poco surgió una discusión sobre Sets, que en Scala admite el método zip y cómo esto puede conducir a errores, por ejemplo

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

Creo que está bastante claro que Set no debería admitir una operación zip , ya que los elementos no están ordenados. Sin embargo, se sugirió que el problema es que Set no es realmente un funtor y no debería tener un método de map . Ciertamente, puede meterse en problemas haciendo un mapeo sobre un conjunto. Cambiando a Haskell ahora,

data AlwaysEqual a = Wrap { unWrap :: a } instance Eq (AlwaysEqual a) where _ == _ = True instance Ord (AlwaysEqual a) where compare _ _ = EQ

y ahora en 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]

Entonces Set no cumple con la ley de funtores

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

Se puede argumentar que esto no es un fallo de la operación de map en Set s, sino un error de la instancia de Eq que definimos, porque no respeta la ley de sustitución, es decir, que para dos instancias de Eq en A y B y un mapeo f : A -> B entonces

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

que no es AlwaysEqual para AlwaysEqual (por ejemplo, considere f = unWrap ).

¿Es la ley de la substición una ley sensata para el tipo Eq que debemos tratar de respetar? Ciertamente, nuestro tipo AlwaysEqual respeta otras leyes de igualdad (la simetría, la transitividad y la reflexividad son triviales), por lo que la sustitución es el único lugar donde podemos tener problemas.

Para mí, la substición parece una propiedad muy deseable para la clase Eq . Por otro lado, algunos comentarios sobre una discusión reciente de Reddit incluyen

"La sustitución parece más fuerte de lo necesario, y básicamente está quotienting el tipo, poniendo requisitos en cada función usando el tipo".
- godofpumpkins
"Realmente tampoco quiero sustitución / congruencia ya que hay muchos usos legítimos para los valores que queremos igualar, pero que de alguna manera son distinguibles".
- sclv
"La sustitución solo vale para la igualdad estructural, pero nada insiste en que Eq es estructural".
- edwardkmett

Estos tres son muy conocidos en la comunidad de Haskell, por lo que dudaría en oponerme a ellos e insistir en la imposibilidad de mis tipos de ecualización.

Otro argumento en contra de que Set sea un Functor - es ampliamente aceptado que ser un Functor te permite transformar los "elementos" de una "colección" mientras se preserva la forma. Por ejemplo, esta cita en la wiki de Haskell (tenga en cuenta que Traversable es una generalización de Functor )

"Donde Foldable te da la posibilidad de pasar por la estructura procesando los elementos pero descartando la forma, Traversable te permite hacer eso mientras conservas la forma y, por ejemplo, introduces nuevos valores".
" Traversable se trata de preservar la estructura exactamente como está".

y en Real World Haskell

"... [Un] functor debe preservar la forma. La estructura de una colección no debe verse afectada por un funtor, solo deberían cambiar los valores que contiene".

Claramente, cualquier instancia de functor para Set tiene la posibilidad de cambiar la forma, al reducir el número de elementos en el conjunto.

Pero parece que Set s realmente debería ser funcionado (ignorando el requisito de Ord por el momento; lo veo como una restricción artificial impuesta por nuestro deseo de trabajar eficientemente con los conjuntos, no un requisito absoluto para ningún conjunto. Por ejemplo, conjuntos de las funciones son algo perfectamente razonable de considerar. En cualquier caso, Oleg ha mostrado cómo escribir instancias eficientes de Functor y Monad para Set que no requieren una restricción Ord ). Hay demasiados usos agradables para ellos (lo mismo es cierto para la instancia de Monad inexistente).

¿Alguien puede aclarar este lío? ¿Debería Set ser un Functor ? Si es así, ¿qué hace uno sobre el potencial de romper las leyes de Functor? ¿Cuáles deberían ser las leyes para Eq y cómo interactúan con las leyes para Functor y la instancia de Set en particular?

Bueno, Set puede tratarse como un functor covariante y como un functor contravariante; generalmente es un functor covariante. Y para que se comporte con respecto a la igualdad, uno debe asegurarse de que sea cual sea la implementación, lo hace.

En cuanto a Set.zip, no tiene sentido. Además de Set.head (lo tienes en Scala). No debería existir.

Set es "solo" un functor (no un Functor ) de la subcategoría de Hask, donde Eq es "agradable" (es decir, la subcategoría donde congruencia, sustitución, se mantiene). Si los tipos de restricciones existían desde mucho tiempo atrás , quizás establecer sería un Functor de algún tipo.