Odnalezienie brakującej etykiety "Zmniejsz" z drzewa palców Artykuł

Question

Wczorajsze Wikibender, które rozpoczęto od this stackoverflow qestion na komonadach, zakończyło się artykułem MarkCC's na stronie Finger Trees.

W artykule szeroko wykorzystuje klasę typu Reduce. Pisze o tej typografii tak, jakby była ona bardzo popularną i często używaną biblioteką, ale nie mogę jej znaleźć w hackage, ani nie mogę znaleźć wystarczającej dokumentacji, aby naprawdę zrozumieć kod.

Czy ktoś może mi pomóc zrozumieć, co Reduce typeclass robi, jak wygląda praca (-<) i (>-) operatorów, a co powinien powiedzieć mi o kod w artykule (skopiowanym poniżej)?

---

kod wpis z Finger Trees Done Right (I hope):

listingu 1: Zgłoszenie przykład do węzła

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 

Zamieszczone 2: Zgłoszenie przykład dla 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 (>-)) 

wykaz 3: Dane typy

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 Zważywszy, że jest to wspólna nazwa alternatywna dla funkcji „spasować”, to myślę, że to jest coś podobnego do the Foldable type class. Definicje instancji również wydają się mieć sens.

Klasa Foldable można zdefiniować przy użyciu tylko foldr, która ma podpis typu foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b, natomiast reducer w tym kodzie pojawi się reducer :: (Reduce t) => (a -> b -> b) -> t a -> b -> b. Poza inną kolejnością argumentów, powinna działać tak samo.

Należy zauważyć, że operatory są tylko argumentami funkcji - można je wszystkie zastąpić f lub innym podobnie generycznym identyfikatorem. Używanie operatora jako nazwy argumentu funkcji binarnej jest ... nieco nietypowym wyborem, ale podkreśla pewne aspekty struktury zgięcia.

Answer 2

Jest to zdefiniowane w artykule powiązanym w artykule: 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)