haskell - online - Prueba si un valor coincide con un constructor

haskell pdf

Question

Supongamos que tengo un tipo de datos como ese:

data NumCol = Empty |
              Single Int |
              Pair Int Int |
              Lots [Int]

Ahora deseo filtrar los elementos que coinciden con un constructor determinado de un [NumCol] . Puedo escribirlo para, digamos, Pair :

get_pairs :: [NumCol] -> [NumCol]
get_pairs = filter is_pair
    where is_pair (Pair _ _) = True
          is_pair _ = False

Esto funciona, pero no es genérico. Tengo que escribir una función separada para is_single , is_lots , etc.

Ojalá pudiera escribir:

get_pairs = filter (== Pair)

Pero esto solo funciona para constructores de tipos que no toman argumentos (es decir, Empty ).

Entonces la pregunta es, ¿cómo puedo escribir una función que tome un valor y un constructor, y devuelva si el valor coincide con el constructor?

Answer 1

Al menos get_pairs se puede definir de forma relativamente simple utilizando una lista de comprensión para filtrar:

get_pairs xs = [x | x@Pair {} <- xs]

Para una solución más general de constructores coincidentes, puede usar prismas del paquete de lens :

{-# LANGUAGE TemplateHaskell #-}

import Control.Lens
import Control.Lens.Extras (is)

data NumCol = Empty |
              Single Int |
              Pair Int Int |
              Lots [Int]

-- Uses Template Haskell to create the Prisms _Empty, _Single, _Pair and _Lots
-- corresponding to your constructors
makePrisms ''''NumCol

get_pairs :: [NumCol] -> [NumCol]
get_pairs = filter (is _Pair)

Answer 2

Las etiquetas de las uniones etiquetadas deben ser valores de primera clase, y con un poco de esfuerzo, lo son.

Alerta Jiggery-Pokery:

{-# LANGUAGE GADTs, DataKinds, KindSignatures,
    TypeFamilies, PolyKinds, FlexibleInstances,
    PatternSynonyms
#-}

Paso uno: defina versiones de tipo de nivel de las etiquetas.

data TagType = EmptyTag | SingleTag | PairTag | LotsTag

Paso dos: defina los testigos de nivel de valor para la representabilidad de las etiquetas de nivel de tipo. La biblioteca Singletons de Richard Eisenberg hará esto por usted. Quiero decir algo como esto:

data Tag :: TagType -> * where
  EmptyT   :: Tag EmptyTag
  SingleT  :: Tag SingleTag
  PairT    :: Tag PairTag
  LotsT    :: Tag LotsTag

Y ahora podemos decir qué cosas esperamos encontrar asociadas con una etiqueta determinada.

type family Stuff (t :: TagType) :: * where
  Stuff EmptyTag   = ()
  Stuff SingleTag  = Int
  Stuff PairTag    = (Int, Int)
  Stuff LotsTag    = [Int]

Para que podamos refactorizar el tipo que primero pensaste

data NumCol :: * where
  (:&) :: Tag t -> Stuff t -> NumCol

y use PatternSynonyms para recuperar el comportamiento que tenía en mente:

pattern Empty        = EmptyT   :&  ()
pattern Single  i    = SingleT  :&  i
pattern Pair    i j  = PairT    :&  (i, j)
pattern Lots    is   = LotsT    :&  is

Entonces, lo que sucede es que cada constructor de NumCol ha convertido en una etiqueta indexada por el tipo de etiqueta para la que está. Es decir, las etiquetas de constructor ahora viven separadas del resto de los datos, sincronizadas por un índice común que asegura que las cosas asociadas con una etiqueta coincidan con la etiqueta misma.

Pero podemos hablar de etiquetas solo.

data Ex :: (k -> *) -> * where  -- wish I could say newtype here
  Witness :: p x -> Ex p

Ahora, Ex Tag , es el tipo de "etiquetas de tiempo de ejecución con una contraparte de nivel de tipo". Tiene una instancia Eq

instance Eq (Ex Tag) where
  Witness EmptyT   ==  Witness EmptyT   = True
  Witness SingleT  ==  Witness SingleT  = True
  Witness PairT    ==  Witness PairT    = True
  Witness LotsT    ==  Witness LotsT    = True
  _                ==  _                = False

Además, podemos extraer fácilmente la etiqueta de un NumCol .

numColTag :: NumCol -> Ex Tag
numColTag (n :& _) = Witness n

Y eso nos permite hacer coincidir sus especificaciones.

filter ((Witness PairT ==) . numColTag) :: [NumCol] -> [NumCol]

Lo que plantea la pregunta de si su especificación es realmente lo que necesita. El punto es que la detección de una etiqueta le da derecho a una expectativa de las cosas de esa etiqueta. El tipo de salida [NumCol] no hace justicia al hecho de que sabe que tiene solo los pares.

¿Cómo podría ajustar el tipo de su función y seguir entregándola?

Answer 3

Un enfoque es usar DataTypeable y el módulo Data.Data . Este enfoque se basa en dos instancias de clase de autogenerado que transportan metadatos sobre el tipo para usted: Typeable y Data . Puede derivarlos con {-# LANGUAGE DeriveDataTypeable #-} :

data NumCol = Empty |
          Single Int |
          Pair Int Int |
          Lots [Int] deriving (Typeable, Data)

Ahora tenemos una función toConstr que, dado un valor, nos da una representación de su constructor:

toConstr :: Data a => a -> Constr

Esto hace que sea fácil comparar dos términos solo por sus constructores. ¡El único problema restante es que necesitamos un valor para comparar cuando definimos nuestro predicado! Siempre podemos simplemente crear un valor ficticio con undefined , pero eso es un poco feo:

is_pair x = toConstr x == toConstr (Pair undefined undefined)

Entonces, lo último que haremos será definir una pequeña clase práctica que automatice esto. La idea básica es llamar toConstr en valores sin función y recurse en cualquier función pasando primero undefined .

class Constrable a where
  constr :: a -> Constr

instance Data a => Constrable a where
  constr = toConstr

instance Constrable a => Constrable (b -> a) where
  constr f = constr (f undefined)

Esto depende de FlexibleInstance , OverlappingInstances y UndecidableInstances , por lo que podría ser un poco malvado, pero, utilizando el (in) famoso teorema del globo ocular, debería estar bien. A menos que agregue más instancias o intente usarlo con algo que no sea un constructor. Entonces podría explotar. Violentamente. Sin promesas.

Finalmente, con el mal contenido, podemos escribir un operador de "igual por constructor":

(=|=) :: (Data a, Constrable b) => a -> b -> Bool
e =|= c = toConstr e == constr c

(El operador =|= es un poco nemotécnico, porque los constructores se definen sintácticamente con a | .)

¡Ahora puede escribir casi exactamente lo que quería!

filter (=|= Pair)

Además, tal vez quieras desactivar la restricción de monomorfismo. De hecho, aquí está la lista de extensiones que habilité que puedes usar:

{-# LANGUAGE DeriveDataTypeable, FlexibleInstances, NoMonomorphismRestriction, OverlappingInstances, UndecidableInstances #-}

Sí, es mucho. Pero eso es lo que estoy dispuesto a sacrificar por la causa. De no escribir s undefined adicional.

Honestamente, si no te importa confiar en la lens (pero chico, esa dependencia es una tontería), debes seguir el enfoque prismático. Lo único que Data.Data.Data recomendar es que puedes usar la clase de datos Data.Data.Data .