haskell - potencia - ¿Cómo le doy una instancia de Functor a un tipo de datos creado para esquemas de recursión general?

funciones recursivas en haskell ejemplos

Question

Tengo un tipo de datos recursivo que tiene una instancia de Functor:

data Expr1 a
  = Val1 a
  | Add1 (Expr1 a) (Expr1 a)
  deriving (Eq, Show, Functor)

Ahora, estoy interesado en modificar este tipo de datos para admitir esquemas de recursión generales, tal como se describen en este tutorial y en este paquete de Hackage . Logré hacer funcionar el catamorfismo:

newtype Fix f = Fix {unFix :: f (Fix f)}

data ExprF a r
  = Val a
  | Add r r
  deriving (Eq, Show, Functor)

type Expr2 a = Fix (ExprF a)

cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix

eval :: Expr2 Int -> Int
eval = cata $ /case
  Val n -> n
  Add x y -> x + y

main :: IO ()
main =
  print $ eval
    (Fix (Add (Fix (Val 1)) (Fix (Val 2))))

Pero ahora no puedo encontrar la forma de darle a Expr2 la misma instancia de functor que tenía el Expr original. Parece que hay una falta de coincidencia cuando intentamos definir la instancia de functor:

instance Functor (Fix (ExprF a)) where
    fmap = undefined

