Cây Functor và có thể gập lại nhưng với các nút. Có sự tổng quát nào không?

Question

data Tree t = Empty | Node t (Tree t) (Tree t) 

Chúng ta có thể tạo functor dụ và sử dụng

fmap :: (t -> a) -> Tree t -> Tree a 

Nhưng nếu thay vì (t -> a) Tôi muốn (Tree t -> a) vì vậy tôi có thể có quyền truy cập vào một tổng thể (Node t) không chỉ t

treeMap :: (Tree t -> a) -> Tree t -> Tree a 
treeMap f Empty = Empty 
treeMap f n@(Node _ l r) = Node (f n) (treeMap f l) (treeMap f r) 

Cùng với lần

treeFold :: (Tree t -> a -> a) -> a -> Tree t -> a 

có tổng quát hơn func tions như thế này?

map :: (f t -> a) -> f t -> f a 
fold :: (f t -> a -> a) -> a -> f t -> a 

Answer 1

Bạn vừa phát hiện ra các dòng hài! Vâng, gần như.

class Functor f => Comonad f where 
    extract :: f a -> a 
    duplicate :: f a -> f (f a) 

instance Comonad Tree where 
    extract (Node x _ _) = x -- this one only works if your trees are guaranteed non-empty 
    duplicate t@(Node n b1 b2) = Node t (duplicate b1) (duplicate b2) 

Với duplicate bạn có thể thực hiện chức năng của mình:

treeMap f = fmap f . duplicate 
freeFold f i = foldr f i . duplicate 

Để làm điều đó đúng, bạn nên thực thi phi emptyness bởi hệ thống loại:

type Tree' a = Maybe (Tree'' a) 

data Tree'' t = Node' t (Tree' t) (Tree' t) 
    deriving (Functor) 

instance Comonad Tree'' where 
    extract (Node' x _ _) = x 
    duplicate t@(Node' _ b1 b2) = Node' t (fmap duplicate b1) (fmap duplicate b2)