2

Data.Tree.Zipper では、バラの木のジッパーのデータ型は次のとおりです。

data TreePos t a  = Loc
  { _content   :: t a        -- ^ The currently selected tree.
  , _before    :: Forest a
  , _after     :: Forest a
  , _parents   :: [(Forest a, a, Forest a)]
  } deriving (Read,Show,Eq)

_after と _before の情報は、_parents フィールドにも表示されるはずなので、冗長であるように思えます。(ノードの兄弟は、その親の子です。)

どうしてこれなの？都合上？

4

2 に答える 2

0

とても丁寧な説明ありがとうございます！

私が混乱した理由は、バラの木のデータ型を取ると

data Rose x = Rose x [Rose x]

そして微分を取る

R = x L(R(x))
R' = L(R) + x L' R'
R' = L(R) / (1 - x L')
R' = L(R) / (1 - x L^2)
R' = L(R) * L(x L^2)

これは、ジッパーの次のデータ型に直接変換されます

data TreePos t a  = Loc
  { _content   :: t a        -- ^ The currently selected tree.
  , _parents'  :: [(Forest a, a, Forest a)]
  } deriving (Read,Show,Eq)

この場合、最初の要素_parents'は、フォーカスされたノードの兄弟に関する情報を保持します。
明らかに、両方のバージョンが同等である必要があります。_parents私は不注意にそれを仮定しただけで_parents'、まったく同じ情報を保持していました。ただし、Data.Tree.Zipper の実装には小さな「欠点」が 1 つあります。私が見る限り、最後の要素には_parents常に 2 つの空のリストが含まれているため、まだ冗長な情報が含まれています :-)

于 2014-03-18T09:44:41.523 に答える