Складывание flatMap/привязка к списку функций (a.k.a. Name That Combinator!)

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

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

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

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

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

Я хочу знать, есть ли стандартная функция, которая фиксирует это поведение "fold-bind". Когда я пытаюсь сыграть в игру "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

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

Ответ 1

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

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

Подумайте flip (.), но для стрелок Kleisli вместо функций.

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

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, 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 Monoid, который просто преобразует моноид в один с перевернутым mappend:

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

Это демонстрирует, что composeParts является "четко определенным шаблоном" в некотором смысле:)

Ответ 2

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

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

(или foldl)

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