plegable flatMap/vinculación a través de una lista de funciones (también conocido como nombre a ese Combinator!)

Question

En el proceso de escribir una simple calculadora RPN, tengo los siguientes alias de tipo:

type Stack = List[Double] 
type Operation = Stack => Option[Stack] 

... y he escrito una línea de aspecto curioso de código Scala:

val newStack = operations.foldLeft(Option(stack)) { _ flatMap _ } 

Esto toma una inicial stack de los valores y aplica una lista de operations a la pila. Cada operación puede fallar (es decir, produce un Option[Stack]) así que las secuencia con flatMap. Lo que es algo inusual acerca de esto (en mi opinión) es que estoy doblando una lista de funciones monádicas, en lugar de doblar sobre una lista de datos.

Quiero saber si hay una función estándar que capture este comportamiento de "doblar". Cuando estoy tratando de jugar el "nombre que Combinator" del juego, Hoogle suele ser mi amigo, por lo que intentó el mismo ejercicio mental en Haskell:

foldl (>>=) (Just stack) operations 

Los tipos aquí son:

foldl :: (a -> b -> a) -> a -> [b] -> a 
(>>=) :: Monad m => m a -> (a -> m b) -> m b 

por lo que el tipo de mi combinador misterio foldl (>>=), después de hacer los tipos de foldl y (>>=) línea de arriba, debe ser:

mysteryCombinator :: Monad m => m a -> [a -> m a] -> m a 

... que es otra vez lo que había esperar. Mi problema es que al buscar en Hoogle una función con ese tipo no se obtienen resultados. Intenté algunas otras permutaciones que pensé que podrían ser razonables: a -> [a -> m a] -> m a (es decir, comenzando con un valor no monádico), [a -> m a] -> m a -> m a (es decir, con argumentos volteados), pero tampoco tuve suerte. Entonces mi pregunta es, ¿alguien sabe un nombre estándar para mi misterioso combinador "doblar"?

Answer 1

a -> m a es sólo un Kleisli flecha con los tipos de argumentos y resultados tanto de ser un . Control.Monad.(>=>) Compone dos flechas Kleisli:

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c 

Piense flip (.), pero para flechas Kleisli en lugar de funciones.

lo tanto, podemos dividir este combinador en dos partes, la composición y la "aplicación":

composeParts :: (Monad m) => [a -> m a] -> a -> m a 
composeParts = foldr (>=>) return 

mysteryCombinator :: (Monad m) => m a -> [a -> m a] -> m a 
mysteryCombinator m fs = m >>= composeParts fs 

Ahora, (>=>) y flip (.) están relacionados en un sentido más profundo que sólo son análogas; tanto la flecha de función, (->), como el tipo de datos que envuelve una flecha Kleisli, Kleisli, son instancias de Control.Category.Category.Así que si tuviéramos que importar ese módulo, se podría, de hecho, se reescribe como composeParts:

composeParts :: (Category cat) => [cat a a] -> cat a a 
composeParts = foldr (>>>) id 

(>>>) (definido en Control.Category) es sólo una manera más agradable de la escritura como flip (.).

---

Por lo tanto, no hay nombre estándar, que yo sepa, pero es sólo una generalización de componer una lista de funciones. Hay un tipo Endo a en la biblioteca estándar que envuelve a -> a y tiene una instancia Monoid donde mempty es y mappend es (.); podemos generalizar esto a cualquier Categoría:

newtype Endo cat a = Endo { appEndo :: cat a a } 

instance (Category cat) => Monoid (Endo cat a) where 
    mempty = Endo id 
    mappend (Endo f) (Endo g) = Endo (f . g) 

Podemos entonces aplicar composeParts como:

composeParts = appEndo . mconcat . map Endo . reverse 

que es sólo mconcat . reverse con un poco de envoltura. Sin embargo, podemos evitar la reverse, que está ahí porque la instancia utiliza (.) en lugar de (>>>), mediante el uso de la Dual a Monoid, que acaba transforma un monoide en uno con un volteado mappend:

composeParts :: (Category cat) => [cat a a] -> cat a a 
composeParts = appEndo . getDual . mconcat . map (Dual . Endo) 

Esto demuestra que composeParts es un "patrón bien definido" en algún sentido :)

Answer 2

El uno, comenzando con un valor que no es monádica (módulo flip)

Prelude> :t foldr (Control.Monad.>=>) return 
foldr (Control.Monad.>=>) return 
    :: Monad m => [c -> m c] -> c -> m c 

(o foldl)

(Sí, sé que esto no responde a la pregunta, pero el diseño de código en los comentarios no es satisfactoria.)