摺疊flatMap /綁定過的函數列表（又名名Combinator的！）

在寫一個簡單的RPN計算器的過程中，我有以下類型別名：摺疊flatMap /綁定過的函數列表（又名名Combinator的！）

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

...我已經寫的Scala代碼好奇的前瞻性線：

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

這需要值的初始stack和適用的operations列表到該堆棧。每個操作可能會失敗（即產生一個Option[Stack]），所以我將它們排序爲flatMap。對於這個（在我看來）有點不尋常的事情是，我摺疊了一列monadic函數，而不是摺疊數據列表。

我想知道是否有一個標準函數捕獲這種「摺疊綁定」行爲。當我試圖打「名稱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（即參數翻轉），但在那裏也沒有運氣。所以我的問題是，有沒有人知道我的神祕「摺疊綁定」組合的標準名稱？

來源

2012-01-03 mergeconflict

我建議不要使用組合器的這種實現;我相信'（>> =）'的大部分實現都是以右關聯的方式使用的，所以這很可能會導致性能問題（比如左對齊的'（++）'堆棧一樣）。 – ehird 2012-01-03 18:12:29

@ehird - 我不認爲我理解......你還會怎麼建議按照從左到右的順序應用一系列'[a - > ma]'操作到某個開始的'a'或'ma '價值？另外，請記住我並不是在問一個語言特定的問題; Scala和Haskell之間的性能特徵會有所不同（你可以假設我使用'foldl'來實現嚴格性）。我真正關心的是這件事是否有一個衆所周知的名字。 – mergeconflict 2012-01-03 18:29:53

我認爲@ehird的觀點是'foldr'可以更有效率，因爲它可以提前停止（例如，如果是'Nothing'）。 – 2012-01-03 18:35:28

a -> m a只是一個Kleisli箭頭的說法和結果類型均爲一個。 Control.Monad.(>=>)構成2個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含半幺羣，這只是轉換一個獨異成一個帶有翻轉mappend：

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

這表明composeParts是在某種意義上是一個「明確的模式」:)

來源

2012-01-03 18:36:27 ehird

+1我打算給出相同的答案（直到編輯...）。我認爲'composeParts'可以說比'mysteryCombinator'乾淨。 – pat 2012-01-03 18:42:52

@pat：同意;我會直接使用'composeParts'。 – ehird 2012-01-03 18:43:33

整潔，我非常喜歡'foldr（>>>）id'的實現，並且絕對喜歡'（Category cat）=> [cat a a] - > cat a a''的表現型。 – mergeconflict 2012-01-03 19:45:20

的一個開始，一個非一元值（模flip）

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

（或foldl）

（是的，我知道這並不能回答這個問題，但代碼佈局在註釋中是不能令人滿意的。）

來源

2012-01-03 18:32:40

摺疊flatMap /綁定過的函數列表（又名名Combinator的！）

回答

相關問題