फिंगर ट्री से गुमशुदा 'कम करें' टाइपक्लास ढूंढना आलेख

Question

कल Wikibender जो this stackoverflow qestion के साथ शुरू हुआ था, MarkCC'sFinger Trees पर आलेख समाप्त हुआ।

लेख में वह Reduce प्रकार वर्ग का व्यापक उपयोग करता है। वह इस टाइपक्लास के बारे में लिखता है जैसे कि यह एक बहुत आम और अक्सर उपयोग पुस्तकालय है, लेकिन मुझे इसे हैकेज पर नहीं मिल रहा है, और न ही मुझे कोड को वास्तव में समझने के लिए पर्याप्त दस्तावेज मिल सकता है।

किसी की मदद कर सकते हैं मुझे समझने क्या Reduce typeclass कर रहा है, कैसे (-<) और (>-) ऑपरेटरों काम है, और क्या मुझे लेख (नीचे की नकल की) में कोड के बारे में बताना चाहिए?

---

कोड लिस्टिंग Finger Trees Done Right (I hope) से:

लिस्टिंग 1: नोड के लिए उदाहरण घोषणा

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 

लिस्टिंग 2: 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 (>-)) 

सूची 3: डेटा प्रकार

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

यह देखते हुए कि reduce एक "तह" समारोह के लिए एक आम वैकल्पिक नाम है, मुझे लगता है था कि यह the Foldable type class को कुछ इसी तरह है। उदाहरण परिभाषाएं इस तरह के रूप में भी समझ में आती हैं। कि कोड में reducerreducer :: (Reduce t) => (a -> b -> b) -> t a -> b -> b प्रतीत होता है जबकि

Foldable वर्ग, बस foldr, जो प्रकार हस्ताक्षर foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b है का उपयोग कर परिभाषित किया जा सकता। एक अलग तर्क आदेश के अलावा, यह वही काम करना चाहिए।

ध्यान दें कि ऑपरेटर फ़ंक्शन के लिए केवल तर्क हैं - आप उन्हें f या अन्य समान सामान्य पहचानकर्ता के साथ बदल सकते हैं। एक ऑपरेटर का उपयोग एक बाइनरी फ़ंक्शन तर्क के नाम के रूप में करना है ... थोड़ा असामान्य विकल्प है, लेकिन यह गुना की संरचना के कुछ पहलुओं पर जोर देता है, मुझे लगता है।

Answer 2

यह लेख में लिखे गए पेपर में परिभाषित किया गया है: 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)