Kind mis-match
    The first argument of `Functor'' should have kind `* -> *'',
    but `Fix (ExprF a)'' has kind `*''
    In the instance declaration for `Functor (Fix (ExprF a))''

¿Cómo escribo una instancia de Functor para Expr2 ?

Pensé en envolver Expr2 en un nuevo tipo con newtype Expr2 a = Expr2 (Fix (ExprF a)) pero luego este newtype necesita ser desenvuelto para pasarlo a cata , lo que no me gusta mucho. Tampoco sé si sería posible derivar automáticamente la instancia del functor Expr2 como lo hice con Expr1 .

Answer 1

El tipo de palabra clave se usa solo como un tipo existente, tal vez esto es lo que está buscando

newtype Expr2 a r = In { out :: (ExprF a r)} deriving Functor

Answer 2

Esta es una vieja herida para mí. El punto crucial es que su ExprF es funcional en ambos parámetros. Entonces si tuviéramos

class Bifunctor b where
  bimap :: (x1 -> y1) -> (x2 -> y2) -> b x1 x2 -> b y1 y2

entonces podrías definir (o imaginarte una máquina que defina para ti)

instance Bifunctor ExprF where
  bimap k1 k2 (Val a)    = Val (k1 a)
  bimap k1 k2 (Add x y)  = Add (k2 x) (k2 y)

y ahora puedes tener

newtype Fix2 b a = MkFix2 (b a (Fix2 b a))

acompañado por

map1cata2 :: Bifunctor b => (a -> a'') -> (b a'' t -> t) -> Fix2 b a -> t
map1cata2 e f (MkFix2 bar) = f (bimap e (map1cata2 e f) bar)

lo que a su vez te da que cuando tomas un punto fijo en uno de los parámetros, lo que queda es todavía funcional en el otro

instance Bifunctor b => Functor (Fix2 b) where
  fmap k = map1cata2 k MkFix2

y tu obtienes lo que querías Pero tu instancia de Bifunctor no se construirá por arte de magia. Y es un poco molesto que necesites un operador diferente de punto fijo y un nuevo tipo de functor. El problema es que ahora tiene dos tipos de subestructura: "valores" y "subexpresiones".

Y aquí está el turno. Hay una noción de functor que se cierra bajo puntos de fijación. Encienda el fregadero de la cocina (especialmente DataKinds ) y

type s :-> t = forall x. s x -> t x

class FunctorIx (f :: (i -> *) -> (o -> *)) where
  mapIx :: (s :-> t) -> f s :-> f t

Tenga en cuenta que los "elementos" vienen en un tipo indexado en i y "estructuras" en un tipo indexado sobre algún otro o . Tomamos i -funciones de conservación en elementos para o preservar funciones en estructuras. Fundamentalmente, i y i podemos ser diferentes.

Las palabras mágicas son "1, 2, 4, 8, ¡tiempo para potenciar!". Un tipo de tipo * puede convertirse fácilmente en un GADT de tipo trivialmente indexado () -> * . Y dos tipos se pueden juntar para hacer un GADT de tipo Either () () -> * . Eso significa que podemos unir ambos tipos de subestructuras. En general, tenemos un tipo de nivel de tipo either .

data Case :: (a -> *) -> (b -> *) -> Either a b -> * where
  CL :: f a -> Case f g (Left a)
  CR :: g b -> Case f g (Right b)

equipado con su noción de "mapa"

mapCase :: (f :-> f'') -> (g :-> g'') -> Case f g :-> Case f'' g''
mapCase ff gg (CL fx) = CL (ff fx)
mapCase ff gg (CR gx) = CR (gg gx)

Entonces podemos refuncionar nuestros bifactores como instancias de FunctorIx con FunctorIx .

Y ahora podemos tomar el punto fijo de cualquier estructura de nodo f que tenga lugares para elementos p o subnodos. Es el mismo trato que tuvimos anteriormente.

newtype FixIx (f :: (Either i o -> *) -> (o -> *))
              (p :: i -> *)
              (b :: o)
  = MkFixIx (f (Case p (FixIx f p)) b)

mapCata :: forall f p q t. FunctorIx f =>
  (p :-> q) -> (f (Case q t) :-> t) -> FixIx f p :-> t
mapCata e f (MkFixIx node) = f (mapIx (mapCase e (mapCata e f)) node)

Pero ahora, tenemos el hecho de que FunctorIx está cerrado bajo FixIx .

instance FunctorIx f => FunctorIx (FixIx f) where
  mapIx f = mapCata f MkFixIx

Los funtores en conjuntos indexados (con la libertad adicional de variar el índice) pueden ser muy precisos y muy potentes. Disfrutan de muchas más propiedades de cierre que Functor ''s do. No creo que se den cuenta.

Answer 3

Me pregunto si sería mejor usar el tipo Free :

data Free f a
  = Pure a
  | Wrap (f (Free f a))
deriving Functor

data ExprF r
  = Add r r
deriving Functor

Esto tiene el beneficio adicional de que hay bastantes bibliotecas que ya trabajan en mónadas gratuitas, por lo que tal vez le ahorren algo de trabajo.

Answer 4

No hay nada de malo en la respuesta del cerdo, pero tal vez puedas usar una más simple como un trampolín:

{-# LANGUAGE DeriveFunctor, ScopedTypeVariables #-}

import Prelude hiding (map)

newtype Fix f = Fix { unFix :: f (Fix f) }

-- This is the catamorphism function you hopefully know and love
-- already.  Generalizes ''foldr''.
cata :: Functor f => (f r -> r) -> Fix f -> r
cata phi = phi . fmap (cata phi) . unFix

-- The ''Bifunctor'' class.  You can find this in Hackage, so if you
-- want to use this just use it from there.
--
-- Minimal definition: either ''bimap'' or both ''first'' and ''second''.
class Bifunctor f where
    bimap :: (a -> c) -> (b -> d) -> f a b -> f c d
    bimap f g = first f . second g

    first :: (a -> c) -> f a b -> f c b
    first f = bimap f id

    second :: (b -> d) -> f a b -> f a d
    second g = bimap id g

-- The generic map function.  I wrote this out with
-- ScopedTypeVariables to make it easier to read...
map :: forall f a b. (Functor (f a), Bifunctor f) => 
       (a -> b) -> Fix (f a) -> Fix (f b)
map f = cata phi 
    where phi :: f a (Fix (f b)) -> Fix (f b)
          phi = Fix . first f

Ahora su lenguaje de expresiones funciona así:

-- This is the base (bi)functor for your expression type.
data ExprF a r = Val a 
               | Add r r
               deriving (Eq, Show, Functor)

instance Bifunctor ExprF where
    bimap f g (Val a) = Val (f a)
    bimap f g (Add l r) = Add (g l) (g r)

newtype Expr a = Expr (Fix (ExprF a))

instance Functor Expr where
    fmap f (Expr exprF) = Expr (map f exprF)

EDITAR: Aquí hay un enlace al paquete bifunctors en Hackage .