查找Haskell樹中節點的值

Question

我目前正在搞亂一些Haskell樹。我是Haskell（來自C）的新手，想知道如何從樹中找到Node的個人價值（我一直在呼籲葉子）。 如果我的樹說： （根）的功率，（branchLeft）2，（branchRight）3

如果我想讀此爲2〜三方面的力量，我應該怎麼去呢？ 我從頭開始，在過去的3個小時裏一直在用代碼搞亂，而且還沒有很遠。

任何提示/想法？

Answer 1

可以將二進制樹的二進制運算符在使用代數數據類型內的節點型號：

data Tree a = Leaf a | InnerNode (a -> a -> a) (Tree a) (Tree a) 

功能a -> a -> a是二進制運算符。例如，整數的簡單的樹可以被定義爲

tree :: Tree Integer 
tree = InnerNode (+) (InnerNode (^) (Leaf 3) (Leaf 2)) (Leaf 5) 

評估或解釋樹在你描述你可以寫一個函數

interpretTree :: Tree Integer -> Integer 

要編寫函數的方式，你可能會想要使用模式匹配和遞歸：

interpretTree (Leaf x) = x   -- the base case 
interpretTree (InnerNode f l r) = ... -- use recursion here 

對於第二種情況，您可以遞歸計算子樹並使用函數f將它們組合起來。

Answer 2

我將定義沿着你所提到的線的數據類型：

data Tree2 b a = Leaf a | Node b (Tree2 b a) (Tree2 b a) 
    deriving Show 

，所以我就可以使用

example :: Tree2 (Integer -> Integer -> Integer) Integer 
example = Node (^) (Leaf 2) (Leaf 3) 

最普遍的摺疊功能（「catamorphism」）你可以在此類型上使用函數（foldLeaf，foldNode）代替每個構造函數（Leaf,Node）遞歸的結構：

foldTree2 :: (a -> v) -> (b -> v -> v -> v) -> Tree2 b a -> v 
foldTree2 foldLeaf foldNode = fold where 
    fold (Leaf a) = foldLeaf a 
    fold (Node b left right) 
       = foldNode b (fold left) (fold right) 

所以我們應該能夠定義大量的使用這種功能，但特別是，你正在尋求的評價函數

inOrderApply :: Tree2 (a -> a -> a) a -> a 
inOrderApply = foldTree2 id id 

ghci> inOrderApply example 
8 
ghci> inOrderApply (Node (+) (Node (-) (Leaf 10) (Leaf 5)) (Node (*) (Leaf 3) (Leaf 2))) 
11