¿Qué son las flechas y cómo puedo usarlas?

Question

Traté de aprender el significado de flechas, pero no las entendí.

Utilicé el tutorial de Wikilibros. Creo que el problema de Wikilibro es principalmente que parece estar escrito para alguien que ya entiende el tema.

¿Alguien puede explicar qué son las flechas y cómo puedo usarlas?

Answer 1

No conozco ningún tutorial, pero creo que es más fácil comprender las flechas si miras algunos ejemplos concretos. El mayor problema que tuve al aprender a usar las flechas fue que ninguno de los tutoriales o ejemplos realmente muestran cómo usar las flechas, solo cómo componerlas. Entonces, con eso en mente, aquí está mi mini-tutorial. Examinaré dos flechas diferentes: funciones y una flecha definida por el usuario tipo MyArr.

-- type representing a computation 
data MyArr b c = MyArr (b -> (c,MyArr b c)) 

1) Una flecha es un cálculo desde la entrada de un tipo especificado a la salida de un tipo especificado. La clase de letra de flecha toma tres argumentos de tipo: el tipo de flecha, el tipo de entrada y el tipo de salida. En cuanto a la cabeza de instancia para casos de flecha encontramos:

instance Arrow (->) b c where 
instance Arrow MyArr b c where 

La Flecha (ya sea (->) o MyArr) es una abstracción de un cálculo. Para obtener una función b -> c, b es la entrada y c es la salida.
Para un MyArr b c, b es la entrada y c es la salida.

2) Para ejecutar realmente un cálculo de flecha, utiliza una función específica para su tipo de flecha. Para las funciones, simplemente aplica la función a un argumento. Para otras flechas, debe haber una función separada (como runIdentity, runState, etc. para mónadas).

-- run a function arrow 
runF :: (b -> c) -> b -> c 
runF = id 

-- run a MyArr arrow, discarding the remaining computation 
runMyArr :: MyArr b c -> b -> c 
runMyArr (MyArr step) = fst . step 

3) Las flechas se utilizan con frecuencia para procesar una lista de entradas. Para las funciones, estas pueden realizarse en paralelo, pero para algunas flechas, la salida en cualquier paso dado depende de las entradas previas (p.mantener un total acumulado de entradas).

-- run a function arrow over multiple inputs 
runFList :: (b -> c) -> [b] -> [c] 
runFList f = map f 

-- run a MyArr over multiple inputs. 
-- Each step of the computation gives the next step to use 
runMyArrList :: MyArr b c -> [b] -> [c] 
runMyArrList _ [] = [] 
runMyArrList (MyArr step) (b:bs) = let (this, step') = step b 
            in this : runMyArrList step' bs 

Este es un motivo por el que las flechas son útiles. Proporcionan un modelo de cálculo que puede hacer uso implícito del estado sin exponer nunca ese estado al programador. El programador puede usar cómputos con flechas y combinarlos para crear sistemas sofisticados.

Aquí hay una myArr que lleva la cuenta del número de entradas que ha recibido:

-- count the number of inputs received: 
count :: MyArr b Int 
count = count' 0 
    where 
    count' n = MyArr (\_ -> (n+1, count' (n+1))) 

Ahora la función runMyArrList count tendrá una lista de longitud n como entrada y devolver una lista de enteros de 1 a n.

Tenga en cuenta que todavía no hemos utilizado ninguna función de "flecha", es decir, métodos de clase de flecha o funciones escritas en términos de ellos.

4) La mayor parte del código anterior es específico de cada instancia de Arrow [1]. Todo en Control.Arrow (y Control.Category) se trata de componer flechas para hacer nuevas flechas. Si se pretende que la categoría es parte de Flecha en lugar de una clase separada:

-- combine two arrows in sequence 
>>> :: Arrow a => a b c -> a c d -> a b d 

-- the function arrow instance 
-- >>> :: (b -> c) -> (c -> d) -> (b -> d) 
-- this is just flip (.) 

-- MyArr instance 
-- >>> :: MyArr b c -> MyArr c d -> MyArr b d 

La función >>> lleva dos flechas y utiliza la salida de la primera como entrada a la segunda.

Aquí hay otro operador, comúnmente llamado "despliegue en abanico":

-- &&& applies two arrows to a single input in parallel 
&&& :: Arrow a => a b c -> a b c' -> a b (c,c') 

-- function instance type 
-- &&& :: (b -> c) -> (b -> c') -> (b -> (c,c')) 

-- MyArr instance type 
-- &&& :: MyArr b c -> MyArr b c' -> MyArr b (c,c') 

-- first and second omitted for brevity, see the accepted answer from KennyTM's link 
-- for further details. 

Desde Control.Arrow proporciona un medio para combinar los cálculos, aquí está un ejemplo:

-- function that, given an input n, returns "n+1" and "n*2" 
calc1 :: Int -> (Int,Int) 
calc1 = (+1) &&& (*2) 

