从手指树文章中找到丢失'减少'类型类

Question

昨天的Wikibender以Comonads上的stackoverflow问题开始,最终出现在MarkCC关于Finger Trees 的文章中.

在文章中,他广泛使用了Reduce类型类.他写了关于这个类型类的文章,好像它是一个非常常见且经常使用的库,但我无法在hackage上找到它,也无法找到足够的文档来真正理解代码.

有人可以帮助我理解Reduce类型类正在做什么,(-<)和(>-)运算符如何工作,以及应该告诉我文章中的代码(下面复制)？

---

从手指树完成的代码清单(我希望):

清单1: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

清单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是一个"折叠"功能的通用替代名称,我猜想,这是类似的东西的Foldable类型类.实例定义似乎也是有意义的.

的Foldable类可以仅使用被定义foldr,它具有式签名foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b,而reducer在该代码看起来是reducer :: (Reduce t) => (a -> b -> b) -> t a -> b -> b.除了不同的参数顺序,它应该工作相同.

请注意,运算符只是函数的参数 - 您可以将它们全部替换为f另一个类似的通用标识符.使用运算符作为二元函数参数的名称是一个稍微不寻常的选择,但它确实强调了折叠结构的某些方面,我猜.

Answer 2

它在文章中链接的文章中定义:手指树:简单的通用数据结构.

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