Haskell - Comparativa constructor sencilla función

Question

En mi proyecto he creado un tipo de datos, que puede contener uno de los pocos tipos de valores (?):

data PhpValue = VoidValue | IntValue Integer | BoolValue Bool 

lo que quería hacer ahora, es tener una forma simple de verificar si dos valores del tipo PhpValue son del mismo constructor (corríjame si me confunden con la terminología aquí, pero básicamente lo que quiero verificar si ambos son, por ejemplo, son IntValue, sin preocuparme por el valor particular).

Aquí es una función que escribí para que:

sameConstructor :: PhpValue -> PhpValue -> Bool 
sameConstructor VoidValue VoidValue = True 
sameConstructor (IntValue _) (IntValue _) = True 
sameConstructor (BoolValue _) (BoolValue _) = True 
sameConstructor _ _ = False 

Esto funciona como debería, pero no me gusta mucho: si agrego más constructores (como FloatValue Float) Voy a tener que reescribe la función, y se hará más grande a medida que mi definición de datos se haga más grande.

La pregunta: ¿Hay alguna manera de escribir esa función, para que su implementación no cambie cuando agregue más constructores?

Para el registro: no quiero cambiar la definición data, tengo suficiente Mónadas en el resto de mi código tal como es;)

Answer 1

Tome un vistazo a Data.Data y su función toConstr. Esto devuelve una representación del constructor que se puede comparar por igualdad.

