Escriba restricciones de parámetros para las instancias de tipos de clase con tipo * -> *

Question

Supongamos que tengo Heap a tipo donde Heap es un constructor de tipo * -> *. Muchas operaciones básicas en montón requieren que el tipo a sea una instancia de la clase de tipo Ord.

data Heap a = ... 

findMin :: Ord a => Heap a -> a 
deleteMin :: Ord a => Heap a -> Heap a 

quiero declarar mi tipo Heap como una instancia de la clase Foldable del modelo en cuanto a parámetro de tipo es una instancia de la clase Ord tipo (que será fácil de expresar a través de findMin y deleteMin funciones).

Este tipo de relación se puede easely expresó cuando se trata de clases de tipos que requieren el tipo de especie *, como Show:

instance Show a => Show (Heap a) where 
    show h = ... 

Pero no tengo problemas con la declaración de Foldable:

instance Foldable Heap where 
    -- Ouch, there is no `a` type parameter to put the constraint on! 
    foldr f z h = ... 

¿Es posible poner una restricción en el parámetro de tipo a en dicha declaración de instancia?

Answer 1

En general, no, cuando al propio constructor de tipos se le da la instancia, no hay forma de restringir los tipos a los que se aplica. En general, esto es algo bueno, ya que garantiza que, p. Functor las instancias son realmente agnósticas sobre su tipo de elemento, lo que ayuda a mantener un comportamiento agradable y predecible agradable y predecible.

A veces es una molestia, y el ejemplo más común de hecho necesita una restricción Ord para una estructura de datos ordenada que, de lo contrario, podría ser una instancia agradable y con buen comportamiento.

Existen algunas técnicas experimentales que incluyen cosas como tipos de restricciones, pero en su caso específico ya existe una solución viable. Si nos fijamos en la definición de Foldable, dice que solo se deben implementar foldMap o foldr, por lo que los consideraremos. Tenga en cuenta los tipos:

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m 
foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b 

En ambos casos, el tipo con una instancia Foldable sólo aparece una vez, como un argumento a la función. Debido a esto, se puede use GADTs con un Ord restricción:

data Heap a where 
    Heap :: (Ord a) => ... 

Al hacer esto, usted necesitará una instancia Ord cualquier momento que crear un valor Heap, incluso un montón vacío; pero cuando recibe un valor de Heap, la coincidencia de patrones en él traerá la instancia Ord de vuelta al ámbito, incluso dentro de la instancia Foldable.

Tenga en cuenta que esto no ayuda en muchas otras situaciones:

fmap :: (Functor f) => (a -> b) -> f a -> f b 

Aquí podemos obtener una instancia Ord en a, pero también iba a necesitar una para b, que no es posible.

return :: (Monad m) => a -> m a 

Aquí tenemos que proporcionar una instancia de Ord también.

Answer 2

Eche un vistazo a la biblioteca keys en Hackage. Compruebe si su clase de tipo FoldableWithKey es lo que necesita.