Сворачивание flatMap / bind поверх списка функций (a.k.a. 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 - это просто стрелка Клейсли с аргументами и типами результатов, равными 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 Monoid, который просто превращает моноид в моно с перевернутым 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)

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