triển khai "findM" trong Haskell?

Question

Tôi đang tìm một hàm cơ bản giống như mapM trên danh sách - nó thực hiện một chuỗi các hành động đơn thuần lấy mọi giá trị trong danh sách dưới dạng tham số - và mỗi hàm monadic trả về m (Maybe b). Tuy nhiên, tôi muốn nó dừng sau thông số đầu tiên làm cho hàm trả về giá trị Just, không thực hiện thêm bất kỳ giá trị nào sau đó và trả về giá trị đó.

Vâng, nó có lẽ sẽ dễ dàng hơn để chỉ hiển thị chữ ký loại:

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

nơi b là giá trị đầu tiên Just. Các Maybe trong kết quả là từ các find ing (trong trường hợp của một danh sách trống, vv), và không có gì để làm với các Maybe trả lại bởi chức năng Monadic.

Tôi dường như không thể thực hiện điều này bằng ứng dụng thư viện đơn giản. Tôi có thể sử dụng

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

mà sẽ làm việc, nhưng tôi đã thử nghiệm này và có vẻ như tất cả trong những hành động monadic được thực hiện trước khi gọi find, vì vậy tôi không thể dựa vào sự lười biếng ở đây.

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

Cách tốt nhất để triển khai chức năng này sẽ không thực thi các hành động đơn thuần sau lần trả lại "chỉ" đầu tiên là gì? Một cái gì đó mà có thể làm:

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

hoặc thậm chí, lý tưởng,

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

Hy vọng rằng có một câu trả lời mà không sử dụng đệ quy rõ ràng, và là tác phẩm của các chức năng thư viện nếu có thể? Hoặc thậm chí có thể là điểm miễn phí một?

Answer 1

Một giải pháp không có điểm đơn giản là sử dụng biến áp MaybeT. Bất cứ khi nào chúng ta thấy m (Maybe a), chúng ta có thể bọc nó vào MaybeT và chúng tôi nhận được tất cả các chức năng MonadPlus ngay lập tức. Kể từ mplus cho MaybeT thực hiện chính xác chúng ta cần - nó chạy các hành động được chỉ đứng thứ hai nếu là người đầu tiên dẫn đến Nothing-msum thực hiện chính xác những gì chúng ta cần:

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) 

---

Cập nhật: Trong trường hợp này, chúng tôi may mắn rằng có tồn tại một biến áp đơn lẻ (MaybeT) có mplus chỉ có ngữ nghĩa chúng ta cần. Nhưng trong một trường hợp chung, có thể là không thể xây dựng một biến thế như vậy. MonadPlus có một số luật phải được thỏa mãn đối với các hoạt động đơn điệu khác. Tuy nhiên, tất cả không bị mất, vì chúng tôi thực sự không cần MonadPlus, tất cả những gì chúng tôi cần là một số monoid phù hợp để gấp.

Vì vậy, giả sử chúng ta không (không thể) có MaybeT. Tính toán giá trị đầu tiên của một số chuỗi hoạt động được mô tả bằng hình mono First. Chúng ta chỉ cần tạo một biến thể đơn thuần sẽ không thực thi phần bên phải, nếu phần bên trái có một giá trị:

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) 

Cái này chính xác mô tả quy trình mà không có bất kỳ tham chiếu đến danh sách hoặc cấu trúc khác. Bây giờ chúng ta chỉ gấp trên danh sách sử dụng monoid này:

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

Hơn nữa, nó cho phép chúng ta tạo ra một hàm tổng quát hơn (và thậm chí ngắn hơn) sử dụng Data.Foldable:

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

Answer 2

này nên làm điều đó:

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

Nếu bạn thực sự muốn làm điều đó chỉ miễn phí (thêm vào như là một chỉnh sửa)

Sau đây sẽ tìm thấy một cái gì đó trong một danh sách sử dụng một functor Alternative, sử dụng một lần như trong câu trả lời của jozefg

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

Tôi không làm được gì chúng ta có thể làm (Monad m) => m . Maybe một trường hợp Alternative, nhưng chúng ta có thể giả vờ có một chức năng hiện có:

-- 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))) 

Sau đó, chúng ta có thể xác định findM trong tĩnh mạch giống như findA

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

Answer 3

Tôi thích câu trả lời Cirdec nếu bạn không nhớ đệ quy, nhưng tôi nghĩ rằng câu trả lời dựa trên nếp gấp tương đương khá là đẹp.

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

Một thử nghiệm nhỏ về cách bạn hiểu nếp gấp.

Answer 4

Điều này có thể được thể hiện khá độc đáo với máy biến áp đơn lẻ MaybeT và 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) 

Và nếu bạn thay đổi chức năng tìm kiếm của bạn để tạo ra một chồng MaybeT, nó trở nên đẹp hơn:

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

Hoặc tại điểm miễn phí:

findM' = (.) msum . map 

Phiên bản ban đầu có thể được cũng hoàn toàn không có điểm, nhưng nó trở nên khá dễ đọc:

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