Mũi tên có thể làm gì mà Monads không thể?

Question

Mũi tên dường như trở nên phổ biến trong cộng đồng Haskell, nhưng có vẻ như với tôi như Monads mạnh hơn. Những gì đạt được bằng cách sử dụng mũi tên? Tại sao Monads không thể được sử dụng thay thế?

Answer 1

Tôi luôn cảm thấy khó khăn khi nghĩ về vấn đề trong các thuật ngữ này: những gì đạt được bằng cách sử dụng các mũi tên. Như các nhà bình luận khác đã đề cập, mỗi đơn nguyên có thể được biến thành một mũi tên. Vì vậy, một đơn nguyên có thể làm tất cả những điều mũi tên-y. Tuy nhiên, chúng ta có thể làm cho mũi tên không phải là monads. Đó là để nói, chúng ta có thể tạo ra các loại có thể thực hiện những điều mũi tên mà không làm cho chúng hỗ trợ ràng buộc đơn thuần. Nó có thể không có vẻ như trường hợp, nhưng chức năng liên kết monadic thực sự là một hoạt động khá hạn chế (do đó mạnh mẽ) mà loại bỏ nhiều loại.

Xem, để hỗ trợ ràng buộc, bạn phải có khả năng khẳng định rằng bất kể loại đầu vào, điều gì sẽ xảy ra sẽ được bao bọc trong đơn nguyên.

(>>=) :: forall a b. m a -> (a -> m b) -> m b 

Nhưng, làm thế nào chúng ta sẽ xác định ràng buộc cho một loại như data Foo a = F Bool a Chắc chắn, chúng tôi có thể kết hợp một một Foo với của người khác nhưng làm thế nào chúng tôi sẽ kết hợp các bools. Hãy tưởng tượng rằng Bool được đánh dấu, có hay không giá trị của tham số kia đã thay đổi. Nếu tôi có a = Foo False whatever và tôi ràng buộc nó vào một hàm, tôi không biết liệu chức năng đó có thay đổi whatever hay không. Tôi không thể viết một ràng buộc thiết lập chính xác Bool. Điều này thường được gọi là vấn đề của siêu thông tin tĩnh. Tôi không thể kiểm tra chức năng bị ràng buộc vào để xác định có hay không nó sẽ thay đổi whatever. Có một số trường hợp khác như thế này: các loại đại diện cho chức năng đột biến, phân tích cú pháp có thể thoát sớm, vv Nhưng ý tưởng cơ bản là: monads đặt một thanh cao không phải tất cả các loại đều có thể xóa. Các mũi tên cho phép bạn soạn các kiểu (có thể hoặc không thể hỗ trợ chuẩn cao, ràng buộc này) theo những cách mạnh mẽ mà không phải thỏa mãn ràng buộc. Tất nhiên, bạn mất một số sức mạnh của các monads.

Đạo đức của câu chuyện: không có mũi tên nào có thể làm đơn nguyên đó không thể, bởi vì một đơn nguyên luôn có thể được tạo thành mũi tên. Tuy nhiên, đôi khi bạn không thể làm cho các loại của bạn thành monads nhưng bạn vẫn muốn cho phép họ có được sự linh hoạt và sức mạnh của các thành phần.

Nhiều người trong số những ý tưởng này được lấy cảm hứng từ tuyệt vời Understanding Haskell Arrows

Answer 2

Câu hỏi không đúng. Nó giống như hỏi tại sao bạn lại ăn cam thay vì táo, vì táo dường như có nhiều dinh dưỡng hơn.

Mũi tên, như monads, là cách thể hiện tính toán, nhưng họ phải tuân theo một tập hợp khác nhau là laws. Đặc biệt, pháp luật có xu hướng làm cho mũi tên đẹp hơn để sử dụng khi bạn có những thứ giống như chức năng.

