Monoid vs MonadPlus

Question

Tôi rất mới đối với cả hai Monads và Monoids và gần đây cũng đã tìm hiểu về MonadPlus. Từ những gì tôi thấy, Monoid và MonadPlus đều cung cấp loại có hoạt động nhị phân kết hợp và nhận dạng. (Tôi muốn gọi đây là semigroup trong ngôn ngữ toán học.) Vậy sự khác nhau giữa Monoid và MonadPlus là gì?

Answer 1

A semigroup là cấu trúc được trang bị hoạt động nhị phân kết hợp. A monoid là một semigroup với phần tử nhận dạng cho phép toán nhị phân.

Monads và nửa nhóm

Mỗi đơn nguyên có phải tuân theo the monad laws. Đối với trường hợp của chúng tôi, điều quan trọng là luật kết hợp. Bày tỏ bằng >>=:

(m >>= f) >>= g  ≡ m >>= (\x -> f x >>= g) 

Bây giờ chúng ta hãy áp dụng luật này để suy ra associativity cho >> :: m a -> m b -> m b:

(m >> n) >> p  ≡ (m >>= \_ -> n) >>= \_ -> p 
        ≡ m >>= (\x -> (\_ -> n) x >>= \_ -> p) 
        ≡ m >>= (\x -> n >>= \_ -> p) 
        ≡ m >>= (\x -> n >> p) 
        ≡ m >> (n >> p) 

(nơi chúng tôi đã chọn x để nó không xuất hiện trong m, n hoặc p).

Nếu chúng tôi chuyên >> để loại m a -> m a -> m a (thay b cho a), chúng ta thấy rằng cho bất kỳ loại a hoạt động >> hình thức một -nửa nhóm trên m a. Vì nó là đúng đối với bất kỳ a, chúng tôi nhận được một nhóm các nhóm liên kết được lập chỉ mục bởi a. Tuy nhiên, chúng không phải là các monoids nói chung - chúng tôi không có phần tử nhận dạng cho >>.

MonadPlus và monoids

MonadPlus thêm hơn hai cuộc phẫu thuật, mplus và mzero. MonadPlus laws tuyên bố rõ ràng rằng mplus và mzero phải tạo thành một hình đơn trên m a cho một tùy ý a. Vì vậy, một lần nữa, chúng tôi nhận được một lớp monoids được lập chỉ mục bởi a.

Lưu ý sự khác biệt giữa MonadPlus và Monoid: Monoid nói rằng một số loại đơn đáp ứng các quy tắc monoidal, trong khi MonadPlus nói rằng đối với tất cả các thể loại am a đáp ứng luật monoidal. Đây là một điều kiện mạnh mẽ hơn nhiều.

Vì vậy, một ví dụ MonadPlus tạo thành hai cấu trúc đại số khác nhau: Một nhóm semigroups với >> và một lớp monoids với mplus và mzero. (Đây không phải là một cái gì đó bất thường, ví dụ như tập hợp các số tự nhiên lớn hơn không {1,2,...} hình thức một -nửa nhóm với + và monoid với × và 1.)

Answer 2

Nếu chúng ta có mà MonadPlus m nắm giữ sau đó bạn muốn nói m là một Monad, nhưng m a (loại phát sinh từ việc áp dụng a với loại "chức năng" m) là một monoid.

Nếu chúng ta định nghĩa (tương tự như định nghĩa Data.Monoid 's, nhưng chúng tôi sẽ tận dụng sau này)

class    Semigroup a where (<>) :: a -> a -> a 
class Semigroup a => Monoid a where zero :: a 

sau đó nó có

mzero :: MonadPlus m => m a 
mplus :: MonadPlus m => m a -> m a -> m a 

với các loại khá có thể so sánh và pháp luật apropriate

-- left and right identity 
mplus a  mzero == a 
mplus mzero a  == a 

-- associativity 
(a `mplus` b) `mplus` c == a `mplus` (b `mplus` c) 

Chúng tôi thậm chí có thể xác định Haskell Monoid nếu chúng tôi sử dụng -XFlexibleInstances

{-# LANGUAGE FlexibleInstances #-} 
instance MonadPlus m => Semigroup (m a) where (<>) = mplus 
instance MonadPlus m => Monoid (m a) where zero = mzero 

dù những chồng chéo nặng với các trường hợp trong Data.Monoid, mà có lẽ là lý do tại sao nó không phải là một trường hợp tiêu chuẩn.

---

Ví dụ khác về một monoid như thế này là Alternative m => m a từ Control.Applicative.

Answer 3

Tôi phải nhấn mạnh sự khác biệt rất quan trọng: không giống như monoid, và không giống như những gì trạng thái câu trả lời khác, MonadPlus thực hiện không cung cấp loại có hoạt động nhị phân liên kết và danh tính. Báo cáo Haskell, tài liệu duy nhất có thể yêu cầu trạng thái của tiêu chuẩn, không quy định luật pháp của MonadPlus và do đó không yêu cầu mplus phải liên kết hoặc mzero làm đơn vị trái hoặc phải của nó. Có lẽ các tác giả vẫn đang tranh luận về luật: có những lý do rất tốt cho việc thừa kế không phải là kết hợp. Ví dụ, nếu mplus là kết hợp nhưng không giao hoán, tính toán tìm kiếm không xác định được biểu diễn bởi MonadPlus không thể hoàn thành (nghĩa là, có tồn tại các giải pháp mà chúng ta không thể tìm thấy). Vì nó là khá hiếm hoi mà mplus là giao hoán, bất kỳ thủ tục tìm kiếm hoàn toàn không xác định không thể được đại diện bởi MonadPlus, nếu chúng ta nhấn mạnh vào sự kết hợp. Đã có một cuộc thảo luận chi tiết về vấn đề này của luật MonadPlus trên SC: Must mplus always be associative