haskell - tipos - ¿Cómo se puede ajustar una restricción de clase en una instancia de una clase que requiere un constructor de tipo en lugar de un tipo concreto?

que es una instancia en c#

Question

Actualmente estoy en el Capítulo 8 de Learn you a Haskell , y he llegado a la sección sobre la clase de tipos de Functor . En dicha sección, el autor da ejemplos de cómo diferentes tipos se pueden convertir en instancias de la clase (por ejemplo, Maybe , un tipo de Tree personalizado, etc.) Viendo esto, decidí (por diversión y práctica) intentar implementar una instancia para los Data.Set Tipo de Data.Set en todo esto ignorando Data.Set.map , por supuesto.

La instancia real en sí es bastante sencilla, y la escribí como:

instance Functor Set.Set where
  fmap f empty = Set.empty
  fmap f s = Set.fromList $ map f (Set.elems s)  

Pero, dado que por casualidad utilizo la función fromList esto trae una restricción de clase que requiere que los tipos utilizados en el Set sean Ord , como se explica por un error del compilador:

Error occurred
ERROR line 4 - Cannot justify constraints in instance member binding
*** Expression    : fmap
*** Type          : Functor Set => (a -> b) -> Set a -> Set b
*** Given context : Functor Set
*** Constraints   : Ord b

Ver: Ejemplo en vivo

Intenté poner una restricción en la instancia o agregar una firma de tipo a fmap , pero ninguno de los dos tuvo éxito (ambos fueron errores del compilador también).

En una situación como esta, ¿cómo se puede cumplir y satisfacer una restricción? ¿Hay alguna forma posible?

¡Gracias por adelantado! :)

Answer 1

Desafortunadamente, no hay una manera fácil de hacer esto con la clase Functor estándar. Esta es la razón por la que Set no viene con una instancia de Functor por defecto: no puede escribir una.

Esto es algo así como un problema, y ​​se han sugerido algunas soluciones (por ejemplo, definir la clase Functor de una manera diferente), pero no sé si existe un consenso sobre la mejor manera de manejar esto.

Creo que un enfoque es volver a escribir la clase Functor utilizando clases de restricción para verificar las restricciones adicionales que pueden tener las instancias de la nueva clase Functor . Esto le permitiría especificar que Set tiene que contener tipos de la clase Ord .

Otro enfoque utiliza solo clases multiparamétricas. Solo pude encontrar el artículo sobre cómo hacer esto para la clase Monad , pero hacer que Set forme parte de Monad enfrenta los mismos problemas que hacerlo parte de Functor . Se llama mónadas restringidas .

La idea básica de usar clases de múltiples parámetros aquí parece ser algo como esto:

class Functor'' f a b where
  fmap'' :: (a -> b) -> f a -> f b

instance (Ord a, Ord b) => Functor'' Data.Set.Set a b where
  fmap'' = Data.Set.map

Esencialmente, todo lo que estás haciendo aquí es hacer que los tipos en el Set también Set parte de la clase. Esto le permite restringir lo que estos tipos pueden ser cuando escribe una instancia de esa clase.

Esta versión de Functor necesita dos extensiones: MultiParamTypeClasses y FlexibleInstances . (Necesita la primera extensión para poder definir la clase y la segunda extensión para poder definir una instancia para el Set ).

Haskell: ¿Un ejemplo de un Foldable que no es un Functor (o no es Traversable)? tiene una buena discusión sobre esto.

Answer 2

Esto es imposible. El propósito de la clase Functor es que si tienes Functor f => fa , puedes reemplazar la a con lo que quieras. La clase no tiene permitido restringirte para que solo devuelvas esto o aquello. Dado que Set requiere que sus elementos satisfagan ciertas restricciones (y, de hecho, esto no es un detalle de implementación sino una propiedad esencial de los conjuntos), no cumple con los requisitos de Functor .

Hay, como se mencionó en otra respuesta, formas de desarrollar una clase como Functor que lo restringe de esa manera, pero en realidad es una clase diferente, porque le da al usuario de la clase menos garantías (no puede usar esta con cualquier parámetro de tipo que desee), a cambio de ser aplicable a una gama más amplia de tipos. Esto es, después de todo, el compromiso clásico de definir una propiedad de tipos: cuantos más tipos quieras satisfacer, menos deben ser obligados a cumplir.

(Otro ejemplo interesante de dónde se muestra esto es la clase MonadPlus . En particular, para cada instancia de MonadPlus TC puede crear un Monoid (TC a) instancia Monoid (TC a) , pero no siempre puede ir al revés. Por lo tanto, el Monoid (Maybe a) instancia es diferente de la instancia de MonadPlus Maybe , porque la primera puede restringir la a pero la segunda no puede).

Answer 3

Puedes hacer esto usando un Functor CoYoneda.

{-# LANGUAGE GADTs #-}

data CYSet a where
    CYSet :: (Ord a) => Set.Set a -> (a -> b) -> CYSet b

liftCYSet :: (Ord a) => Set.Set a -> CYSet a
liftCYSet s = CYSet s id

lowerCYSet :: (Ord a) => CYSet a -> Set.Set a
lowerCYSet (CYSet s f) = Set.fromList $ map f $ Set.elems s

instance Functor CYSet where
  fmap f (CYSet s g) = CYSet s (f . g)

main = putStrLn . show
  $ lowerCYSet
  $ fmap (/x -> x `mod` 3)
  $ fmap abs
  $ fmap (/x -> x - 5)
  $ liftCYSet $ Set.fromList [1..10]
-- prints "fromList [0,1,2]"