Folding flatMap/bind na liście funkcji (aka imię To Combinator!)

Question

W trakcie pisania prosty kalkulator RPN, mam następujący aliasy Typ:

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

... i Pisałem ciekawy wyglądający wiersz kodu Scala:

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

Dzieje wstępną stack wartości i dotyczy listę operations do tego stosu. Każda operacja może się nie powieść (to jest uzyskać Option[Stack]), więc sekwencjonuję je za pomocą flatMap. Rzeczą niezwykłą w tym (moim zdaniem) jest to, że składam listę monadycznych funkcji, zamiast składać listę danych.

Chcę wiedzieć, czy istnieje standardowa funkcja, która przechwytuje to zachowanie "zwijania". Kiedy próbuję odtworzyć „nazwa, która Combinator” gra, Hoogle jest zwykle mój przyjaciel, więc próbowałem to samo ćwiczenie psychiczne w Haskell:

foldl (>>=) (Just stack) operations 

Tutejsze typy:

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

więc rodzaj mojej tajemnicy foldl (>>=) Combinator, po dokonaniu rodzaje foldl i (>>=) line, powinno być:

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

... co jest znowu to, co chcemy oczekiwać. Mój problem polega na tym, że wyszukiwanie Hoogle dla funkcji z tym typem nie daje żadnych wyników. Próbowałem kilka innych permutacji, które uważałem za rozsądne: a -> [a -> m a] -> m a (tzn. Zaczynając od wartości niemagadycznej), [a -> m a] -> m a -> m a (tj. Z odwróconymi argumentami), ale nie ma też szczęścia. Moje pytanie brzmi, czy ktokolwiek zna standardową nazwę mojego tajemniczego kombinatora "fałd-wiązania"?

Answer 1

a -> m a tylko Kleisli strzałka z typami argumentów i rezultatu zarówno będąc . Control.Monad.(>=>) komponuje dwa strzały Kleisli:

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

Think flip (.), ale dla Kleisli strzałki zamiast funkcji.

Więc możemy podzielić ten COMBINATOR na dwie części, skład i „Aplikacja”:

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 

Teraz (>=>) i flip (.) związane są w głębszym sensie niż po prostu będąc analogiczne; zarówno strzałka funkcji, (->), jak i typ danych zawijający strzałkę Kleisli, Kleisli, są instancjami Control.Category.Category.Więc jeśli byliśmy na import tego modułu, możemy w rzeczywistości przepisać composeParts jak:

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

(>>>) (zdefiniowane w Control.Category) jest po prostu ładniejszy sposób pisania jako flip (.).

---

Tak więc, nie znam żadnej standardowej nazwy, ale to tylko uogólnienie tworzenia listy funkcji. Istnieje typ Endo a w standardowej bibliotece, która otacza a -> a i ma instancję Monoid, gdzie mempty jest id i mappend jest (.); możemy uogólnić na dowolny Kategoria:

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) 

Możemy następnie wdrożyć composeParts jak:

composeParts = appEndo . mconcat . map Endo . reverse 

który jest po prostu mconcat . reverse z jakiegoś opakowania. Możemy jednak uniknąć reverse, który jest tam, ponieważ instancja korzysta (.) zamiast (>>>), za pomocą Dual a monoid, który właśnie przekształca monoid do jednego z obróconą mappend:

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

To pokazuje, że composeParts jest "dobrze zdefiniowany wzorzec" w pewnym sensie :)

Answer 2

Ten zaczynając o wartości nie jest monadycznej (modulo flip)

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

(lub foldl)

(Tak, wiem, że to nie jest odpowiedź na pytanie, ale układ kod w komentarzach nie jest zadowalająca.)