不可变数据结构只是一个效率问题,如果它们不断变化,或者你以错误的方式构建它们.例如,在增长列表的末尾不断追加更多是二次的,而连接列表列表是线性的.如果你仔细想想,你通常可以以合理的方式建立你的结构,懒惰的评价是你的朋友 – 发出承诺解决问题并停止担忧.

盲目地尝试复制命令式算法可能是无效的,但是你的断言错误地认为函数式编程必须在这里渐近变坏.

案例研究：纯函数GEP：线性时间的Karva表示法

我会坚持你为GEP解析Karva表示法的案例研究. (
我在this answer中更充分地使用了这个解决方案.)

这是一个相当干净的纯功能解决方案.我将借此机会在此过程中删除一些好的一般递归方案.

码

(导入Data.Tree提供数据树a = Node {rootLabel :: a,subForest :: Forest a}其中类型Forest a = [Tree a].)

import Data.Tree
import Data.Tree.Pretty -- from the pretty-tree package for visualising trees

arity :: Char -> Int
arity c 
  | c `elem` "+*-/" = 2
  | c `elem` "Q" = 1
  | otherwise = 0

一个hylomorphism是一个变形现象(build up,unfoldr)和一个变形现象(combine,foldr)的组合.
这些术语在开创性的论文Functional Programming with Bananas,Lenses and Barbed wire中被引入FP社区.

我们将把水平拉出来(ana /展开)并将它们组合在一起(cata / fold).

hylomorphism :: b -> (a -> b -> b) -> (c -> (a,c)) -> (c -> Bool) -> c -> b
hylomorphism base combine pullout stop seed = hylo seed where
 hylo s | stop s = base
        | otherwise = combine new (hylo s') 
          where (new,s') = pullout s

为了提取一个级别,我们使用上一级别的总arity来找到拆分这个新级别的位置,并为下一次准备好的arnd传递：

pullLevel :: (Int,String) -> (String,(Int,String))
pullLevel (n,cs) = (level,(total,cs')) where
                   (level,cs') = splitAt n cs
                   total = sum $map arity level

要将级别(作为字符串)与下面的级别(已经是森林)组合,我们只需要提取每个角色所需的树的数量.

combineLevel :: String -> Forest Char -> Forest Char
combineLevel "" [] = []
combineLevel (c:cs) levelBelow = Node c subforest : combineLevel cs theRest 
      where (subforest,theRest) = splitAt (arity c) levelBelow

现在我们可以使用hylomorphism解析Karva.请注意,我们从字符串1之外的整个arity中播种它,因为根级别只有一个节点.相应地,我们将结果应用于结果以使该单例在hylomorphism之后退出.

karvaToTree :: String -> Tree Char
karvaToTree cs = let
  zero (n,_) = n == 0          
    in head $hylomorphism [] combineLevel pullLevel zero (1,cs)

线性时间

没有指数爆炸,也没有重复的O(log(n))查找或昂贵的修改,所以我们不应该遇到太多麻烦.

> arity是O(1)
> splitAt部分是O(部分)
> pullLevel(part,cs)是使用splitAt获取级别的O(部分),加上地图级别的O(部分),所以O(部分)
> combineLevel(c：cs)是splitAt的O(arity c),递归调用的O(sum $map arity cs)
> hylomorphism [] combineLevel pullLevel zero(1,cs)

>对每个级别进行pullLevel调用,因此总的pullLevel成本为O(总和部分)= O(n)
>对每个级别进行combineLevel调用,因此总的combineLevel成本为O(sum $map arity levels)= O(n),因为整个输入的总arity由n限制为有效字符串.
>使O(#levels)调用为零(即O(1)),#level由n绑定,因此也低于O(n)

因此karvaToTree在输入长度上是线性的.

我认为这使得你需要使用可变性来获得线性算法的断言.

演示

让我们看一下结果(因为Tree语法太多了,很难读出输出！).您必须使用cabal安装pretty-tree来获取Data.Tree.Pretty.

see :: Tree Char -> IO ()
see = putStrLn.drawVerticalTree.fmap (:"")

ghci> karvaToTree "Q/a*+b-cbabaccbac"
Node {rootLabel = 'Q',subForest = [Node {rootLabel = '/',subForest = [Node {rootLabel = 'a',subForest = []},Node {rootLabel = '*',subForest = [Node {rootLabel = '+',subForest = [Node {rootLabel = '-',subForest = [Node {rootLabel = 'b',Node {rootLabel = 'a',subForest = []}]},Node {rootLabel = 'c',Node {rootLabel = 'b',subForest = []}]}]}]}

ghci> see $karvaToTree "Q/a*+b-cbabaccbac"
      Q      
      |      
      /      
      |      
 ------      
/      \     
a      *     
       |     
       ----- 
      /     \
      +     b
      |      
     ----    
    /    \   
    -    c   
    |        
    --       
   /  \      
   b  a

与this tutorial where I found the example预期的输出相匹配：