在Haskell中實現「findM」？

我正在尋找一個基本類似於列表mapM的函數 - 它執行一系列以列表中的每個值作爲參數的monadic動作 - 並且每個monadic函數返回m (Maybe b)。但是，我希望它在第一個參數導致函數返回值Just後停止，之後不再執行，並返回該值。在Haskell中實現「findM」？

那麼，它可能會更容易只顯示類型簽名：

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

其中b是第一Just值。結果中的Maybe來自find ing（在空列表等的情況下），並且與由Monadic函數返回的Maybe無關。

我似乎無法用一個簡單的庫函數應用程序來實現它。我可以用

findM f xs = fmap (fmap fromJust . find isJust) $ mapM f xs

這將工作，但我試用了一下，似乎所有的單子行動呼籲find之前執行的，所以我不能靠懶惰這裏。

ghci> findM (\x -> print x >> return (Just x)) [1,2,3] 
1 
2 
3 
-- returning IO (Just 1)

實現此功能的最佳方式是在第一次「正確」返回後不會執行monadic操作？東西會做：

ghci> findM (\x -> print x >> return (Just x)) [1,2,3] 
1 
-- returning IO (Just 1)

甚至，理想情況下，

ghci> findM (\x -> print x >> return (Just x)) [1..] 
1 
-- returning IO (Just 1)

希望有不使用顯式的遞歸，並且如果可能的庫函數組成一個答案？或者，甚至可能是一個免費之一？

來源

2013-09-01 Justin L.

一個簡單的無點解決方案是使用MaybeT變壓器。無論何時我們看到m (Maybe a)，我們都可以將它包裝到MaybeT中，我們立即獲得所有MonadPlus函數。由於mplus爲MaybeT不正是我們所需要的 - 它運行僅當第一個導致Nothing第二給定的動作 - msum不正是我們所需要的：

import Control.Monad 
import Control.Monad.Trans.Maybe 

findM :: (Monad m) => (a -> m (Maybe b)) -> [a] -> m (Maybe b) 
findM f = runMaybeT . msum . map (MaybeT . f)

更新：在這種情況下，我們幸運的是，存在一個monad變換器（MaybeT），其mplus只是我們需要的語義。但在一般情況下，可能會構建這種變壓器。 MonadPlus有一些必須符合其他monadic操作的法律。然而，所有不會丟失，因爲我們實際上不需要MonadPlus，我們需要的是一個合適的monoid摺疊。

那麼讓我們假裝我們沒有（不能）有MaybeT。計算一些操作序列的第一個值由First monoid描述。我們只是需要做的是將不執行正確的部分單子變型，如果左側部分有一個值：

newtype FirstM m a = FirstM { getFirstM :: m (Maybe a) } 
instance (Monad m) => Monoid (FirstM m a) where 
    mempty = FirstM $ return Nothing 
    mappend (FirstM x) (FirstM y) = FirstM $ x >>= maybe y (return . Just)

這正是幺描述過程中沒有任何參考列表或其他結構。現在，我們只是用這個幺倍以上列表：

findM' :: (Monad m) => (a -> m (Maybe b)) -> [a] -> m (Maybe b) 
findM' f = getFirstM . mconcat . map (FirstM . f)

此外，它允許我們使用Data.Foldable創造一個更通用的（甚至更短）功能：

findM'' :: (Monad m, Foldable f) 
     => (a -> m (Maybe b)) -> f a -> m (Maybe b) 
findM'' f = getFirstM . foldMap (FirstM . f)

來源

2013-09-01 08:12:21

哈！看起來我們在同一時間有完全相同的想法。雖然你有點快。 :) – shang

是的。 'Maybe'的'MonadPlus'實例中的'mzero'和'mplus'與'Maybe'的'Alternative'實例中的'empty'和'<|>'完全相同。 'MaybeT'的'mzero'和'mplus'是'return Nothing'和我定義的'<||>'函數，除了用我的原始答案和jozefg的答案來寫。我們所缺少的關於這個問題的完整論文是解釋如何從查看'（Monad m）=> m。 f'爲f寫一個monad變換器，以便你可以替換m。 f'帶一個新的數據類型，所以你可以開始寫它的實例。 – Cirdec

@Cirdec我更新了答案。在一般情況下，可能無法構建這樣的變壓器，但我們實際上並不需要。有足夠的幺半羣並摺疊它。 –

這應做到：

findM _ [] = return Nothing 
findM filter (x:xs) = 
    do 
     match <- filter x 
     case match of 
      Nothing -> findM filter xs 
      _ -> return match

如果你真的想這樣做，指向自由（添加爲編輯）

下面將使用Alternative函子發現列表中的東西，採用摺疊在jozefg的答案

findA :: (Alternative f) => (a -> f b) -> [a] -> f b 
findA = flip foldr empty . ((<|>) .)

我沒有的東西我們可以(Monad m) => m . Maybe的實例Alternative，但我們可以假裝有一個現有的功能：

-- Left biased choice 
(<||>) :: (Monad m) => m (Maybe a) -> m (Maybe a) -> m (Maybe a) 
(<||>) left right = left >>= fromMaybe right . fmap (return . Just) 
-- Or its hideous points-free version 
(<||>) = flip ((.) . (>>=)) (flip ((.) . ($) . fromMaybe) (fmap (return . Just)))

然後我們就可以在同樣定義findM爲findA

findM :: (Monad m) => (a -> m (Maybe b)) -> [a] -> m (Maybe b) 
findM = flip foldr (return Nothing) . ((<||>) .)

來源

2013-09-01 03:07:25 Cirdec

我喜歡Cirdec的答案，如果你不介意的遞歸，但我認爲基於等價摺疊的答案非常漂亮。

findM f = foldr test (return Nothing) 
    where test x m = do 
       curr <- f x 
       case curr of 
        Just _ -> return curr 
        Nothing -> m

一個很好的測試你對褶皺的理解程度。

來源

2013-09-01 03:38:25 jozefg

有沒有一種方法可以做到這一點方面替代的'<|>'？它似乎非常接近於能夠免費點 –

這可以非常好聽表達與MaybeT monad變壓器和Data.Foldable。

import Data.Foldable (msum) 
import Control.Monad.Trans.Maybe (MaybeT(..)) 

findM :: Monad m => (a -> m (Maybe b)) -> [a] -> m (Maybe b) 
findM f = runMaybeT . msum . map (MaybeT . f)

如果你改變你的搜索功能產生MaybeT棧，它變得更好：

findM' :: Monad m => (a -> MaybeT m b) -> [a] -> MaybeT m b 
findM' f = msum . map f

或者在點免費電話：

findM' = (.) msum . map

原來的版本可以也完全沒有點錯，但它變得相當不可讀：

findM = (.) runMaybeT . (.) msum . map . (.) MaybeT

來源

2013-09-01 08:21:48 shang

在Haskell中實現「findM」？

回答

相關問題