Con una extensión (se puede poner {-# LANGUAGE DeriveDataTypeable #-} en la parte superior de su módulo), puede tener una instancia Data derivada de forma automática:

data PhpValue = VoidValue | IntValue Integer | BoolValue Bool 
       deriving (Typeable, Data) 

A continuación, debería ser capaz de utilizar la función toConstr para comparar por constructor.

Ahora, el siguiente será cierto:

toConstr (BoolValue True) == toConstr (BoolValue False) 

Usando on de Data.Function ahora se puede reescribir sameConstructor a:

sameConstructor = (==) `on` toConstr 

Esto es lo mismo que

sameConstructor l r = toConstr l == toConstr r 

pienso la versión que usa on es más fácil de leer de un vistazo.

Answer 2

Esto se conoce como expression problem en Haskell y en los idiomas de la familia ML; hay una serie de soluciones insatisfactorias (incluido el uso de Data.Typeable y abusos de clases de tipos, en Haskell), pero no hay soluciones agradables.

Answer 3

En su caso especial que puede utilizar el Show magia del compilador:

data PhpValue = VoidValue | IntValue Integer | BoolValue Bool deriving Show 

sameConstructor v1 v2 = cs v1 == cs v2 where 
    cs = takeWhile (/= ' ') . show 

Por supuesto, en función de la representación de cadena generada por el compilador está muy cerca de un hack ...

Answer 4

Dado que la definición sigue un formato regular, puede usar Template Haskell para derivar automáticamente dicha función para cualquier tipo de datos. Seguí adelante y escribí un simple package para esto ya que no estaba completamente satisfecho con las soluciones existentes.

En primer lugar, definimos una clase

class EqC a where 
    eqConstr :: a -> a -> Bool 
    default eqConstr :: Data a => a -> a -> Bool 
    eqConstr = (==) `on` toConstr 

y luego una función deriveEqC :: Name -> DecsQ que generará automáticamente instancias para nosotros.

El default es una default signature, y significa que cuando el tipo es un ejemplo de Data podemos omitir la definición de eqConstr, y caer de nuevo a la aplicación de Tikhon.

El beneficio de Template Haskell es que produce una función más eficiente. Podemos escribir $(deriveEqC ''PhpValue) y obtener una instancia que es exactamente lo que escribiríamos a mano. Echar un vistazo a la core generado:

$fEqCPhpValue_$ceqConstr = 
    \ ds ds1 -> 
    case ds of _ { 
     VoidValue -> 
     case ds1 of _ { 
      __DEFAULT -> False; 
      VoidValue -> True 
     }; 
     IntValue ds2 -> 
     case ds1 of _ { 
      __DEFAULT -> False; 
      IntValue ds3 -> True 
     }; 
     BoolValue ds2 -> 
     case ds1 of _ { 
      __DEFAULT -> False; 
      BoolValue ds3 -> True 
     } 
    } 

Por el contrario, el uso de Data introduce una gran cantidad de indirección adicional reificando una explícita Constr para cada argumento antes de compararlos por la igualdad:

eqConstrDefault = 
    \ @ a $dData eta eta1 -> 
    let { 
     f 
     f = toConstr $dData } in 
    case f eta of _ { Constr ds ds1 ds2 ds3 ds4 -> 
    case f eta1 of _ { Constr ds5 ds6 ds7 ds8 ds9 -> 
    $fEqConstr_$c==1 ds ds5 
    } 
    } 

(Hay muchos otros problemas relacionados con el cálculo de toConstr que no vale la pena mostrar)

En la práctica, esto lleva a que la implementación de Template Haskell sea aproximadamente dos veces más rápida:

benchmarking EqC/TH 
time     6.906 ns (6.896 ns .. 6.915 ns) 
        1.000 R² (1.000 R² .. 1.000 R²) 
mean     6.903 ns (6.891 ns .. 6.919 ns) 
std dev    45.20 ps (32.80 ps .. 63.00 ps) 

benchmarking EqC/Data 
time     14.80 ns (14.77 ns .. 14.82 ns) 
        1.000 R² (1.000 R² .. 1.000 R²) 
mean     14.79 ns (14.77 ns .. 14.81 ns) 
std dev    60.17 ps (43.12 ps .. 93.73 ps) 

Answer 5

Una alternativa popular a Data es Generic. Creo que Data tiene más sentido en este contexto, pero pensé que tendría sentido agregar esto solo para completarlo.

{-# LANGUAGE DefaultSignatures, TypeOperators, FlexibleContexts #-} 
module SameConstr where 

import GHC.Generics 
import Data.Function (on) 

class EqC a where 
    eqConstr :: a -> a -> Bool 
    default eqConstr :: (Generic a, GEqC (Rep a)) => a -> a -> Bool 
    eqConstr = geqConstr `on` from 

class GEqC f where 
    geqConstr :: f p -> f p -> Bool 
    {-# INLINE geqConstr #-} 
    geqConstr _ _ = True 

instance GEqC f => GEqC (M1 i c f) where 
    {-# INLINE geqConstr #-} 
    geqConstr (M1 x) (M1 y) = geqConstr x y 

instance GEqC (K1 i c) 
instance GEqC (f :*: g) 
instance GEqC U1 
instance GEqC V1 

instance (GEqC f, GEqC g) => GEqC (f :+: g) where 
    {-# INLINE geqConstr #-} 
    geqConstr (L1 x) (L1 y) = geqConstr x y 
    geqConstr (R1 x) (R1 y) = geqConstr x y 
    geqConstr _ _ = False 

Answer 6

Si no desea utilizar cualquiera de las formas razonables de las otras respuestas, se puede utilizar de una manera completamente no compatible que se garantiza que sea rápido, pero en realidad no garantiza para dar resultados correctos o incluso no choque. Tenga en cuenta que incluso será un placer tratar de comparar funciones, por lo que dará resultados totalmente falsos.

{-# language MagicHash, BangPatterns #-} 

module DangerZone where 

import GHC.Exts (Int (..), dataToTag#) 
import Data.Function (on) 

{-# INLINE getTag #-} 
getTag :: a -> Int 
getTag !a = I# (dataToTag a) 

sameConstr :: a -> a -> Bool 
sameConstr = (==) `on` getTag 

Otro problema (podría decirse) es que esto se asemeja a los nuevos tipos. Así que si usted tiene

newtype Foo a = Foo (Maybe a) 

continuación

sameConstr (Foo (Just 3)) (Foo Nothing) == False 

pesar de que están construidas con la Foo constructor. Puede solucionar esto utilizando un poco de la maquinaria en GHC.Generics, pero sin el costo de tiempo de ejecución asociado con el uso de genéricos no optimizados. ¡Esto se pone bastante peludo!

{-# language MagicHash, BangPatterns, TypeFamilies, DataKinds, 
      ScopedTypeVariables, DefaultSignatures #-} 

import Data.Proxy (Proxy (..)) 
import GHC.Generics 
import Data.Function (on) 
import GHC.Exts (Int (..), dataToTag#) 

--Define getTag as above 

class EqC a where 
    eqConstr :: a -> a -> Bool 
    default eqConstr :: forall i q r s nt f. 
         (Generic a 
         , Rep a ~ M1 i ('MetaData q r s nt) f 
         , GNT nt) 
        => a -> a -> Bool 
    eqConstr = genEqConstr 

-- This is separated out to work around a bug in GHC 8.0 
genEqConstr :: forall a i q r s nt f. 
         (Generic a 
         , Rep a ~ M1 i ('MetaData q r s nt) f 
         , GNT nt) 
        => a -> a -> Bool 
genEqConstr = (==) `on` modGetTag (Proxy :: Proxy nt) 

class GNT (x :: Bool) where 
    modGetTag :: proxy x -> a -> Int 

instance GNT 'True where 
    modGetTag _ _ = 0 

instance GNT 'False where 
    modGetTag _ a = getTag a 

La idea clave aquí es que nos fijamos en los metadatos de nivel de tipo asociado con la representación genérica de la línea para determinar si es o no es un newtype. Si es así, informamos su "etiqueta" como 0; de lo contrario, usamos su etiqueta actual.