更确切地说,从Haskell中的深度优先预订单列表构建BST

对Praxis编程的这一提交给出了一个O(n)函数,它"撤消"二进制搜索树的前序遍历,将列表转换回树.提供缺失的数据声明:

data Tree a = Leaf | Branch {value::a, left::Tree a, right:: Tree a}
                 deriving (Eq, Show)

fromPreOrder :: Ord a => [a] -> Tree a
fromPreOrder [] = Leaf
fromPreOrder (a:as) = Branch a l (fromPreOrder bs)
  where
    (l,bs) = lessThan a as

lessThan 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

很明显,在每个递归步骤中将一个构造函数添加到树中,这是其效率的关键.

唯一的"问题"是列表是手动穿过计算的,这不是一种非常糟糕的Haskellian方式,并且使得它更难以看到它实际上是以单线程方式逐个元素地消耗.

我尝试使用状态monad(在Codepad上进行了修饰)来纠正这个问题:

import Control.Monad.State

data 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 Leaf

prebuild::Ord a => [a] -> Tree a
prebuild = evalState prebuild'

不幸的是,这只是看起来很混乱,似乎没有任何理由更容易理解.

有人认为我还没有能够到达任何地方(部分原因是因为我对底层概念的理解不够深刻):我是否可以在列表上使用左侧折叠来构建最终的延续生产树？这可能吗？还有什么不是疯了吗？

另一个想法是把它写成一棵树展开,但我认为不可能有效地做到这一点; 列表最终将被遍历太多次,程序将为O(n ^ 2).

编辑

从另一个方向拿东西,我有一种唠叨的怀疑,即有可能提出一种算法,该算法首先将列表分成增加的段并减少段,但我还没有找到与该想法具体相关的东西.