Wiki Haskell liệt kê một tên few introductions. Đặc biệt, các Wikibook là một giới thiệu cấp cao đẹp, và các tutorial bởi John Hughes là một tổng quan tốt về các loại mũi tên.

Ví dụ thế giới thực, so sánh this tutorial sử dụng giao diện dựa trên mũi tên của Hakyll 3, với khoảng the same thing trong giao diện dựa trên mon đơn của Hakyll 4.

Answer 3

Mỗi đơn nguyên làm nảy sinh một mũi tên

newtype Kleisli m a b = Kleisli (a -> m b) 
instance Monad m => Category (Kleisli m) where 
    id = Kleisli return 
    (Kleisli f) . (Kleisli g) = Kleisli (\x -> (g x) >>= f) 
instance Monad m => Arrow (Kleisli m) where 
    arr f = Kleisli (return . f) 
    first (Kleisli f) = Kleisli (\(a,b) -> (f a) >>= \fa -> return (fa,b)) 

Nhưng, có những mũi tên mà không phải là monads. Vì vậy, có những mũi tên làm những việc mà bạn không thể làm với monads. Một ví dụ điển hình là biến áp mũi tên để thêm một số thông tin tĩnh

data StaticT m c a b = StaticT m (c a b) 
instance (Category c, Monoid m) => Category (StaticT m c) where 
    id = StaticT mempty id 
    (StaticT m1 f) . (StaticT m2 g) = StaticT (m1 <> m2) (f . g) 
instance (Arrow c, Monoid m) => Arrow (StaticT m c) where 
    arr f = StaticT mempty (arr f) 
    first (StaticT m f) = StaticT m (first f) 

mũi tên này là hữu ích vì nó có thể được sử dụng để theo dõi các thuộc tính tĩnh của một chương trình. Ví dụ: bạn có thể sử dụng công cụ này để cụ thể API của bạn để đo lường tĩnh số lượng cuộc gọi bạn đang thực hiện.

Answer 4

Vâng, tôi sẽ để lừa một chút ở đây bằng cách thay đổi câu hỏi từ Arrow để Applicative. Rất nhiều động cơ tương tự được áp dụng và tôi biết các ứng dụng tốt hơn mũi tên. (Và trên thực tế, every Arrow is also an Applicative nhưng not vice-versa, vì vậy tôi chỉ cần lấy nó xuống một chút nữa xuống dốc để Functor.)

Cũng giống như tất cả các Monad là một Arrow, mỗi Monad cũng là một Applicative. Có Applicatives không phải là Monad s (ví dụ: ZipList), do đó, đó là một câu trả lời có thể.

Nhưng giả sử chúng ta đang xử lý loại thừa nhận một phiên bản Monad cũng như Applicative. Tại sao chúng ta có thể sử dụng dụ Applicative thay vì Monad? Bởi vì Applicative ít mạnh mẽ, và đi kèm với lợi ích:

1. Có những điều chúng ta biết rằng Monad có thể làm mà Applicative không thể. Ví dụ: nếu chúng tôi sử dụng trường hợp Applicative của IO để lắp ráp một hành động ghép từ những hành động đơn giản hơn, thì không có hành động nào mà chúng tôi soạn có thể sử dụng kết quả của bất kỳ hành động nào khác. Tất cả các ứng dụng IO có thể thực hiện là thực thi các hành động thành phần và kết hợp các kết quả của chúng với các hàm thuần túy.
2. Applicative loại có thể được viết để chúng tôi có thể phân tích tĩnh mạnh mẽ của các hành động trước khi thực hiện chúng. Vì vậy, bạn có thể viết một chương trình kiểm tra hành động Applicative trước khi thực hiện, tìm hiểu xem nó sẽ làm gì và sử dụng nó để cải thiện hiệu suất, cho người dùng biết điều gì sẽ được thực hiện, v.v.

