Conjuntos, Funtores y Eq confusión

Una discusión surgió recientemente en el trabajo sobre los Conjuntos, que en Scala soportan 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 s no debería soportar 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 map. Ciertamente, usted puede meterse en problemas mediante el mapeo de un conjunto. Cambiar 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]

Así que Set no satisface la ley del funtor

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

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

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

Que no se sostiene para AlwaysEqual (por ejemplo, considere f = unWrap).

Es la ley de sustitución a ¿ley sensata para el tipo Eq que debemos tratar de respetar? Ciertamente, otras leyes de igualdad son respetadas por nuestro tipo AlwaysEqual (la simetría, la transitividad y la reflexividad están trivialmente satisfechas) por lo que la sustitución es el único lugar en el que podemos meternos en 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 es básicamente cociente el tipo, poniendo requisitos en cada función usando el tipo."

-- godofpumpkins

"También realmente no quiero sustitución/congruencia ya que hay muchos usos legítimos para valores que queremos equiparar pero que de alguna manera son distinguibles."

-- sclv

"La sustitución solo es válida para la igualdad estructural, pero nada insiste en que Eq es estructural."

-- edwardkmett

Estos tres son todos bastante conocidos en la comunidad Haskell, así que dudaría en ir en contra de ellos e insistir en la sustitución de mis Eq tipos!

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

"Donde Foldable le da la capacidad de ir a través de la estructura procesando los elementos pero desechando la forma, Traversable le permite hacer eso mientras preserva la forma y, por ejemplo, poniendo nuevos valores."

"Traversable se trata de preservar la estructura exactamente como está."

Y en el Mundo Real Haskell

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

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

Pero parece como si Set s realmente deberían ser funtores (ignorando el requisito Ord por el momento - lo veo como una restricción artificial impuesta por nuestro deseo de trabajar eficientemente con conjuntos, no un requisito absoluto para cualquier conjunto. Por ejemplo, los conjuntos de funciones son una cosa perfectamente sensata a considerar. En cualquier case, Oleg ha mostrado cómo escribir instancias eficientes de Funtor y Mónada para Set que no requieren una restricción Ord). Hay demasiados usos agradables para ellos (lo mismo es cierto para la instancia no existente Monad).

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