Chức năng Unadence Monad trong Haskell

Question

Tôi đang gặp phải một số rắc rối thực sự khi thiết kế chức năng của chức năng sequence của Haskell, mà Hoogle nói với tôi chưa tồn tại. Đây là cách ứng xử:

ghci> sequence [Just 7, Just 8, Just 9] 
Just [7,8,9] 
ghci> sequence [getLine, getLine, getLine] 
hey 
there 
stack exchange 
["hey","there","stack exchange"] :: IO [String] 

Vấn đề của tôi là thực hiện một chức năng như thế này:

unsequence :: (Monad m) => m [a] -> [m a] 

Vì vậy mà nó cư xử như thế này:

ghci> unsequence (Just [7, 8, 9]) 
[Just 7, Just 8, Just 9] 
ghci> sequence getLine 
hey 
['h','e','y'] :: [IO Char] --(This would actually cause an error, but hey-ho.) 

tôi không thực sự biết nếu điều đó là có thể, bởi vì tôi muốn thoát khỏi cái đơn tại một thời điểm nào đó, nhưng tôi đã bắt đầu, mặc dù tôi không biết cách đặt điểm ngắt cho hàm đệ quy này:

unsequence m = (m >>= return . head) : unsequence (m >>= return . tail) 

Tôi nhận thấy rằng tôi cần điểm ngắt khi m ở đây bằng return [], nhưng không phải tất cả các đơn vị đều có Eq trường hợp, vậy làm cách nào tôi có thể thực hiện việc này? Điều này thậm chí có thể? Nếu vậy, tại sao và tại sao không? Xin hãy nói với tôi điều đó.

Answer 1

Thực sự không thể tạo ra hàm unsequence chỉ sử dụng monads. Lý do là:

1. Bạn có thể tạo cấu trúc đơn sắc một cách an toàn và dễ dàng từ giá trị sử dụng return.
2. Tuy nhiên, không an toàn khi xóa giá trị khỏi cấu trúc đơn sắc. Ví dụ: bạn không thể xóa phần tử khỏi danh sách trống (tức là chức năng loại [a] -> a không an toàn).
3. Do đó, chúng tôi có chức năng đặc biệt (ví dụ: >>=), một cách an toàn sẽ xóa giá trị khỏi cấu trúc đơn lẻ (nếu có), xử lý và trả lại cấu trúc đơn thuần an toàn khác.

Do đó, an toàn để tạo cấu trúc đơn nguyên từ một giá trị. Tuy nhiên, không an toàn để loại bỏ một giá trị từ một cấu trúc đơn lẻ.

Giả sử chúng tôi có chức năng extract :: Monad m => m a -> a có thể “ an toàn ” xóa giá trị khỏi cấu trúc đơn sắc. Sau đó, chúng tôi có thể triển khai unsequence như sau:

unsequence :: Monad m => m [a] -> [m a] 
unsequence = map return . extract 

Tuy nhiên, không có cách nào để trích xuất giá trị từ cấu trúc đơn sắc. Do đó, unsequence [] và unsequence Nothing sẽ trả lại undefined.

Tuy nhiên, bạn có thể tạo một hàm unsequence cho các cấu trúc vừa đơn thuần vừa sinh động. A Comonad được định nghĩa như sau:

class Functor w => Comonad w where 
    extract :: w a -> a 
    duplicate :: w a -> w (w a) 
    extend :: (w a -> b) -> w a -> w b 

    duplicate = extend id 
    extend f = fmap f . duplicate 

Cấu trúc comonadic trái ngược với cấu trúc đơn nguyên. Cụ thể:

1. Bạn có thể trích xuất một cách an toàn giá trị từ cấu trúc comonadic.
2. Tuy nhiên, bạn không thể tạo cấu trúc comonadic mới một cách an toàn từ một giá trị, đó là lý do tại sao hàm duplicate tạo an toàn cấu trúc comonadic mới từ một giá trị.

Hãy nhớ rằng định nghĩa của unsequence yêu cầu cả hai return và extract? Bạn không thể tạo cấu trúc comonadic mới một cách an toàn từ một giá trị (tức là cấu trúc comonadic không có return). Do đó chức năng unsequence được định nghĩa như sau:

unsequence :: (Comonad m, Monad m) => m [a] -> [m a] 
unsequence = map return . extract 

Điều thú vị sequence công trình trên các cấu trúc đơn giản monadic. Vì vậy, thông qua trực giác bạn có thể giả định rằng unsequence hoạt động trên cấu trúc đơn giản comonadic. Tuy nhiên nó không phải như vậy bởi vì trước tiên bạn cần trích xuất danh sách từ cấu trúc comonadic và sau đó đặt từng phần tử của danh sách vào một cấu trúc đơn nguyên.

Phiên bản chung của unsequence chức năng chuyển đổi một cấu trúc danh sách comonadic vào một danh sách các cấu trúc monadic:

unsequence :: (Comonad w, Monad m) => w [a] -> [m a] 
unsequence = map return . extract 

Mặt khác các sequence chức năng hoạt động trên cấu trúc đơn giản monadic vì bạn chỉ gấp danh sách các cấu trúc đơn nguyên thành cấu trúc danh sách đơn sắc bằng cách chuỗi tất cả các monads:

sequence :: Monad m => [m a] -> m [a] 
sequence = foldr cons (return []) 
    where cons mx mxs = do 
     x <- mx 
     xs <- mxs 
     return $ x:xs 

Hy vọng điều đó sẽ hữu ích.

Answer 2

Bạn không thể có số unsequence :: (Monad m) => m [a] -> [m a]. Vấn đề nằm trong danh sách: bạn không thể chắc chắn làm thế nào các yếu tố bạn sẽ nhận được với một danh sách, và điều đó phức tạp bất kỳ định nghĩa hợp lý của unsequence.

Điều thú vị là nếu bạn đã hoàn toàn, 100% chắc chắn rằng danh sách bên trong đơn nguyên là vô hạn, bạn có thể viết một cái gì đó như:

unsequenceInfinite :: (Monad m) => m [a] -> [m a] 
unsequenceInfinite x = fmap head x : unsequenceInfinite (fmap tail x) 

Và nó sẽ làm việc!

Cũng hãy tưởng tượng rằng chúng tôi có một hàm Pair nằm xung quanh. Chúng tôi có thể viết unsequencePair như

unsequencePair :: (Monad m) => m (Pair a) -> Pair (m a) 
unsequencePair x = Pair (fmap firstPairElement x) (fmap secondPairElement x) 

Nói chung, nó quay ra bạn chỉ có thể xác định unsequence cho functors với tài sản mà bạn có thể luôn luôn "zip" cùng hai giá trị mà không làm mất thông tin. Danh sách vô hạn (trong Haskell, một loại có thể cho chúng là Cofree Identity) là một ví dụ. Các Pair functor là một. Nhưng không phải danh sách thông thường hoặc functors như Maybe hoặc Either.

Trong gói distributive, có một kiểu chữ được gọi là Distributive đóng gói thuộc tính này. unsequence của bạn được gọi là distribute ở đó.