Сворачивание flatMap/bind поверх списка функций (он же Name That Combinator!)

Question

В процессе написания простого калькулятора RPN у меня есть следующие псевдонимы:

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

... и я написал любопытную строку кода Scala:

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

Это занимает начальный stack значений и применяет список operations в этот стек. Каждая операция может потерпеть неудачу (т.е. Option[Stack]) поэтому я их последовательности flatMap, Несколько необычно (на мой взгляд) то, что я сворачиваю список монадических функций, а не сворачиваю список данных.

Я хочу знать, есть ли стандартная функция, которая фиксирует это поведение "сгиба". Когда я пытаюсь поиграть в игру "Name That Combinator", Hoogle, как правило, является моим другом, поэтому я попробовал то же умственное упражнение в Haskell:

foldl (>>=) (Just stack) operations

Типы здесь:

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

Так что тип моей тайны foldl (>>=) комбинатор, после внесения типов foldl а также (>>=) выстроиться, должно быть:

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

... что опять-таки то, что мы ожидали. Моя проблема в том, что поиск в Google функции такого типа не дает результатов. Я попробовал пару других перестановок, которые я думал, может быть разумным: a -> [a -> m a] -> m a (т.е. начиная с немонадного значения), [a -> m a] -> m a -> m a (то есть с перебранными аргументами), но там тоже не повезло. Итак, мой вопрос: кто-нибудь знает стандартное имя для моего загадочного комбинатора "сложить-связать"?

Answer 1

a -> m a это просто стрелка Клейсли с аргументом и типом результата. Control.Monad. (> =>) Составляет две стрелки Клейсли:

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

Считать flip (.), но для Клейсли стрелки вместо функций.

Таким образом, мы можем разделить этот комбинатор на две части: композицию и "приложение":

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

Сейчас, (>=>) а также flip (.) связаны в более глубоком смысле, чем просто аналогия; обе стрелки функции, (->) и тип данных, обертывающий стрелку Клейсли, Kleisli, являются экземплярами Control.Category.Category. Так что, если бы мы импортировали этот модуль, мы могли бы переписать composeParts как:

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

(>>>) (определено в Control.Category) это просто более хороший способ записи flip (.),

---

Итак, нет стандартного имени, о котором я знаю, но это просто обобщение составления списка функций. Там есть Endo a введите стандартную библиотеку, которая упаковывает a -> a и имеет экземпляр Monoid, где mempty является id а также mappend является (.); мы можем обобщить это для любой категории:

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)

Затем мы можем реализовать composeParts как:

composeParts = appEndo . mconcat . map Endo . reverse

который просто mconcat . reverse с некоторой упаковкой. Тем не менее, мы можем избежать reverse, который существует, потому что экземпляр использует (.) скорее, чем (>>>) с помощью Dual a Моноид, который просто превращает моноид в перевернутый mappend:

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

Это показывает, что composeParts в некотором смысле это "четко определенный шаблон":)

Answer 2

Тот, который начинается с немонадного значения: (по модулю flip)

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

(или же foldl)

(Да, я знаю, что это не отвечает на вопрос, но расположение кода в комментариях не является удовлетворительным.)