Missing 'reducir' clase de tipos de dedo Árbol artículo

Question

de Wikibender ayer que comenzó con this stackoverflow qestion en Comonads terminaron en MarkCC's artículo sobre Finger Trees.

En el artículo hace un uso extensivo de la clase de tipo Reduce. Escribe sobre esta clase de tipos como si fuera una biblioteca muy común y de uso frecuente, pero no puedo encontrarla en hackage, ni puedo encontrar suficiente documentación para comprender realmente el código.

Puede alguien ayudarme a entender lo que la clase de tipos Reduce está haciendo, cómo el trabajo (-<) y (>-) operadores, y lo que me informes sobre el código en el artículo (copiado abajo)?

---

Listado de Código de Finger Trees Done Right (I hope):

Listado 1: declaración de instancia para el nodo

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 

Listado 2: declaración de instancia para 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 (>-)) 

lista 3: Datos tipos

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

Dado que reduce es un nombre alternativo común para una función de "doblar", supongo que es algo similar a the Foldable type class. Las definiciones de instancias también parecen tener sentido como tales.

La clase Foldable se puede definir utilizando sólo foldr, que tiene el tipo de firma foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b, mientras que el reducer en ese código parece ser reducer :: (Reduce t) => (a -> b -> b) -> t a -> b -> b. Aparte de un orden de argumento diferente, debería funcionar igual.

Tenga en cuenta que los operadores son solo argumentos para la función; puede reemplazarlos todos con f u otro identificador genérico similar. Usar un operador como el nombre de un argumento de función binaria es ... una elección un tanto inusual, pero sí enfatiza algunos aspectos de la estructura del pliegue, supongo.

Answer 2

Se define en el documento vinculado en el artículo: 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)