Haskell novato en los tipos

Question

Soy completamente nuevo para Haskell (y más generalmente para la programación funcional), así que perdóneme si esto es realmente algo básico. Para obtener más que un gusto, trato de implementar en Haskell algunas cosas algorítmicas en las que estoy trabajando. Tengo un módulo simple Interval que implementa intervalos en la línea. Contiene el tipo

data Interval t = Interval t t 

la función auxiliar

makeInterval :: (Ord t) => t -> t -> Interval t 
makeInterval l r | l <= r = Interval l r 
        | otherwise = error "bad interval" 

y algunas funciones de utilidad sobre los intervalos.

Aquí, mi interés radica en los intervalos multidimensionales (intervalos d), aquellos objetos que se componen de d intervalos. Quiero considerar por separado los intervalos d que son la unión de d intervalos separados en la línea (intervalo múltiple) de aquellos que son la unión del intervalo d en d líneas separadas (intervalo de seguimiento). Con los tratamientos algorítmicos distintas en mente, creo que sería bueno tener dos tipos distintos (incluso si ambos son listas de intervalos aquí) como

import qualified Interval as I 

-- Multilple interval 
newtype MInterval t = MInterval [I.Interval t] 

    -- Track interval 
newtype TInterval t = TInterval [I.Interval t]  

para permitir comprobaciones de validez distintas, por ejemplo,

makeMInterval :: (Ord t) => [I.Interval t] -> MInterval t 
makeMInterval is = if foldr (&&) True [I.precedes i i' | (i, i') <- zip is (tail is)] 
        then (MInterval is) 
        else error "bad multiple interval" 


makeTInterval :: (Ord t) => [I.Interval t] -> TInterval t 
makeTInterval = TInterval 

¡Ahora llego al punto, por fin! Pero algunas funciones están naturalmente relacionadas con intervalos múltiples e intervalos de seguimiento. Por ejemplo, una función order devolvería el número de intervalos en un intervalo múltiple o un intervalo de seguimiento. ¿Que puedo hacer? Añadiendo

-- Dimensional interval 
data DInterval t = MIntervalStuff (MInterval t) | TIntervalStuff (TInterval t) 

no ayuda mucho, ya que, si entiendo bien (corríjanme si me equivoco), que tendría que escribir

order :: DInterval t -> Int 
order (MIntervalStuff (MInterval is)) = length is 
order (TIntervalStuff (TInterval is)) = length is 

y llame order como order (MIntervalStuff is) o order (TIntervalStuff is) cuando is es un MInterval o un TInterval. No es tan bueno, parece extraño. Tampoco quiero duplicar la función (tengo muchas funciones relacionadas con los intextuales múltiples y de seguimiento, y algunas otras definiciones de intervalo d, como la longitud igual múltiple y los intervalos de seguimiento).

Me da la sensación de que estoy completamente equivocado y me he perdido un punto importante acerca de los tipos en Haskell (y/o no puedo olvidarme lo suficiente sobre la programación de OO). Entonces, una pregunta bastante nueva, ¿cuál sería la mejor manera en Haskell para manejar una situación así? ¿Tengo que olvidarme de introducir MInterval y TInterval e ir solo con un tipo?

Gracias mucho por su ayuda,

Garulfo

Answer 1

consideran el uso de clases de tipos para mostrar similitudes entre diferentes tipos. Consulte el tutorial de Haskell [1] sobre clases y sobrecarga para obtener ayuda.

[1]: http://www.haskell.org/tutorial/classes.html Haskell tutorial

Answer 2

lo que quiere son tipos con la misma estructura y operaciones comunes, pero que pueden ser distinguidos, y para el cual determinadas operaciones sólo tienen sentido en uno u otro tipo. El modismo para esto en Haskell es Phantom Types.

1. http://www.haskell.org/haskellwiki/Phantom_type
2. http://www.haskell.org/haskellwiki/Wrapper_types
3. http://blog.malde.org/index.php/2009/05/14/using-a-phantom-type-to-label-different-kinds-of-sequences/
4. http://neilmitchell.blogspot.com/2007/04/phantom-types-for-real-problems.html

Answer 3

Editar: esta es la misma idea que la respuesta de SCLV; sus enlaces proporcionan más información sobre esta técnica.

¿Qué tal este enfoque?

data MInterval = MInterval --multiple interval 
data TInterval = TInterval --track interval 

data DInterval s t = DInterval [I.Interval t] 

