9

Comonadsでのこのstackoverflowqestionで始まった昨日のWikibenderは、FingerTreesに関するMarkCCの記事に行き着きました。

Reduceこの記事では、彼は型クラスを多用しています。彼はこの型クラスについて、非常に一般的で頻繁に使用されるライブラリであるかのように書いていますが、ハッキングでは見つけることができず、コードを実際に理解するのに十分なドキュメントも見つかりません。

Reduce誰かが型クラスが何をしているのか、演算子(-<)と演算子がどのように機能するのか、そして(>-)記事（以下にコピー）のコードについて何を教えてくれるのかを理解するのを手伝ってもらえますか？

正しく行われたフィンガーツリーからのコードリスト（私は願っています） ：

リスト1：ノードのインスタンス宣言

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

これが「fold」関数の一般的な別名であることを考えると、型クラスreduceに似ていると思います。インスタンス定義もそのように意味があるようです。Foldable

クラスは、型シグネチャを持つFoldablejustを使用して定義できますが、そのコードでははのように見えます。引数の順序が異なることを除けば、同じように機能するはずです。foldrfoldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> breducerreducer :: (Reduce t) => (a -> b -> b) -> t a -> b -> b

f演算子は関数への単なる引数であることに注意してください。これらすべてを、または別の同様に一般的な識別子に置き換えることができます。二変数引数の名前として演算子を使用することは...少し珍しい選択ですが、それはフォールドの構造のいくつかの側面を強調していると思います。

于 2011-12-09T19:13:06.617 に答える
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 に答える