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