Entender la función de enlace en Haskell

Question

Estoy familiarizado con las mónadas en la teoría de categorías (son un concepto muy fácil, de hecho), pero la función >>= en Haskell me desconcierta por completo. Ok, entonces aplicar bind a un valor de M a y una función a -> M u es lo mismo que aplicar primero la mónada a esta función, luego evaluarla en el valor especificado y multiplicar el resultado: a >>= f es lo mismo que join $ (fmap f) $ a. Pero, ¿cómo es esta una descripción natural de la computación? ¿Hay alguna forma útil de verlo que me ayude a entenderlo?

¿Hay algún buen artículo en alguna parte que sea no dirigido a alguien fresco de la jungla C++?

Answer 1

Considere el operador de composición de funciones monádicas <=<. Esto es análogo a ., excepto que funciona en funciones monádicas. Se puede definir simplemente en términos de >>=, por lo que aprender sobre uno nos educará sobre el otro.

(<=<) :: (a -> m b) -> (b -> m c) -> a -> m c 
(f <=< g) x = g x >>= f 

(.) :: (a -> b) -> (b -> c) -> a -> c 
(f . g) x = g x |> f 
    where z |> h = h z 

En el caso de ., g se "realizó" primero, y luego f se lleva a cabo en la salida del g. En el caso de <=<, gy sus efectos se "realizan" primero, y luego f y se realizan sus efectos. Es un poco inapropiado decir que uno sucede "antes" que el otro, en realidad, ya que no todas las mónadas funcionan de esa manera.

Quizás es más exacto decir que f puede aprovechar la información contextual adicional proporcionada por g. Pero que es no del todo correcto, ya que g podría potencialmente llevar información contextual. Si quieres describir las mónadas al 100%, realmente tienes que caminar sobre cáscaras de huevo.

Pero en casi todos los casos no triviales, f <=< g significa que los efectos (así como el resultado ) de la función monádica g influirán posteriormente el comportamiento de la función monádica f.

---

Para hacer frente a preguntas sobre v >>= f = join (fmap f v)

Considere f :: a -> m b y v :: m a. ¿Qué significa fmap f v? Bien fmap :: (c -> d) -> m c -> m d, y en este caso c = a y d = m b, entonces fmap f :: m a -> m (m b). Ahora, por supuesto, podemos aplicar v :: m a a esta función, lo que resulta en m (m b). pero ¿qué exactamente tiene ese tipo de resultado m (m b)?

interiorm representa el contexto de producido a partir de f. El exteriorm representa el contexto que se origina en v (n.b. fmap no debe alterar este contexto original).

Y luego usted join que m (m b), rompiendo esos dos contextos juntos en m a. Este es el corazón de la definición de Monad: debe proporcionar una forma de destruir contextos. Puede inspeccionar los detalles de implementación de varias instancias Monad para tratar de comprender cómo "destruyen" contextos juntos. Sin embargo, la conclusión aquí es que el "contexto interno" es inobservable hasta que se fusiona con el "contexto externo". Si usa v >>= f, entonces no hay noción real de de la función f que recibe un valor puro a y produce un resultado monádico simple m b. En su lugar, entendemos que f actúa dentro del contexto original de v.

Answer 2

Quizás =<< es más fácil de entender desde un punto de vista de cálculo (es solo flip (>>=)). Tiene tipeado (=<<) :: (Monad m) => (a -> m b) -> m a -> m b, y corresponde al tipo de aplicación de función, cf ($) :: (a -> b) -> a -> b. Por lo tanto, >>= se acaba de convertir la aplicación de función en el nivel monádico.

También, (>>=) se utiliza en desugaring do notación, y do corresponde sintácticamente mucho de imperiosas código (en una mónada adecuado).

Answer 3

Hmm. Creo que una buena manera de pensar es que >>= le permite componer cálculos; los cálculos en sí tienen el formato a -> m b. Entonces, m b solo representa el resultado de un cálculo.

Por lo que un cálculo solo toma algún valor y produce algún resultado. Un buen ejemplo aquí es el tipo de lista: a -> [b] representa un cálculo no determinista. Toma una entrada pero puede producir resultados múltiples. Por sí mismo, el a -> [b] como un cálculo tiene sentido. Pero, ¿cómo combinarías esto? La respuesta natural es que realizaría cada "cómputo" consecutivo en todos de los resultados anteriores. Y esto es exactamente lo que hace >>= para las listas.

Una cosa que realmente me ayudó a ver el valor práctico de esto fue pensar en los DFA y los NFA. Se puede imaginar algo trivial escribir un DFA en Haskell como esto:

data State = S1 | S2 | S3 | S4 | Q 
data Input = A | B 
transition :: State -> Input -> State 
transition S1 A = S2 
transition S1 B = S3 
-- and so on... 

entonces podríamos simplemente veces sobre la entrada:

foldl transition S1 [A, A, B, B] 

Ahora, ¿cómo habría que tomar este código y generalizarlo a NFA? Bueno, la "función" de transición para un NFA puede considerarse como un cálculo no determinista. Así podemos definir algo como:

transition S1 A = [S1, S2] 
transition S1 B = [] 

Pero ahora tendríamos que hacer un poco de gimnasia extraños utilizar foldl! Felizmente, podemos simplemente foldM en su lugar. Entonces aquí el "cálculo" modelado por la mónada es la función de transición no determinista.

Answer 4

Aquí hay una idea aproximada de cómo funciona un modelo de cálculo: Un constructor de tipo M con una instancia de Monad representa una estructura de datos paramétrica, y las partes no paramétricas de esa estructura pueden contener otra información. El return y el join corresponden a algún tipo de monoide para esas partes de la estructura.Una función a -> M b introduce información en esa estructura, basada en una entrada del tipo a. Por lo tanto, al levantar una función a -> M b a M a -> M b estamos usando la información paramétrica de M para crear información no paramétrica, y luego combinar eso con la información ya presente en un valor de tipo M a.

La naturaleza asimétrica del tipo a -> M b proporciona una dirección inherente al flujo de información no paramétrica, mientras que el requisito de asociatividad significa que el orden general es lo único que importa.

El resultado final es el aumento de funciones con algún tipo de contexto que tiene una noción integrada de causa y efecto.