haskell - 从手指树文章中找到丢失的 'Reduce' 类型类

Question

昨天的Wikibender以 this stackoverflow qestion 开头的在 Comonads 上结束于 MarkCC's关于 Finger Trees 的文章.

在文章中，他广泛使用了 Reduce类型类。他写这个 typeclass 好像它是一个非常常见和经常使用的库，但我在 hackage 上找不到它，也找不到足够的文档来真正理解代码。

谁能帮我理解Reduce typeclass 是干什么的，(-<) 怎么样和 (>-)运算符(operator)工作，关于文章中的代码应该告诉我什么(复制如下)？

代码 list 来自 Finger Trees Done Right (I hope) :

list 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

list 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 (>-))

list 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 .实例定义似乎也很有意义。
Foldable类可以使用 foldr 来定义，其类型签名为 foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b ，而 reducer在该代码中似乎是 reducer :: (Reduce t) => (a -> b -> b) -> t a -> b -> b .除了不同的参数顺序之外，它应该工作相同。

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