Comonad trùng lặp chức năng

Question

Tại sao khi bạn xác định chức năng trùng lặp

duplicate :: w a -> w (w a)  

cho typeclass Comonad (link), bạn phải thay đổi tất cả các yếu tố "trong bối cảnh" (tức là thay đổi các yếu tố khác hơn hiện tại giá trị của ngữ cảnh). Tại sao không chỉ sử dụng một cái gì đó như trả về trong một Monad?

Ví dụ rút (khoá kéo):

data Z a = Z [a] a [a]  

lý do tại sao tôi không thể chỉ xác định trùng lặp như

duplicate z = Z [] z []  

tôi đã cố gắng để đưa ra một yêu cầu cho trùng lặp chức năng từ các quy tắc Comonad, nhưng tôi luôn kết thúc với một bản sao mà chỉ kết thúc tốt đẹp các yếu tố giống như một trả lại trong một đơn nguyên mà không cần phải làm bất cứ điều gì khác.

Một blog post nói:

trùng lặp là một chút khó khăn hơn để nắm bắt. Từ một danh sách dây kéo, chúng tôi phải xây dựng một danh sách dây kéo của danh sách dây khóa kéo. Biểu hiện đằng sau điều này (được xác nhận bởi các quy tắc comonad mà mọi trường hợp phải thực hiện) là việc di chuyển bên trong cấu trúc trùng lặp trả về cấu trúc ban đầu, bị thay đổi bởi cùng một bước di chuyển

Nhưng tôi không hiểu tại sao nó phải là theo cách đó. Các fmap trong các quy tắc Comonad luôn áp dụng đối với các yếu tố bao bọc và sau đó một yếu tố này luôn luôn là "quà nào" với chiết xuất, tại sao bận tâm làm bất cứ điều gì khác trong trùng lặp chức năng khác hơn là chỉ gói các đối số của trùng lặp ?

Bạn có thể chỉ ra những gì tôi đã bỏ lỡ không? Tôi cảm thấy như tôi đã làm một số lỗi rõ ràng ở đâu đó, nhưng tôi không thể tự mình tìm ra nó.

Cảm ơn bạn đã trả lời!

Answer 1

Điều quan trọng là bạn có thể làm những việc khác với loại đơn giản hơn là chỉ đơn giản là extract từ đó. Bằng trực giác, nếu điều duy nhất bạn có thể làm là trích xuất giá trị, thì loại chỉ chứa một giá trị, do đó sao chép một giá trị đó là sao chép mọi thứ. Đây không phải là sự thật nói chung, và nó không đúng cho zippers.

Luật Comonad chỉ là luật danh mục trong ngụy trang về các chức năng của loại w a -> b. Vì những thứ này đến từ các danh mục, có thể dễ dàng hơn để lý luận về các danh mục đó theo các điều khoản của luật Comonad. extract là danh tính của thể loại này và =<= là toán tử thành phần.

-- | Right-to-left 'Cokleisli' composition 
(=<=) :: Comonad w => (w b -> c) -> (w a -> b) -> w a -> c 
f =<= g = f . extend g 

Chúng tôi cũng biết rằng extend f = fmap f . duplicate, vì vậy chúng tôi có thể viết

f =<= g = f . fmap g . duplicate 

này trông khá dễ dàng để lý do về.Bây giờ, hãy trang bị loại Z của bạn với một chức năng khác mà chúng ta có thể nói đến. isFirst sẽ chỉ trả về true khi Z đại diện cho một giá trị tại một vị trí trong danh sách không có gì trước nó.

isFirst :: Z a -> Bool 
isFirst (Z [] _ _) = True 
isFirst _   = False 

Bây giờ, hãy xem xét điều gì xảy ra khi chúng tôi sử dụng isFirst với ba loại danh mục. Hai chỉ có vẻ như là ngay lập tức áp dụng cho nó là extract là một bản sắc trái và phải cho sáng tác bởi =<=. Vì chúng tôi chỉ loại bỏ điều này, chúng tôi chỉ cần tìm một ví dụ phản đối. Tôi nghi ngờ rằng một trong số extract =<= isFirst hoặc isFirst =<= extract sẽ không thành công cho số nhập Z [1] 2 []. Cả hai số này phải giống như isFirst $ Z [1] 2 [], là False. Chúng tôi sẽ thử extract =<= isFirst trước tiên, điều này sẽ xảy ra.

extract =<= isFirst    $ Z [1] 2 [] 
extract . fmap isFirst . duplicate $ Z [1] 2 [] 
extract . fmap isFirst $ Z []   (Z [1] 2 []) [] 
extract    $ Z [] (isFirst (Z [1] 2 [])) [] 
extract    $ Z [] False     [] 
           False 

Khi chúng tôi thử isFirst =<= extract chúng tôi sẽ không may mắn như vậy.

isFirst =<= extract    $ Z [1] 2 [] 
isFirst . fmap extract . duplicate $ Z [1] 2 [] 
isFirst . fmap extract $ Z []   (Z [1] 2 []) [] 
isFirst    $ Z [] (extract (Z [1] 2 [])) [] 
isFirst    $ Z [] 2      [] 
True 

Khi chúng tôi mất thông tin về cấu trúc. Trong thực tế, chúng tôi đã mất thông tin về mọi thứ xuất hiện ở khắp mọi nơi ngoại trừ tiêu điểm duy nhất của dây kéo. Chính xác duplicate sẽ có toàn bộ 'dây kéo không dây ở khắp mọi nơi trong bối cảnh giữ giá trị tại vị trí đó và ngữ cảnh của vị trí đó.

Hãy xem những gì chúng tôi có thể suy ra từ các luật này. Với một bàn tay nhỏ vẫy về loại chức năng, chúng ta có thể thấy rằng =<= extract là fmap extract . duplicate và điều này cần phải là chức năng nhận dạng. Rõ ràng tôi đang khám phá lại cách các luật được viết trong tài liệu cho Control.Category. Điều này cho phép chúng tôi viết một cái gì đó giống như

z = (=<= extract)    z 
z = fmap extract . duplicate $ z 

Bây giờ, z chỉ có một nhà xây dựng, vì vậy chúng tôi có thể thay thế mà trong

Z left x right = fmap extract . duplicate $ Z left x right 

Từ họ gõ của trùng lặp, chúng ta biết nó phải trả lại các nhà xây dựng tương tự.

Z left x right = fmap extract $ Z lefts (Z l x' r) rights 

Nếu chúng ta áp dụng fmap để Z này, chúng tôi có

Z left x right = Z (fmap extract lefts) (extract (Z l x' r)) (fmap extract rights) 

Nếu chúng ta chia này lên bởi các bộ phận của các nhà xây dựng Z chúng tôi có ba phương trình

left = fmap extract lefts 
x = extract (Z l x' r) 
right = fmap extract rights 

này cho chúng ta biết ít nhất là kết quả của duplicate (Z left x right) phải giữ:

• một danh sách với độ dài tương tự như left cho phía bên trái
• một Z với x ở giữa cho giữa
• một danh sách với độ dài tương tự như right cho phía bên phải

Hơn nữa, chúng ta có thể thấy rằng các giá trị ở giữa trong danh sách ở bên trái và bên phải phải giống như giá trị ban đầu trong các danh sách đó.Xem xét chỉ một luật này, chúng tôi biết đủ để yêu cầu một cấu trúc khác nhau cho kết quả của duplicate.