tipos - Haskell-función simple de comparación de constructores(?)

string en haskell

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 sencilla de verificar si dos valores del tipo PhpValue son del mismo constructor ( PhpValue si estoy confundido con la terminología aquí, pero básicamente lo que quiero comprobar es si ambos están , por ejemplo, son IntValue , sin preocuparse por el valor particular).

Aquí hay una función que escribí para eso:

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

Esto funciona como debería, pero realmente no me gusta: si agrego más constructores (como FloatValue Float ), tendré que volver a escribir la función, y aumentará de tamaño a medida que mi definición de datos crezca.

La pregunta: ¿Existe una forma de escribir una función de este tipo, para que su implementación no cambie cuando agrego más constructores?

Para el registro: no quiero cambiar la definición de los data , tengo suficientes mónadas en el resto de mi código tal como está;)

Answer 1

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 paquete simple para esto ya que no estaba completamente satisfecho con las soluciones existentes.

Primero, 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á instancias automáticamente para nosotros.

El default es una firma predeterminada , y significa que cuando el tipo es una instancia de Data , podemos omitir la definición de eqConstr y recurrir a la implementació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 sea exactamente lo que escribiríamos a mano. Eche un vistazo al núcleo 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
}
} 

En contraste, el uso de Data introduce una gran cantidad de direccionamiento adicional al volver a verificar un Constr explícito para cada argumento antes de compararlos por 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 un montón de otros fanáticos involucrados en la computación toConstr que no vale la pena mostrar)

En la práctica, esto lleva a que la implementación de la plantilla Haskell sea el doble de 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 2

Eche un vistazo a Data.Data y su función Data.Data . Esto devuelve una representación del constructor que se puede comparar para la igualdad.

Con una extensión (puede colocar {-# LANGUAGE DeriveDataTypeable #-} en la parte superior de su módulo), puede obtener una instancia de Data derivada automáticamente:

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

Entonces deberías poder usar la función toConstr para comparar por constructor.

Ahora lo siguiente será cierto:

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

Usando desde Data.Function ahora puede reescribir sameConstructor para:

sameConstructor = (==) `on` toConstr

Esto es lo mismo que

sameConstructor l r = toConstr l == toConstr r

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

Answer 3

En tu caso especial puedes usar el Show magic del compilador:

data PhpValue = VoidValue | IntValue Integer | BoolValue Bool deriving Show
sameConstructor v1 v2 = cs v1 == cs v2 where
cs = takeWhile (/= '' '') . show

Por supuesto, dependiendo de la cadena de caracteres generada por el compilador está muy cerca de un hack ...

Answer 4

Esto se conoce como el problema de expresión en los lenguajes de Haskell y ML-family; hay una serie de soluciones insatisfactorias (incluyendo el uso de Data.Typeable y el uso Data.Typeable clases de tipos, en Haskell) pero no hay soluciones agradables.

Answer 5

Si no desea utilizar ninguna de las formas razonables en las otras respuestas, puede utilizar una forma totalmente no admitida que se garantiza que sea rápida pero que no garantice realmente dar resultados correctos o incluso no bloquearse. Tenga en cuenta que esto incluso le complacerá intentar 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 (posiblemente) es que esto se compara con los nuevos tipos. Así que si tienes

newtype Foo a = Foo (Maybe a)

entonces

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

a pesar de que están construidos con el constructor Foo . Puede GHC.Generics 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 muy 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 asociados con la representación genérica del tipo para determinar si es un tipo nuevo. Si es así, reportamos su "etiqueta" como 0 ; De lo contrario usamos su etiqueta real.

Answer 6

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

{-# 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