haskell - 在Haskell中使用尾递归拆分BinTree

因此，本周我们了解了Haskell中的联合类型，尾递归和二叉树。我们这样定义树数据类型：

data BinTree a = Empty
           | Node (BinTree a) a (BinTree a)
           deriving (Eq, Show)

leaf :: a -> BinTree a
leaf x = Node Empty x Empty

现在，我们被要求编写一个函数以找到最左边的节点，将其返回，将其剪切掉，还返回没有我们刚刚剪切的节点的其余树。

我们做了这样的事情，效果很好：

splitleftmost :: BinTree a -> Maybe (a, BinTree a)
splitleftmost Empty = Nothing
splitleftmost (Node l a r) = case splitleftmost l of
                                 Nothing -> Just (a, r)
                                 Just (a',l') -> Just (a', Node l' a r)

现在，我需要使该函数尾部递归。我想我了解尾递归的含义，但是发现很难将其应用于此问题。有人告诉我编写一个函数，该函数使用合适的参数调用主函数，但仍然无法解决该问题。

最佳答案

由于节点没有父链接，因此一种方法是在列表中维护根到叶的路径。最后，可以使用左折构造修改后的树：

slm :: BinTree a -> Maybe (a, BinTree a)
slm = run []
    where
    run _ Empty = Nothing
    run t (Node Empty x r) = Just (x, foldl go r t)
        where go l (Node _ x r) = Node l x r

    run t n@(Node l _ _) = run (n:t) l