9

昨天的Wikibender以这个关于 Comonads 的 stackoverflow 问题开始，最终出现在MarkCC关于手指树的文章中。

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

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

正确完成手指树的代码清单（我希望）：

清单 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 ]
4

2 回答 2

6

它在文章链接的论文中定义：手指树：一种简单的通用数据结构。

class Reduce f where
  reducer :: (a -> b -> b) -> (f a -> b -> b)
  reducel :: (b -> a -> b) -> (b -> f a -> b)
于 2011-12-09T19:18:37.447 回答
6

鉴于这是“折叠”函数的reduce常见替代名称，我猜它类似于类型 class。实例定义似乎也很有意义。Foldable

Foldable可以使用 just 定义该类，foldr它具有类型签名foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b，而reducer在该代码中似乎是reducer :: (Reduce t) => (a -> b -> b) -> t a -> b -> b。除了不同的参数顺序之外，它应该工作相同。

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

于 2011-12-09T19:13:06.617 回答