Haskell - 二進制搜索樹

Question

作爲Haskell的初學者，我目前正試圖讓我的頭繞BST。目前我正在嘗試在樹上進行摺疊。

這是我到目前爲止，但它會產生一個錯誤。

inorder' :: (b -> a -> b) -> b -> BinaryTree a -> b 
inorder' _ a myTree = a 
inorder' fun a (Node left root right) = inorder' fun (fun root (inorder' fun a left)) right 

我現在真的很傻眼了，因爲我工作了很長一段時間我們弄清楚到底是什麼問題，但我似乎根本就沒有拿出一個解決方案。

Answer 1

Inorder意味着你（1）首先處理左子樹，（2）然後處理節點本身，以及（3）最後處理右子樹。

葉沒有價值

根據您的功能，BinaryTree a定義，大概是：

data BinaryTree a = Leaf | Node (BinaryTree a) a (BinaryTree a) 

因此，這意味着，有兩種情況：在葉的情況下，沒有數據，所以我們簡單地返回給定值：

inorder' _ a Leaf = a -- with an uppercase, otherwise it does match all 

而對於Node情況下，我們在上面已經指出，如何工作的：

inorder' f a (Node left val right) = inorder' f c right 
    where b = inorder' f a left 
      c = f b val

或全部：

inorder' :: (b -> a -> b) -> b -> BinaryTree a -> b 
inorder' _ a Leaf = a 
inorder' f a (Node left val right) = inorder' f c right 
    where b = inorder' f a left 
      c = f b val 

葉值

在這種情況下，BinaryTree的定義如下：

data BinaryTree a = Leaf a | Node (BinaryTree a) a (BinaryTree a) 

如果葉子有一個值，我們只需要修正第一個子句：

inorder' :: (b -> a -> b) -> b -> BinaryTree a -> b 
inorder' f b (Leaf a) = f b a 
inorder' f a (Node left val right) = inorder' f c right 
    where b = inorder' f a left 
      c = f b val