Ví dụ của người đầu tiên, tôi đã làm việc để thiết kế một loại ngôn ngữ tính toán OLAP sử dụng Applicative s. Loại thừa nhận một phiên bản Monad, nhưng tôi đã cố ý tránh việc đó, bởi vì tôi muốn các truy vấn là ít hơn mạnh mẽ hơn những gì Monad sẽ cho phép. Applicative có nghĩa là mỗi phép tính sẽ được tính theo số lượng truy vấn dự đoán được.

Ví dụ về sau, tôi sẽ sử dụng ví dụ đồ chơi từ my still-under-development operational Applicative library. Nếu bạn viết đơn nguyên Reader như một chương trình hoạt động Applicative thay vào đó, bạn có thể kiểm tra kết quả Reader s để đếm bao nhiêu lần họ sử dụng ask hoạt động:

{-# LANGUAGE GADTs, RankNTypes, ScopedTypeVariables #-} 

import Control.Applicative.Operational 

-- | A 'Reader' is an 'Applicative' program that uses the 'ReaderI' 
-- instruction set. 
type Reader r a = ProgramAp (ReaderI r) a 

-- | The only 'Reader' instruction is 'Ask', which requires both the 
-- environment and result type to be @r@. 
data ReaderI r a where 
    Ask :: ReaderI r r 

ask :: Reader r r 
ask = singleton Ask 

-- | We run a 'Reader' by translating each instruction in the instruction set 
-- into an @r -> a@ function. In the case of 'Ask' the translation is 'id'. 
runReader :: forall r a. Reader r a -> r -> a 
runReader = interpretAp evalI 
    where evalI :: forall x. ReaderI r x -> r -> x 
      evalI Ask = id 

-- | Count how many times a 'Reader' uses the 'Ask' instruction. The 'viewAp' 
-- function translates a 'ProgramAp' into a syntax tree that we can inspect. 
countAsk :: forall r a. Reader r a -> Int 
countAsk = count . viewAp 
    where count :: forall x. ProgramViewAp (ReaderI r) x -> Int 
      -- Pure :: a -> ProgamViewAp instruction a 
      count (Pure _) = 0 
      -- (:<**>) :: instruction a 
      --   -> ProgramViewAp instruction (a -> b) 
      --   -> ProgramViewAp instruction b 
      count (Ask :<**> k) = succ (count k) 

Như tốt nhất như tôi hiểu, bạn không thể viết countAsk nếu bạn triển khai Reader làm một đơn nguyên. (Sự hiểu biết của tôi đến from asking right here in Stack Overflow, tôi sẽ thêm.)

Động cơ tương tự này thực sự là một trong những ý tưởng đằng sau Arrow s.Một trong những ví dụ thúc đẩy lớn cho Arrow là một thiết kế bộ phối hợp phân tích cú pháp sử dụng "thông tin tĩnh" để có được hiệu suất tốt hơn so với các trình phân tích cú pháp đơn thuần. Ý nghĩa của chúng bằng "thông tin tĩnh" ít nhiều giống như trong ví dụ Reader của tôi: có thể viết một ví dụ Arrow nơi các trình phân tích cú pháp có thể được kiểm tra rất nhiều giống như của tôi có thể là Reader s. Sau đó, thư viện phân tích cú pháp có thể, trước khi thực hiện một trình phân tích cú pháp, kiểm tra nó để xem liệu nó có thể dự đoán trước thời gian mà nó sẽ thất bại và bỏ qua nó trong trường hợp đó hay không.

Trong một trong những nhận xét trực tiếp cho câu hỏi của bạn, jberryman đề cập đến việc các mũi tên trên thực tế có thể mất phổ biến. Tôi sẽ thêm nó như tôi thấy, Applicative là những gì mũi tên đang mất phổ biến.

---

Tài liệu tham khảo:

• Paolo Capriotti & Ambrus Kaposi, "Free Applicative Functors". Rất khuyến khích.
• Gergo Erdi, "Static analysis with Applicatives". Truyền cảm hứng, nhưng tôi rất khó để theo dõi ...