フィンガーツリーから抜け落ちたタイプクラスを見つける記事

Question

Comonadsでthis stackoverflow qestionで始まるWikibenderがの記事Finger Treesで終了しました。

この記事では、Reduceタイプのクラスを広く使用しています。彼は非常に一般的で頻繁に使用されるライブラリであるかのようにこのtypeclassについて書いていますが、私はhackageでそれを見つけることはできませんし、コードを本当に理解するのに十分な文書を見つけることもできません。

誰かが私にReduce型クラスが何をしているのか、どのように(-<)と(>-)オペレーターの仕事を理解することができ、そして何が記事（以下コピー）内のコードを教えなければなりませんか？

---

コード表示Finger Trees Done Right (I hope)から：

リスト1：データ：2-3フィンガーツリー

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のインスタンス宣言：ノード

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のインスタンス宣言タイプ

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に似たものだと推測すると思います。インスタンス定義も同様に意味があるように見えます。そのコードにreducerはreducer :: (Reduce t) => (a -> b -> b) -> t a -> b -> bであるように見える一方

Foldable

クラスは、型シグネチャfoldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> bを有するだけfoldrを使用して定義することができます。別の引数の順序以外にも、同じように動作するはずです。

演算子は関数の単なる引数であり、すべてをfまたは同様の汎用識別子で置き換えることができます。バイナリ関数の引数の名前として演算子を使用するのは、やや珍しい選択ですが、折り返しの構造のいくつかの側面を強調しています。

Answer 2

記事にリンクされている論文には、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)