he encontrado con frecuencia funciones como calc1 útil en pliegues complicados o funciones que funcionan con punteros, por ejemplo.

La clase de tipo Monad nos proporciona un medio para combinar cálculos monádicos en un solo nuevo cálculo monádico utilizando la función >>=. Del mismo modo, la clase Arrow nos proporciona medios para combinar los cálculos arrowized en un único nuevo cómputo arrowized usando unas pocas funciones primitivas (first, arr y ***, con >>> y id de Control.Category). También similar a Mónadas, la pregunta de "¿Qué hace una flecha?" no puede ser generalmente respondida. Depende de la flecha

Lamentablemente no conozco muchos ejemplos de instancias de flechas en la naturaleza. Las funciones y FRP parecen ser las aplicaciones más comunes. HXT es el único otro uso significativo que viene a la mente.

[1] Excepto count. Es posible escribir una función de conteo que haga lo mismo para cualquier instancia de ArrowLoop.

Answer 2

Hay notas de la conferencia de John Hughes de un taller de AFP (Programación funcional avanzada). Tenga en cuenta que fueron escritos antes de que las clases de flecha se cambiaron en las bibliotecas Base:

http://www.cse.chalmers.se/~rjmh/afp-arrows.pdf

Answer 3

De un vistazo a su historial de desbordamiento de pila, voy a suponer que usted se sienta cómodo con algunos de los otros clases de tipo estándar, particularmente Functor y Monoid, y comienzan con una breve analogía de ellas.

La operación única en Functor es fmap, que sirve como una versión generalizada de map en las listas. Este es prácticamente todo el propósito de la clase de tipo; define "cosas sobre las que puedes mapear". Entonces, en cierto sentido, Functor representa una generalización de ese aspecto particular de las listas.

Las operaciones para Monoid son versiones generalizadas de la lista vacía y (++), y define "cosas que se pueden combinar de forma asociativa, con una cosa particular que es un valor de identidad". Las listas son prácticamente lo más simple que se ajusta a esa descripción, y Monoid representa una generalización de ese aspecto de las listas.

De la misma manera como los dos anteriores, las operaciones en la clase Category tipo son versiones generalizadas de id y (.), y define "cosas que conectan dos tipos en una dirección particular, que se pueden conectar de cabeza a cola ". Por lo tanto, esto representa una generalización de ese aspecto de las funciones . Notablemente, no se incluyen en la generalización currying o aplicación de función.

La clase de tipo Arrow construye fuera de Category, pero el concepto subyacente es el mismo: Arrow s son las cosas que lo componen como funciones y tienen una "identidad flecha" definida para cualquier tipo. Las operaciones adicionales definidas en la clase Arrow solo definen una forma de elevar una función arbitraria a Arrow y una forma de combinar dos flechas "en paralelo" como una sola flecha entre tuplas.

Por lo tanto, lo primero que hay que tener en cuenta aquí es que expresiones que construyen Arrow s son, esencialmente, composición de funciones elaborada. Los combinadores como (***) y (>>>) son para escribir estilo "pointfree", mientras que la notación proc ofrece una manera de asignar nombres temporales a las entradas y salidas mientras se conectan las cosas.

Una cosa útil a tener en cuenta aquí es que, aunque Arrow s a veces se describen como "el siguiente paso" de Monad s, realmente no hay una relación terriblemente significativa allí. Para cualquier Monad puede trabajar con las flechas Kleisli, que son solo funciones con un tipo como a -> m b. El operador (<=<) en Control.Monad es la composición de flecha para estos.Por otro lado, Arrow s no te dan un Monad a menos que también incluyas la clase ArrowApply. Entonces no hay una conexión directa como tal.

La diferencia clave aquí es que mientras que Monad s se puede utilizar para secuenciar cálculos y hacer cosas paso a paso, Arrow s son en cierto sentido "atemporales" al igual que las funciones normales. Pueden incluir maquinaria adicional y funcionalidad que se empalma con (.), pero es más como construir una tubería, sin acumular acciones.

Las otras clases de tipos relacionadas añaden funcionalidad adicional a una flecha, como la posibilidad de combinar flechas con Either y (,).

---

Mi ejemplo favorito de un Arrow es transductores de corriente con estado, que se ven algo como esto:

data StreamTrans a b = StreamTrans (a -> (b, StreamTrans a b)) 

Una flecha StreamTrans convierte un valor de entrada a una versión "actualizada" de la producción y sí mismo; considere las formas en que esto difiere de un estado Monad.

Escribir instancias para Arrow y sus clases de tipos relacionados para el tipo anterior puede ser un buen ejercicio para entender cómo funcionan.

También escribí un similar answer previously que puede ser útil.

Answer 4

