Catamorphism和樹遍歷哈斯克爾

Question

我不耐煩了，期待了解catamorphism related to this SO question :)

我只練真實世界哈斯克爾教程的開始。所以，也許我現在要問的方式太多了，如果是這樣的話，只要告訴我我應該學習的概念。我的報價爲wikipedia code sample for catamorphism。

我想知道你對下面的foldTree的看法，這是一種遍歷Tree的方法，與其他SO的問題和答案相比，還處理遍歷樹n-ary tree traversal。 （獨立於二進制或不是，我認爲下面的變形可以編寫以便管理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需要反饋定義TreeAlgebra ， 一個TreeAlgebra具有一個定義的態射葉以做某事？
但在這種情況下，摺疊我希望{f =葉}而不是相反的代碼

任何澄清從你會非常歡迎。

Answer 1

不完全確定你在問什麼。但是，是的，你提供TreeAlgebra到foldTree對應於你想在樹上執行的計算。例如，要總結在樹中的所有元素的Int是你可以使用這個代數：

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 

見我們去做什麼了？我們用我們選擇的類型替換了遞歸子代。這樣我們可以在摺疊時將子樹的總和放在那裏。

現在的真正神奇的事情。我將在pseudohaskell中編寫它 - 將它編寫成真正的Haskell是可能的，但我們必須添加一些註釋來幫助類型分析器，這可能會讓人困惑。我們採用參數化數據類型的「固定點」 - 也就是構造一個數據類型T，例如T = TreeNode a T。他們稱這個運營商爲Mu。

type Mu f = f (Mu f) 

請仔細看看這裏。 Mu的參數不是類型，如Int或Foo -> Bar。這是一個類型構造函數像Maybe或TreeNode Int - Mu本身的參數需要一個參數。 （對類型構造函數進行抽象化的可能性是Haskell的類型系統在其表現力上真正脫穎而出的原因之一）。

所以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 

我說catamorphism的本質屬性是計算一些功能f，只須有f的值，它的直接孩子。我們稱之爲我們試圖計算的東西的類型r，並且數據結構node（IntNode將是這種可能的實例）。因此，要計算特定節點上的r，我們需要將其子節點替換爲r的節點。該計算的類型爲node r -> r。因此，一個catamorphism說，如果我們有這些計算中的一個，那麼我們可以計算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約束只是說，node具有合適的fmap）：

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

我使用的參數名稱t用於助記符「樹」的價值。這是一個抽象的，密集的定義，但它非常簡單。它說：遞歸地執行cata f - 我們在樹上進行的計算 - 在t的每個孩子（它們本身Mu node s）上得到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 

因此樹catamorphism可以在我們的一個通用的術語來定義如下：

type Tree a = Mu (TreeNode a) 

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

我出來的時候。我知道真的很抽象，但我希望它至少能給你一個新的觀點來幫助你學習。祝你好運！

Answer 2

我想你是在問一個關於{}的問題。對{}的討論有一個較早的問題。這些被稱爲Haskell's record syntax。另一個問題是爲什麼要構建代數。這是一個典型的函數範例，將數據概括爲函數。

最著名的例子是Church's construction of the Naturals，其中f = + 1和z = 0， 0 = z， 1 = f z， 2 = f (f z)， 3 = f (f (f z))， 等等

你們看到的基本上是被應用到同樣的想法樹。工作教堂的例子，樹會點擊。