Haskell: ¿Cómo puedo definir una clase de tipo para conjuntos?

Question

Novato total aquí, luchando.

Estoy tratando de definir una clase de tipo para los conjuntos. Para este caso solo requeriría la definición de 'existe'. 'exists' tomaría un conjunto y una función en un elemento de conjunto, y devolvería 0 un booleano. ¿Cómo puedo definir eso en Haskell?

¿Está lo siguiente incluso en la dirección correcta? Así que no es la definición de clase y un tipo implementación de conjunto con la lista, por lo que 'existe' devuelve cierto por ahora ..

-- Set.hs -- 

class Set a b where 

    exists :: a -> (b -> Bool) -> Bool 


-- ListSet.hs -- 

instance Set ListSet a where 

    exists a f = True 

-

(resultado: Demasiados parámetros para la clase `set ')

Answer 1

Puede hacerlo de esta manera, con suficientes extensiones. Por lo menos, necesitará clases de tipo de parámetros múltiples. Sin embargo, será muy molesto de usar: tendrá que especificar firmas de tipo explícitas en todo el lugar. Una forma de solucionarlo es introducir una dependencia funcional (utilizando otra extensión):

class Set a b | a -> b where 
    exists :: a -> (b -> Bool) -> Bool 

Esto dice que si se conoce el tipo de conjunto, se conoce el tipo de los elementos, también. Sin embargo, hay una manera más sencilla que funciona sin ningún tipo de extensiones:

class Set f where 
    exists :: f a -> (a -> Bool) -> Bool 

En este caso, la clase de tipo se extiende sobre los tipos de mayor kinded, que es un buen truco y duro para llegar a por su cuenta si usted nunca ha lo he visto antes!

Answer 2

Daniel Wagner ya dio una respuesta perfecta sobre lo que está tratando de hacer. Solo quiero agregar un punto acerca de su error: Too many parameters for class 'Set'. Esto significa que no habilitó la extensión GHC correspondiente - MultiParamTypeClasses. Puede hacerlo especificando tipo especial de comentario en la parte superior de su archivo de origen:

{-# LANGUAGE MultiParamTypeClasses #-} 
-- 
-- Your source code here 
-- 

, entonces debería ser capaz de compilar el código.

Otra característica de Haskell mencionada en la respuesta de Daniel también requiere habilitar cierta extensión, es decir, FunctionalDependencies (esta es la cosa extraña de .. | a -> b .. dentro de la declaración de clase de tipo). Puede habilitar múltiples extensiones al mismo tiempo utilizando una coma, así:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-} 

comentario de Carl menciona otra extensión, TypeFamilies, que también podría proporcionar un medio para lo que está tratando de hacer (clase genérica de tipos de conjuntos u otro tipo de colecciones). Puede leer sobre esto aquí: http://www.haskell.org/haskellwiki/Type_families.