Introduccion
En Haskell, es habitual trabajar con efectos como functors cuyos objetos son algunas expresiones que nos interesan en este momento.
Cuando vemos el tipo de expresión
Quizás a , nos abstraemos de la existencia real de alguna
a , concentrando toda nuestra atención en esta
a . La misma historia con la
Lista a - valores plurales de
a ;
Estado sa -
a , dependiendo de algún estado actual;
Ea -
a , que puede devolver algún error
e .
Antes de continuar, el artículo usará varias definiciones:
type (:=) ta = ta
Por ejemplo:
Lista :
. Quizás: = a - esta expresión es fácil de imaginar, esta es una lista de valores cuya existencia está en duda.
Además, como ejemplo, utilizaremos cuatro tipos comunes:
Lector ,
Estado ,
Cualquiera de los dos ,
Quizás .
Composiciones y transformadores
La forma más obvia de aplicar más de un efecto a una expresión es simplemente incrustar uno en el otro, esta es la composición habitual de los functores. En las composiciones, los efectos no tienen efecto entre sí (a menos que se usen métodos
transitables sobre ellos). Y para combinar muchos efectos en uno, se utilizan transformadores. Cada método tiene sus ventajas y desventajas:
Composiciones
- No se necesitan tipos adicionales para construirlos
- No existe un método general para fusionar efectos con las clases Functor / Applicative / Monad
- Todo se compone maravillosamente hasta que se trata de mónadas
Transformadores:
- Te permite combinar varios efectos en uno
- Pero necesita un tipo separado (con mayor frecuencia algún tipo nuevo )
- Usando la elevación, puede realizar cálculos en cualquier capa de la pila de transformación.
- Pero no puede tener en cuenta los efectos por separado, aunque hay funciones especializadas
Los transformadores son diferentes de las composiciones de embrague (no sé cómo llamarlo de manera diferente). Con cierta composición, puede convertirlo en un transformador y viceversa. Los esquemas de atraque nos ayudarán con esto.
Esquemas de atraque
Si observamos más de cerca los tipos de transformadores de mónada, podemos identificar algunos patrones:
newtype ReaderT rma = ReaderT { runReaderT :: r -> ma } newtype MaybeT ma = MaybeT { runMaybeT :: m (Maybe a) } newtype ExceptT ema = ExceptT { runExceptT :: m (Either ea)) } newtype StateT sma = StateT { runStateT :: s -> m (a,s) }
Los transformadores describen un caso especial de cómo el efecto definido e indefinido actual debería combinarse.
Deje que
t sea definitivo y que sea indefinido, intente:
Reader: r -> ua ===> (->) r :. u := a ===> t :. u := a
Algunos efectos son bastante complejos y se pueden definir a través de la composición de otros efectos más simples:
State: s -> u (a, s) ===> (->) s :. (,) s := a ==> t :. u :. t' := a
Si echamos un vistazo más de cerca a los primeros 3 ejemplos, podemos notar patrones comunes: si en
Reader , un cierto efecto envuelve uno indefinido (lo pone entre paréntesis, se convierte en un objeto de un functor), entonces con
Either y
Maybe es lo contrario: un efecto indefinido envuelve uno específico. En el caso de
State, incluso colocamos el functor entre dos efectos definidos más simples.
Intentemos expresar estos patrones en tipos:
newtype TU tua = TU (t :. u := a) newtype UT tua = UT (u :. t := a) newtype TUT tut' a = TUT (t :. u :. t' := a)
Acabamos de definir esquemas de acoplamiento: esta es una composición de functores en un contenedor que indica la posición de un efecto específico e indefinido.
De hecho, los métodos para transformadores cuyos nombres comienzan con
run simplemente eliminan la envoltura del transformador, devolviendo la composición de los functores. Describimos tal clase de tipos:
class Composition t where type Primary ta :: * run :: ta -> Primary ta
Ahora tenemos una forma universal de ejecutar estos circuitos:
instance Composition (TU tu) where type Primary (TU tu) a = t :. u := a run (TU x) = x instance Composition (UT tu) where type Primary (UT tu) a = u :. t := a run (UT x) = x instance Composition (TUT tu t') where type Primary (TUT tu t') a = t :. u :. t' := a run (TUT x) = x
¿Qué pasa con los transformadores? Aquí también necesitará una clase de tipo en la que se prescriba un esquema de acoplamiento para un tipo particular, se declara que el método de
inserción eleva el efecto indefinido al nivel del transformador y
construye para construir un cierto efecto en un transformador:
class Composition t => Transformer t where type Schema (t :: * -> *) (u :: * -> *) = (r :: * -> *) | r -> tu embed :: Functor u => u ~> Schema tu build :: Applicative u => t ~> Schema tu type (:>) tua = Transformer t => Schema tua
Ahora queda por declarar las instancias, comience con
Maybe y
Either :
instance Transformer Maybe where type Schema Maybe u = UT Maybe u embed x = UT $ Just <$> x build x = UT . pure $ x instance Transformer (Either e) where type Schema (Either e) u = UT (Either e) u embed x = UT $ Right <$> x build x = UT . pure $ x
Crearemos nuestro propio tipo para
Reader , ya que no está en la
base . Y también necesita una instancia de la clase
Composición , ya que es un contenedor para el functor de flecha:
newtype Reader ea = Reader (e -> a) instance Composition (Reader e) where type Primary (Reader e) a = (->) ea run (Reader x) = x instance Transformer (Reader e) where type Schema (Reader e) u = TU ((->) e) u embed x = TU . const $ x build x = TU $ pure <$> run x
Haz algo similar con el
Estado :
newtype State sa = State ((->) s :. (,) s := a) instance Composition (State s) where type Primary (State s) a = (->) s :. (,) s := a run (State x) = x instance Transformer (State s) where type Schema (State s) u = TUT ((->) s) u ((,) s) embed x = TUT $ \s -> (s,) <$> x build x = TUT $ pure <$> run x
Como un ejemplo
Queda por probar esto en los problemas del mundo real: como ejemplo, escribiremos un programa que calcule la colocación correcta de varios tipos de paréntesis.
Definir tipos para paréntesis: pueden estar abriendo y cerrando; y también tienen diferentes estilos:
data Shape = Opened | Closed data Style = Round | Square | Angle | Curly
Otros símbolos de nuestro programa no son interesantes:
data Symbol = Nevermind | Bracket Style Shape
También definimos una lista de errores que nuestro programa puede encontrar:
data Stumble = Deadend (Int, Style)
¿Qué efectos necesita nuestro programa? Necesitamos mantener una lista de paréntesis en espera de verificación y debemos detenernos en el primer error encontrado. Hacemos un transformador:
State [(Int, Style)] :> Either Stumble := ()
El algoritmo es simple: pasamos por la estructura con corchetes indexados, si después del pasaje no encontramos un error y todavía tenemos los corchetes en el estado, entonces el corchete abierto no tiene uno cerrado:
checking :: Traversable t => t (Int, Symbol) -> Either Stumble () checking struct = run (traverse proceed struct) [] >>= \case (s : _, _) -> Left . Logjam $ s where ([], _) -> Right ()
Recordamos cualquier paréntesis abierto, compare cualquier cerrado con el último abierto recordado:
proceed :: (Int, Symbol) -> State [(Int, Style)] :> Either Stumble := () proceed (_, Nevermind) = pure () proceed (n, Bracket style Opened) = build . modify . (:) $ (n, style) procceed (n, Bracket closed Closed) = build get >>= \case []-> embed $ Left . Deadend $ (n, closed) ((m, opened) : ss) -> if closed /= opened then embed . Left $ Mismatch (m, opened) (n, closed) else build $ put ss where
Conclusión
Usando esquemas de acoplamiento, teniendo alguna composición de functores, podemos convertirlos en transfómeros y viceversa. Desafortunadamente, tal truco no funcionará con la madre de las mónadas: secuelas. Y todo porque no pueden ser imaginados como una composición de functores, sino que es posible como una composición de profunctores ... Y, sin embargo, esta es una historia completamente diferente.
Código de la biblioteca en Github |
Documentación de piratería |
Ejemplo de paréntesis