makeMInterval :: (Ord t) => [I.Interval t] -> Maybe (DInterval MInterval t) 
makeMInterval is = if foldr (&&) True [I.precedes i i' | (i, i') <- zip is (tail is)] 
    then Just (DInterval is) 
    else Nothing 

order :: DInterval s t -> Int 
order (DInterval is) = length is 

equalOrder :: DInterval s1 t -> DInterval s2 t -> Bool 
equalOrder i1 i2 = order i1 == order i2 

addToMInterval :: DInterval MInterval t -> Interval t -> Maybe (DInterval MInterval t) 
addToMInterval = .. 

Aquí el tipo DInterval representa intervalos multidimensionales, pero se necesita un parámetro de tipo adicional como un tipo fantasma. Esta información de tipo adicional permite que el contador de tipos diferencie entre diferentes tipos de intervalos, aunque tengan exactamente la misma representación.

Obtiene el tipo de seguridad de su diseño original, pero todas sus estructuras comparten la misma implementación. Fundamentalmente, cuando el tipo de intervalo no importa, puede dejarlo sin especificar.

También cambié la implementación de su función makeMInterval; devolver un Maybe para una función como esta es mucho más idiomático que el error de llamada.

Más explicación sobre lo mejor:

Vamos a examinar su función makeInterval. Se supone que esta función toma una lista de Intervalos, y si cumplen con los criterios, devuelve un intervalo múltiple, de lo contrario un intervalo de seguimiento. Esta explicación lleva al tipo:

makeInterval :: (Ord t) => 
    [I.Interval t] -> 
    Either (DInterval TInterval t) (DInterval MInterval t) 

Ahora que tenemos el tipo, ¿cómo podemos implementarlo? Nos gustaría volver a utilizar nuestra función makeMInterval.

makeInterval is = maybe 
        (Left $ DInterval TInterval is) 
        Right 
        (makeMInterval is) 

La función maybe tiene tres argumentos: un defecto b utilizar si el Tal es Nothing, una función de si el a -> b Tal es Just a, y una Maybe a. Devuelve el valor predeterminado o el resultado de aplicar la función al valor Maybe.

Nuestro valor predeterminado es el intervalo de seguimiento, por lo que creamos un intervalo de seguimiento de la izquierda para el primer argumento. Si tal vez es Just (DInterval MInterval t), el intervalo múltiple ya existe, así que todo lo que es necesario es pegarlo en el lado derecho de cualquiera. Finalmente, makeMInterval se usa para crear el intervalo múltiple.

Answer 4

Lo que quiere es una clase de tipo. Las clases de tipo es como se hace la sobrecarga en Haskell. Una clase de tipo es una estructura común que comparten muchos tipos. En el caso de que quiera crear una clase de todos los tipos que tienen una función order:

class Dimensional a where 
    order :: a -> Int 

Esto es decir que hay una clase de tipos a llamados Dimensional, y para cada tipo perteneciente a esta clase hay una función a -> Int llamada order.Ahora necesita declarar todos sus tipos como pertenecientes a la clase:

instance Dimensional MInterval where 
    order (MInterval is) = length is 

y así sucesivamente. También se pueden declarar funciones que actúan sobre las cosas que son de una clase dada, de esta manera:

isOneDimensional :: (Dimensional a) => a -> Bool 
isOneDimensional interval = (order interval == 1) 

La declaración de tipo se puede leer "para todos los tipos a que pertenecen a la clase de tipos Dimensional, estas funciones se lleva a a y devuelve una Bool ".

Me gusta pensar en las clases como estructuras algebraicas en las matemáticas (no es lo mismo que no se pueden aplicar algunas limitaciones lógicas, pero ...): indica cuáles son los requisitos para que un tipo pertenezca a alguna clase (en la analogía, las operaciones deben definirse sobre un conjunto para que pertenezca a una determinada construcción algebraica), y luego, para cada tipo específico, usted declara cuál es la implementación específica de las funciones requeridas (en la analogía, qué son las funciones específicas para cada conjunto específico).

Tome, por ejemplo, un grupo. Los grupos deben tener una identidad, una inversa para cada elemento y una multiplicación:

class Group a where: 
     identity :: a 
     inverse :: a -> a 
     (<*>)  :: a -> a -> a 

y enteros forman un grupo bajo la adición:

instance Group Integer where: 
     identity = 0 
     inverse x = (- x) 
     x <*> y  = x + y 

Tenga en cuenta que esto no va a resolver la repetición, ya que tienes que instanciar cada tipo.