Tìm chữ “Giảm” Typeclass từ Cây Finger Điều

Question

Ngày hôm qua Wikibender bắt đầu bằng this stackoverflow qestion trên Comonads kết thúc tại MarkCC's bài viết trên Finger Trees.

Trong bài viết, ông sử dụng rộng rãi loại lớp học Reduce. Anh ấy viết về kiểu chữ này như thể nó là một thư viện rất phổ biến và thường xuyên sử dụng, nhưng tôi không thể tìm thấy nó trên hackage, cũng như tôi không thể tìm đủ tài liệu để thực sự hiểu được mã.

Ai đó có thể giúp tôi hiểu những gì máy đánh chữ Reduce đang hoạt động, cách các toán tử (-<) và (>-) hoạt động và điều gì sẽ cho tôi biết về mã trong bài viết (được sao chép bên dưới)?

---

Mã từ Finger Trees Done Right (I hope):

Liệt kê 1: khai dụ cho Node

instance Reduce Node where 
    reducer (-<) (Node2 a b) z = a -< (b -< z) 
    reducer (-<) (Node3 a b c) z = a -< (b -< (c -< z)) 
    reducer (>-) (Node2 b a) = (z >- b) >- a 
    reducer (>-) (Node3 c b a) = ((z >- c) >- b) >- a 

Liệt kê 2: khai dụ cho FingerTree

instance Reduce FingerTree where 
    reducer (-<) Empty zero = zero 
    reducer (-<) (Single x) zero = x -< zero 
    reducer (-<) Deep left mid right zero = left -<' (mid -<'' (right -<' zero)) 
    where (-<') = reducer (-<) 
      (-<'') = reducer (reducer (-<)) 
    reducel (>-) zero Empty = zero 
    reducel (>-) zero (Single x) = zero >- x 
    reducel (>-) zero (Deep left mid right) = ((zero >-' left) >-'' mid) >-' right 
    where (>-') = reducel (>-) 
      (>-'') = reducel (reducel (>-)) 

niêm yết 3: Dữ liệu các loại

data Node s = Node2 s s | Node3 s s s 

data FingerTree a = Empty 
    | Single a 
    | Deep (Digit a) (FingerTree (Node a)) (Digit a) 

data Digit a = [ a ] 

Answer 1

Cho rằng reduce là tên thay thế chung cho chức năng "gấp", tôi đoán rằng nó giống như the Foldable type class. Các định nghĩa cá thể dường như có ý nghĩa như vậy, là tốt.

Lớp Foldable thể được định nghĩa bằng chỉ foldr, trong đó có các loại chữ ký foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b, trong khi reducer trong mã đó dường như là reducer :: (Reduce t) => (a -> b -> b) -> t a -> b -> b. Khác với một thứ tự đối số khác, nó sẽ hoạt động tương tự.

Lưu ý rằng toán tử chỉ là đối số cho hàm - bạn có thể thay thế tất cả bằng f hoặc một số nhận dạng chung tương tự khác. Sử dụng toán tử làm tên của đối số hàm nhị phân là ... một sự lựa chọn hơi khác thường, nhưng nó nhấn mạnh một số khía cạnh của cấu trúc của nếp gấp, tôi đoán vậy.

Answer 2

Được xác định trong giấy được liên kết trong bài viết: Finger Trees: A Simple General-purpose Data Structure.

class Reduce f where 
    reducer :: (a -> b -> b) -> (f a -> b -> b) 
    reducel :: (b -> a -> b) -> (b -> f a -> b)