Folding flatMap/ràng buộc hơn một danh sách các hàm (hay còn gọi là tên đó Combinator!)

Question

Trong quá trình viết một máy tính RPN đơn giản, tôi có bí danh loại sau đây:

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

... và tôi đã viết một đường tò mò nhìn mã Scala:

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

này có một ban đầu stack các giá trị và áp dụng một danh sách các operations để ngăn xếp đó. Mỗi thao tác có thể không thành công (tức là tạo ra một Option[Stack]) để tôi sắp xếp chúng theo số flatMap. Điều đó hơi khác thường về điều này (trong tâm trí của tôi) là tôi đang xếp chồng lên một danh sách các chức năng đơn thuần, thay vì xếp chồng lên một danh sách dữ liệu.

Tôi muốn biết liệu có một chức năng tiêu chuẩn để ghi lại hành vi "liên kết gấp" này hay không. Khi tôi đang cố gắng để chơi trò "Name That Combinator" trò chơi, Hoogle thường là bạn của tôi, vì vậy tôi cố gắng thực hiện tinh thần tương tự trong Haskell:

foldl (>>=) (Just stack) operations 

Các loại ở đây là:

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

Vì vậy, các loại bí ẩn foldl (>>=) combinator của tôi, sau khi thực hiện các loại foldl và (>>=) dòng lên phải nộp là:

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

... mà là một lần nữa những gì chúng ta muốn chờ đợi. Vấn đề của tôi là tìm kiếm Hoogle cho một chức năng với loại đó không mang lại kết quả nào. Tôi đã thử một vài hoán vị khác mà tôi nghĩ có thể là hợp lý: a -> [a -> m a] -> m a (tức là bắt đầu với giá trị không đơn nguyên), [a -> m a] -> m a -> m a (tức là với đối số bị lật), nhưng cũng không có may mắn. Vì vậy, câu hỏi của tôi là, không ai biết một tên chuẩn cho tổ hợp bí ẩn "gấp-ràng buộc" của tôi?

Answer 1

a -> m a chỉ là một Kleisli mũi tên với các loại đối số và kết quả cả hai là một. Control.Monad.(>=>) soạn hai mũi tên Kleisli:

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

Nghĩ flip (.), nhưng đối với Kleisli mũi tên thay vì chức năng.

Vì vậy, chúng ta có thể chia combinator này thành hai phần, thành phần và các "ứng dụng":

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 

Bây giờ, (>=>) và flip (.) có liên quan trong một cảm giác sâu hơn chỉ là tương tự; cả mũi tên hàm, (->) và loại dữ liệu bao quanh mũi tên Kleisli, Kleisli, là các trường hợp Control.Category.Category.Vì vậy, nếu chúng ta import module đó, chúng ta có thể trên thực tế viết lại composeParts như:

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

(>>>) (quy định tại Control.Category) chỉ là một cách đẹp hơn viết như flip (.).

---

Vì vậy, không có tên tiêu chuẩn mà tôi biết, nhưng đó chỉ là khái quát về việc tạo danh sách hàm. Có loại Endo a trong thư viện chuẩn bao bọc a -> a và có trường hợp Monoid trong đó mempty là id và mappend là (.); chúng ta có thể khái quát này cho bất kỳ loại:

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) 

Sau đó chúng tôi có thể thực hiện composeParts như:

composeParts = appEndo . mconcat . map Endo . reverse 

mà chỉ mconcat . reverse với một số gói là. Tuy nhiên, chúng ta có thể tránh được những reverse, mà là có vì dụ sử dụng (.) hơn (>>>), bằng cách sử dụng các Dual a monoid, mà chỉ biến đổi một monoid thành một với một búng mappend:

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

Điều đó chứng tỏ composeParts là một "mẫu được xác định rõ" theo một nghĩa nào đó)

Answer 2

Người bắt đầu với một giá trị không monadic là (modulo flip)

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

(hoặc foldl)

(Vâng, tôi biết điều này không trả lời câu hỏi, nhưng cách bố trí đang trong ý kiến ​​là không thỏa đáng.)