16

このSOの質問に関連するカタモルフィズムを理解することを楽しみにしています:)

Real World Haskell チュートリアルの最初の部分しか練習していません。だから、多分私は今あまりにも多くを求めるつもりです, もしそうなら, 私が学ぶべき概念を教えてください.

以下に、カタモルフィズムのウィキペディアのコード サンプルを引用します。

以下のfoldTree、ツリーをトラバースする方法、この他のSOの質問と回答と比較して、ツリーのn-aryツリートラバーサルをトラバースすることについてのあなたの意見を知りたいです。(バイナリかどうかは別として、以下のカタモルフィズムはn分木を扱うように書けると思います)

私が理解していることをコメントに入れました。修正していただけると幸いです。いくつかのことを明確にしてください。

{-this is a binary tree definition-}
data Tree a = Leaf a
            | Branch (Tree a) (Tree a)

{-I dont understand the structure between{} 
however it defines two morphisms, leaf and branch 
leaf take an a and returns an r, branch takes two r and returns an r-} 
data TreeAlgebra a r = TreeAlgebra { leaf   :: a      -> r
                                   , branch :: r -> r -> r }

{- foldTree is a morphism that takes: a TreeAlgebra for Tree a with result r, a Tree a
and returns an r -} 
foldTree :: TreeAlgebra a r -> Tree a -> r
foldTree a@(TreeAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldTree a@(TreeAlgebra {branch = g}) (Branch l r) = g (foldTree a l) (foldTree a r)

この時点で私は多くの困難を抱えています.射の葉はどの葉にも適用されると推測しているようですが,このコードを実際に使用するには,foldTreeに定義されたTreeAlgebra,定義された射の葉を持つTreeAlgebraを供給する必要があります.何かをするために？
しかし、この場合、foldTree コードでは {f = leaf} を期待し、その逆ではありません

あなたからの明確化は大歓迎です。

4

2 に答える 2

28

あなたが何を求めているのか正確にはわかりません。しかし、そうです、ツリーで実行したい計算に対応する toTreeAlgebraをフィードします。foldTreeたとえば、Ints の木のすべての要素を合計するには、次の代数を使用します。

sumAlgebra :: TreeAlgebra Int Int
sumAlgebra = TreeAlgebra { leaf = id
                         , branch = (+) }

つまり、リーフの合計を取得するには、リーフidの値に適用 (何もしない) します。ブランチの合計を取得するには、各子の合計を合計します。

(+)たとえば、ではなく枝について言えるという事実\x y -> sumTree x + sumTree yは、カタモルフィズムの本質的な特性です。再帰的なデータ構造で関数を計算するには、直接の子fの値があれば十分です。f

Haskell は、カタモルフィズムのアイデアを抽象的に形式化できるという点で、非常にユニークな言語です。子に対してパラメータ化された、ツリー内の単一ノードのデータ型を作成しましょう。

data TreeNode a child
    = Leaf a
    | Branch child child

私たちがそこで何をしたか見てください。再帰的な子を選択したタイプに置き換えただけです。これは、折りたたみ時にサブツリーの合計をそこに配置できるようにするためです。

さて、本当に魔法のことです。これを疑似Haskellで書くつもりです - 実際のHaskellで書くことは可能ですが、タイプチェッカーを助けるためにいくつかの注釈を追加する必要があり、混乱を招く可能性があります. Tパラメータ化されたデータ型の「固定小数点」を取ります。つまり、 のようなデータ型を構築しますT = TreeNode a T。彼らはこれを operator と呼んでいますMu。

type Mu f = f (Mu f)

ここをよく見てください。への引数は、やMuのような型ではありません。orのような型コンストラクタです--それ自体への引数は引数を取ります。(型コンストラクターを抽象化できる可能性は、Haskell の型システムの表現力を本当に際立たせるものの 1 つです)。IntFoo -> BarMaybeTreeNode IntMu

したがって、型Mu fは、その型パラメーターを取り、それ自体fで埋めるものとして定義されMu fます。ノイズの一部を減らすために同義語を定義します。

type IntNode = TreeNode Int

を展開するMu IntNodeと、次のようになります。

Mu IntNode = IntNode (Mu IntNode)
           = Leaf Int | Branch (Mu IntNode) (Mu IntNode)

があなたの とどのようMu IntNodeに等しいか分かりますTree Intか? 再帰構造をばらばらにしてMuから、元に戻しました。Muこれにより、すべてのタイプについて一度に話すことができるという利点が得られます。これにより、カタモルフィズムを定義するために必要なものが得られます。

定義しましょう:

type IntTree = Mu IntNode

カタモルフィズムの本質的な特性は、何らかの関数 を計算するには、直接の子fの値があれば十分であると述べましたf。計算しようとしているものの型とrデータ構造を呼び出しましょうnode(IntNodeこれのインスタンス化の可能性があります)。したがって、特定のノードで計算するrには、その子を に置き換えたノードが必要rです。この計算の型はnode r -> rです。したがって、カタモルフィズムは、これらの計算の 1 つがあれば、再帰r構造全体を計算できることを示しています (再帰はここで で明示的に示されていることを思い出してください)。Mu

cata :: (node r -> r) -> Mu node -> r

この例を具体的にすると、次のようになります。

cata :: (IntNode r -> r) -> IntTree -> r

r言い換えると、子に s を持つノードを取得して を計算できれば、ツリー全体の をr計算できます。r

これを実際に計算するには、ノードの子に対して任意の関数をマップできる必要がありますnode。Functor

fmap :: (a -> b) -> node a -> node b

これは、 に対して簡単に実行できますIntNode。

fmap f (Leaf x) = Leaf x                  -- has no children, so stays the same
fmap f (Branch l r) = Branch (f l) (f r)  -- apply function to each child

さて、最後に、 の定義を与えることができますcata (制約は、 が適切な を持っているFunctor nodeと言っているだけです):nodefmap

cata :: (Functor node) => (node r -> r) -> Mu node -> r
cata f t = f (fmap (cata f) t)

t「tree」のニーモニック値にパラメーター名を使用しました。これは抽象的で緻密な定義ですが、実際には非常に単純です。再帰的に実行cata f- ツリーに対して行っている計算 -tの子 (それ自体がMu nodes) のそれぞれに対して を取得しnode r、その結果を渡してそれ自体fの結果を計算しtます。

node r -> rこれを最初に結び付けると、定義している代数は本質的にその関数を定義する方法です。実際、 が与えられるとTreeAlgebra、fold 関数を簡単に取得できます。

foldFunction :: TreeAlgebra a r -> (TreeNode a r -> r)
foldFunction alg (Leaf a) = leaf alg a
foldFunction alg (Branch l r) = branch alg l r

したがって、ツリーのカタモルフィズムは、次のように一般的なものの観点から定義できます。

type Tree a = Mu (TreeNode a)

treeCata :: TreeAlgebra a r -> (Tree a -> r)
treeCata alg = cata (foldFunction alg)

時間がありません。非常に急速に抽象化されたことは承知していますが、少なくとも学習に役立つ新しい視点が得られたことを願っています. 幸運を！

于 2010-12-14T01:32:30.863 に答える
4

{} について質問していたと思います。{} について詳しく説明した以前の質問があります。これらはHaskell のレコード構文と呼ばれます。もう 1 つの問題は、代数を構成する理由です。これは、データを関数として一般化する典型的な関数パラダイムです。

最も有名な例は、Church の Naturals の構築であり、ここf = + 1でz = 0、 0 = z、 1 = f z、 2 = f (f z)、 3 = f (f (f z))など...

あなたが見ているのは、基本的に同じアイデアがツリーに適用されていることです。教会の例で作業すると、ツリーがクリックされます。

于 2010-12-15T05:31:10.500 に答える