可以「綁定」對List monad做一個減少嗎？

Question

我知道如何使用僅僅使用「綁定」操作的list monad來完成等效的Scheme（或Python）map和filter函數。

下面是一些斯卡拉說明：

scala> // map 
scala> List(1,2,3,4,5,6).flatMap {x => List(x * x)}       
res20: List[Int] = List(1, 4, 9, 16, 25, 36) 

scala> // filter  
scala> List(1,2,3,4,5,6).flatMap {x => if (x % 2 == 0) List() else List(x)} 
res21: List[Int] = List(1, 3, 5) 

，並在Haskell同樣的事情：

Prelude> -- map 
Prelude> [1, 2, 3, 4, 5, 6] >>= (\x -> [x * x]) 
[1,4,9,16,25,36] 

Prelude> -- filter 
Prelude> [1, 2, 3, 4, 5, 6] >>= (\x -> if (mod x 2 == 0) then [] else [x]) 
[1,3,5] 

計劃和Python也有一個reduce功能往往與map和filter分組。 reduce函數使用所提供的二元函數組合列表的前兩個元素，然後將其結合到下一個元素，然後繼續。計算值列表的總和或乘積的常用方法。下面是一些Python來說明：

>>> reduce(lambda x, y: x + y, [1,2,3,4,5,6]) 
21 
>>> (((((1+2)+3)+4)+5)+6) 
21 

有沒有辦法做到這一點reduce的使用上的列表單子只是綁定操作相當於？如果綁定本身無法做到這一點，那麼執行此操作的最「單點」方式是什麼？

如果可能，請在回答時限制/避免使用語法糖（即：在Haskell中使用do表示法或在Scala中使用序列綜合法）。

Answer 1

綁定操作的定義屬性之一是結果仍然在monad¹的「內部」。所以當你在列表上執行綁定時，結果將再次成爲一個列表。由於減少操作²通常會導致列表以外的其他操作，因此無法用綁定操作來表示。

除此之外，列表上的綁定操作（即concatMap/flatMap）只能一次查看一個元素，並且無法重用先前步驟的結果。所以，即使我們可以將結果包裝在單元素列表中，也沒有辦法只用monad操作。

---

¹所以，如果你有一個類型，使您可以通過除外單子類型類中定義的在其上執行任何操作，你永遠無法「突破」的單子。這就是IO monad的作用。順便說一下，在Haskell和Scala中被稱爲摺疊。

Answer 2

如果綁定本身無法完成此操作，那麼執行此操作的最「單點」方法是什麼？

雖然通過@ sepp2k給出的答案是正確的，有一種方法做一個列表monadically一個reduce式的操作，但使用該產品或「作家」的單子，並對應於分發操作產品單子通過列表函子。

的定義是：

import Control.Monad.Writer.Lazy 
import Data.Monoid 

reduce :: Monoid a => [a] -> a 
reduce xs = snd . runWriter . sequence $ map tell xs 

讓我解壓：

• 的Writer單子具有數據類型Writer w a這基本上是一個值a的元組（產品）和 「寫」值w。類型寫入的值w的必須是幺其中Writer單子的綁定操作定義是這樣的：

  (w, a) >>= f = let (w', b) = f a in (mappend w w', b) 
  

  即採取傳入寫入的值，並且將結果寫入值，和組合它們使用monoid的二進制操作。

• tell操作寫入值tell :: w -> Writer w()。因此，map tell具有類型[a] -> [Writer a()]，即其中原始列表的每個元素已被「寫入」單子中的一元值的列表。

• sequence :: Monad m => [m a] -> m [a]對應於分配法在列表和單子之間，即將單子類型分佈在列表類型上; sequence可以以結合的術語來定義：

  sequence [] = return [] 
  sequnece (x:xs) = x >>= (\x' -> (sequence xs) >>= (\xs' -> return $ x':xs')) 
  

  （actually the implementation in Prelude uses foldr，一個線索的還原狀使用）

  因此，sequence $ map tell xs已鍵入Writer a [()]

• 的runWriter操作拆包WriterrunWriter :: Writer w a -> (a, w), 這裏用snd來構成累計值。

上的Int小號列出一個例子用法是使用幺實例：

instance Monoid Int where 
       mappend = (+) 
       mempty = 0 

則：

> reduce ([1,2,3,4]::[Int]) 
    10