Làm thế nào để đại diện cho cây với chia sẻ trong Haskell

Question

tôi muốn đại diện cho một "cây" của hình dạng sau trong Haskell:

/\        
    /\/\ 
/\/\/\ 
/\/\/\/\ 
` ` ` ` ` 

/và \ là những ngành, 'lá. Bạn có thể thấy rằng bắt đầu từ bất kỳ nút nào, theo con đường bên trái, sau đó bên phải sẽ đưa bạn đến cùng một nút như sau đường dẫn bên phải rồi sang trái. Bạn có thể gắn nhãn các lá, áp dụng một chức năng của hai phần tử ở mỗi nút và truyền thông tin này đến gốc trong thời gian O (n^2). Những nỗ lực ngây thơ của tôi đang cho tôi một thời gian chạy theo cấp số mũ. Bất kỳ gợi ý nào?

Answer 1

Nó chắc chắn có thể xây dựng một cây có nút được chia sẻ. Ví dụ, chúng ta chỉ có thể định nghĩa:

data Tree a = Leaf a | Node (Tree a) (Tree a) 

và sau đó cẩn thận xây dựng một giá trị thuộc loại này như trong

tree :: Tree Int 
tree = Node t1 t2 
    where 
    t1 = Node t3 t4 
    t2 = Node t4 t5 
    t3 = Leaf 2 
    t4 = Leaf 3 
    t5 = Leaf 5 

để đạt được chia sẻ subtrees (trong trường hợp này t4).

Tuy nhiên, như hình thức chia sẻ này không thể quan sát được trong Haskell, nó là rất khó để duy trì: ví dụ nếu bạn đi qua một cây để relabel lá

relabel :: (a -> b) -> Tree a -> Tree b 
relabel f (Leaf x) = Leaf (f x) 
relabel f (Node l r) = Node (relabel f l) (relabel f r) 

bạn lỏng lẻo chia sẻ. Ngoài ra, khi thực hiện tính toán từ dưới lên, chẳng hạn như

sum :: Num a => Tree a -> a 
sum (Leaf n) = n 
sum (Node l r) = sum l + sum r 

bạn sẽ không tận dụng lợi thế của việc chia sẻ và có thể trùng lặp.

Để khắc phục những vấn đề này, bạn có thể làm cho việc chia sẻ rõ ràng (và do đó quan sát được) bằng cách mã hóa cây của bạn trong một cách đồ thị như:

type Ptr = Int 
data Tree' a = Leaf a | Node Ptr Ptr 
data Tree a = Tree {root :: Ptr, env :: Map Ptr (Tree' a)} 

Cây từ ví dụ trên có thể được viết như

tree :: Tree Int 
tree = Tree {root = 0, env = fromList ts} 
    where 
    ts = [(0, Node 1 2), (1, Node 3 4), (2, Node 4 5), 
      (3, Leaf 2), (4, Leaf 3), (5, Leaf 5)] 

giá phải trả là chức năng mà đi qua những cấu trúc có phần rườm rà để viết, nhưng bây giờ chúng ta có thể xác định ví dụ như một chức năng ghi nhãn lại rằng bảo tồn chia sẻ

relabel :: (a -> b) -> Tree a -> Tree b 
relabel f (Tree root env) = Tree root (fmap g env) 
    where 
    g (Leaf x) = Leaf (f x) 
    g (Node l r) = Node l r 

và sum chức năng không trùng lặp với công việc khi cây đã chia sẻ nút:

sum :: Num a => Tree a -> a 
sum (Tree root env) = fromJust (lookup root env') 
    where 
    env' = fmap f env 
    f (Leaf n) = n 
    f (Node l r) = fromJust (lookup l env') + fromJust (lookup r env') 

Answer 2

lẽ bạn có thể đại diện cho nó đơn giản là một danh sách các lá và áp dụng các mức chức năng theo trình độ cho đến khi bạn xuống đến một giá trị, tức là một cái gì đó như thế này:

type Tree a = [a] 

propagate :: (a -> a -> a) -> Tree a -> a 
propagate f xs = 
    case zipWith f xs (tail xs) of 
    [x] -> x 
    xs' -> propagate f xs'