haskell - 在 Haskell 中更惯用地从深度优先预购列表构建 BST

Question

This submission to Programming Praxis给出一个 O(n) 函数，该函数“撤消”二叉搜索树的前序遍历，将列表转换回树.提供缺失的数据声明:

data Tree a = Leaf | Branch {value::a, left::Tree a, right:: Tree a}                 deriving (Eq, Show)fromPreOrder :: Ord a => [a] -> Tree afromPreOrder [] = LeaffromPreOrder (a:as) = Branch a l (fromPreOrder bs)  where    (l,bs) = lessThan a aslessThan n [] = (Leaf,[])lessThan n all@(a:as)  | a >= n    = (Leaf,all)  | otherwise = (Branch a l r,cs)  where (l,bs) = lessThan a as        (r,cs) = lessThan n bs

很明显，在每个递归步骤中都会向树中添加一个构造函数，这是其效率的关键。

唯一的“问题”是列表是手动通过计算进行线程化的，这不是一种非常 haskell 式的方法，并且使得很难看出它实际上是在单线程中逐个元素地消耗的。方式。

我尝试使用状态单子(monad)(prettified on Codepad)来纠正这个问题:

import Control.Monad.Statedata Tree a = Leaf            | Branch {root::a, left::Tree a, right::Tree a}               deriving (Eq,Show)peek = State peek' where  peek' [] = (Nothing,[])  peek' a@(x:_) = (Just x,a) pop = State pop' where  pop' [] = error "Tried to read past the end of the list"  pop' (_:xs) = ((),xs)prebuild'::Ord a => State [a] (Tree a)prebuild' = do  next <- peek  case next of    Nothing -> return Leaf    Just x -> do                 pop                 leftpart <- lessThan x                 rightpart <- prebuild'                 return (Branch x leftpart rightpart) lessThan n = do  next <- peek  case next of    Nothing -> return Leaf    Just x -> do      if x < n      then do         pop         leftpart <- lessThan x         rightpart <- lessThan n         return (Branch x leftpart rightpart)      else         return Leafprebuild::Ord a => [a] -> Tree aprebuild = evalState prebuild'

不幸的是，这看起来非常困惑，而且似乎并不容易推理。

一个想法我还没有取得任何进展(部分原因是我对基本概念没有足够深入的理解，很可能):我可以在列表上使用左折叠来构建一个最终生成树的延续？这可能吗？另外，这会不会有点疯狂？

另一个想法是将其写为树展开，但我认为不可能有效地做到这一点；该列表最终会被遍历太多次，程序的复杂度将是 O(n^2)。

编辑

从另一个方向来看，我一直怀疑可能会想出一种算法，首先将列表分成递增段和递减段，但我还没有找到具体的方法有了这个想法。

Answer 1

我认为您在 State 方面遇到的问题是您的原语(push、pop、peek) 不是正确的。我认为更好的方法是 available_ ，它检查堆栈的前面是否匹配特定条件，并在每种情况下执行不同的操作:

available_ p f m = do
    s <- get
    case s of
        x:xs | p x -> put xs >> f x
        _ -> m

实际上，在我们的用例中，我们可以专门化一点:当堆栈的头部不满足条件时，我们总是希望返回一个Leaf，并且我们总是希望当它发生时递归。

available p m = available_ p
    (\x -> liftM2 (Branch x) (lessThan' x) m)
    (return Leaf)

(您也可以只写 available 开头，然后完全跳过 available_。在我的第一次迭代中，我就是这么做的。)现在写 fromPreOrder 和 lessThan 很简单，而且我认为可以深入了解它们的行为。我将用撇号来命名它们，这样我们就可以使用 QuickCheck 仔细检查它们是否做正确的事情。

fromPreOrder' = available (const True) fromPreOrder'
lessThan' n   = available (<n)         (lessThan' n)

在 ghci 中:

> quickCheck (\xs -> fromPreOrder (xs :: [Int]) == evalState fromPreOrder' xs)
+++ OK, passed 100 tests.