Me gustaría agregar que las flechas en Haskell son mucho más sencillas de lo que podrían parecer según la literatura. Son simplemente abstracciones de funciones.

Para ver cómo esto es prácticamente útil, considera que tienes un montón de funciones que quieres componer, donde algunas son puras y algunas son monadic. Por ejemplo, f :: a -> b, g :: b -> m1 c y h :: c -> m2 d.

Sabiendo cada uno de los tipos involucrados, que podría construir una composición a mano, pero el tipo de salida de la composición tendría que reflejar los tipos intermedios mónada (en el caso anterior, m1 (m2 d)). ¿Qué sucede si solo quisiera tratar las funciones de como si fueran solo a -> b, b -> c y c -> d? Es decir, Quiero abstraer la presencia de mónadas y razonar solo sobre los tipos subyacentes . Puedo usar flechas para hacer exactamente esto.

Aquí es una flecha, que abstrae la presencia de IO para funciones en el mónada IO, de manera que puedo componer con funciones puras sin el código componer la necesidad de saber que IO está involucrado. Comenzamos definiendo un IOArrow para envolver funciones IO:

data IOArrow a b = IOArrow { runIOArrow :: a -> IO b } 

instance Category IOArrow where 
    id = IOArrow return 
    IOArrow f . IOArrow g = IOArrow $ f <=< g 

instance Arrow IOArrow where 
    arr f = IOArrow $ return . f 
    first (IOArrow f) = IOArrow $ \(a, c) -> do 
    x <- f a 
    return (x, c) 

Entonces hago algunas funciones simples que quiero componer:

foo :: Int -> String 
foo = show 

bar :: String -> IO Int 
bar = return . read 

y utilizarlos:

main :: IO() 
main = do 
    let f = arr (++ "!") . arr foo . IOArrow bar . arr id 
    result <- runIOArrow f "123" 
    putStrLn result 

Aquí Estoy llamando a IOArrow y runIOArrow, pero si estuviera pasando estas flechas en una biblioteca de funciones polimórficas, solo tendrían que aceptar argumentos de tipo "Flecha a => a b c". Ninguno del código de la biblioteca necesitaría saber que una mónada estaba involucrada. Solo el creador y el usuario final de la flecha deben saberlo.

Generalizando IOArrow a trabajar para las funciones de ninguna mónada se llama el "Kleisli flecha", y ya hay una flecha orden interna para hacer precisamente eso:

main :: IO() 
main = do 
    let g = arr (++ "!") . arr foo . Kleisli bar . arr id 
    result <- runKleisli g "123" 
    putStrLn result 

Se podría, por supuesto, también utilizan flechas operadores de composición y la sintaxis proc, a que sea un poco más claro que las flechas están involucrados:

arrowUser :: Arrow a => a String String -> a String String 
arrowUser f = proc x -> do 
    y <- f -< x 
    returnA -< y 

main :: IO() 
main = do 
    let h =  arr (++ "!") 
      <<< arr foo 
      <<< Kleisli bar 
      <<< arr id 
    result <- runKleisli (arrowUser h) "123" 
    putStrLn result 

Aquí debe quedar claro que aunque main conoce la mónada IO está involucrado, arrowUser no. No habría forma de "ocultar" IO desde arrowUser sin flechas, no sin recurrir a unsafePerformIO para convertir el valor monádico intermedio en uno puro (y perder así el contexto para siempre). Por ejemplo:

arrowUser' :: (String -> String) -> String -> String 
arrowUser' f x = f x 

main' :: IO() 
main' = do 
    let h  = (++ "!") . foo . unsafePerformIO . bar . id 
     result = arrowUser' h "123" 
    putStrLn result 

intentar escribir que sin unsafePerformIO, y sin tener que arrowUser' acuerdo con los argumentos de tipo Monad.

Answer 5

Cuando comencé a explorar las composiciones de Arrow (esencialmente Monads), mi enfoque era romper con la sintaxis funcional y la composición con la que se asociaba más comúnmente y comenzar por comprender sus principios utilizando un enfoque más declarativo.Con esto en mente, creo que el siguiente desglose más intuitiva:

function(x) { 
    func1result = func1(x) 
    if(func1result == null) { 
    return null 
    } else { 
    func2result = func2(func1result) 
    if(func2result == null) { 
     return null 
    } else { 
     func3(func2result) 
    } 

Así que, esencialmente, para algún valor x, llamamos una primera función que asumimos puede devolver null (func1), otro que puede retun null o sea asignado a null de manera intercambiable, finalmente, una tercera función que también puede devolver null. Ahora, dado el valor x, pase x a func3, solo entonces, si no devuelve null, pase este valor a func2, y solo si este valor no es nulo, pase este valor a func1. Es más determinista y el flujo de control le permite construir un manejo de excepciones más sofisticado.

Aquí podemos utilizar la composición de la flecha: (func3 <=< func2 <=< func1) x.