ハスケルでのカタモルフィズムと樹木

StackOverflow https://stackoverflow.com/questions/4434292

質問

私は焦り、カタルフィズムを理解するのを楽しみにしています これに関連しているので、質問 :)

私は現実世界のHaskellチュートリアルの始まりのみを練習しました。だから、たぶん私は今、あまりにも多くの方法を尋ねるつもりです。もしそうなら、私が学ぶべき概念を教えてください。

以下では、引用します カタルフィズムのウィキペディアコードサンプル.

この他の質問と答えと比較して、木を横断する方法であるFoldtreeについてのあなたの意見を知りたいと思います。 n-アリーツリートラバーサル. 。 （バイナリであるかどうかとは独立して、以下のカタルフィズムはn-aryツリーを管理するために書くことができると思います）

私は私が理解していることをコメントし、あなたが私を修正して、いくつかのことを明確にすることができれば嬉しいです。

{-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は定義されたモルフィズム葉を持つトレアリアブラである定義されたトレアルギブラに供給する必要があります何かをするために？
しかし、この場合、foldtreeコードの場合、{f = leaf}を期待しますが、逆ではありません

あなたからの明確化は本当に歓迎されます。

役に立ちましたか？

解決

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

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

つまり、葉の合計を取得するには、適用してください id （何もしない）葉の価値に。ブランチの合計を取得するには、 合計 それぞれの子供の。

私たちが言うことができるという事実 (+) たとえば、枝の代わりに \x y -> sumTree x + sumTree y カタモルフィアの本質的な特性です。何らかの関数を計算するためにそれが言っています f いくつかの再帰データ構造では、 f その直接の子供たちのために。

Haskellは、Catamorphismのアイデアを抽象的に形式化できるという点で、非常にユニークな言語です。ツリー内の単一のノードのデータ型を作成しましょう。

data TreeNode a child
    = Leaf a
    | Branch child child

私たちがそこで何をしたかわかりますか？再帰的な子供たちを選択したタイプに置き換えました。これは、折り畳んでいるときにサブツリーの合計をそこに置くことができるようにするためです。

今、本当に魔法のようなことのために。私はこれをPseudohaskellで書くつもりです - 実際のHaskellでそれを書くことは可能ですが、私たちは混乱することができるTypeCheckerを助けるためにいくつかの注釈を追加する必要があります。パラメーター化されたデータ型の「固定点」、つまりデータ型の構築を取得します T そのような T = TreeNode a T. 。彼らはこのオペレーターを呼び出します Mu.

type Mu f = f (Mu f)

ここを注意深く見てください。への議論 Mu のようなタイプではありません Int また Foo -> Bar. 。それはタイプです コンストラクタ お気に入り Maybe また TreeNode Int - への議論 Mu それ自体が議論をします。 （タイプのコンストラクターを抽象化する可能性は、Haskellのタイプシステムを表現力のある力で本当に際立たせるものの1つです）。

だからタイプ 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 特定のノードでは、子供を置き換えるノードが必要です rs。この計算にはタイプがあります node r -> r. 。したがって、カタモーフィズムは、これらの計算のいずれかがある場合、計算できると言います r 全体で 再帰 構造（再帰はここで明示的に示されていることを忘れないでください Mu):

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

私たちの例のためにこの具体を作ると、これは次のように見えます。

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

再検討して、ノードを使用できれば rs子供のためにsとcompute an r, 、その後、ANを計算できます 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 制約はそれを言うだけです node 適切なものがあります fmap):

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

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

これを最初に戻すと、あなたが定義している代数は本質的にそれを定義する方法です node r -> r 働き。確かに、 TreeAlgebra, 、折り畳み関数を簡単に取得できます。

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)

私は時間外です。それは本当に速く抽象化したことを知っていますが、少なくともあなたの学習を助けるための新しい視点を与えてくれることを願っています。幸運を！

他のヒント

あなたは{}について質問していたと思います。 {}の良い議論を伴う以前の質問があります。それらは呼ばれます Haskellのレコード構文. 。もう1つの質問は、なぜ代数を構築するのかです。これは、データとしてデータを一般化する典型的な関数パラダイムです。

最も有名な例はです 教会の自然の建設, 、 どこ f = + 1 と z = 0, 0 = z, 1 = f z, 2 = f (f z), 3 = f (f (f z))、など...

あなたが見ているのは、本質的に木に適用されているのと同じアイデアです。教会の例を操作すると、木がクリックします。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top