algorithm - 我是否可以始终将仅可变算法转换为单赋值并且仍然有效？

Question

上下文

这个问题的上下文是我想玩 Gene Expression Programming (GEP)，一种进化算法，使用 Erlang . GEP 使用称为“Karva 符号”的基于字符串的 DSL。 Karva notation很容易翻译成表达式解析树，但翻译算法假设了一个具有可变对象的实现:不完整的子表达式在翻译过程的早期创建，它们自己的子表达式稍后用未知的值填充在它们被创建的时候。

Karva 表示法的目的是保证在没有任何昂贵的编码技术或遗传密码更正的情况下创建语法正确的表达式。问题是，对于像 Erlang 这样的单赋值编程语言，我必须recreate随着每个子表达式被填充，表达式树不断地被填充。这需要一个廉价的 - O(n)？ - 更新操作并将其转换为可以在指数时间内完成的操作(除非我弄错了)。如果我找不到一种有效的函数算法来将 K 表达式转换为表达式树，那么 GEP 的一个引人注目的特性就会丢失。

问题

我很欣赏 K 表达式翻译问题非常模糊，所以我想要的是关于如何将固有非功能性算法(利用可变数据结构的 alg)转换为不具有功能性的算法的建议。纯函数式编程语言如何适应计算机科学早期产生的许多算法和数据结构，这些算法和数据结构依赖于可变性以获得所需的性能特征？

Answer 1

精心设计的不变性避免不必要的更新

如果不可变数据结构不断变化，或者您以错误的方式构建它们，那么它们只会是一个效率问题。例如，在不断增长的列表的末尾连续追加更多是二次的，而连接列表的列表是线性的。如果您仔细考虑，通常可以以合理的方式构建您的结构，而懒惰的评估是您的 friend - promise 解决它并停止担心。

盲目地尝试复制命令式算法可能是低效的，但是您断言函数式编程在这里必须是渐进式的，这是错误的。

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

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

这是该问题的一个相当干净的纯函数式解决方案。在此过程中，我将借此机会列举一些优秀的通用递归方案。

代码

(导入 Data.Tree 用品 data Tree a = Node {rootLabel :: a, subForest :: Forest a} 其中 type 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 是 anamorphism (build up, expandr) 和 catamorphism (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

为了拉出一个级别，我们使用前一级别的总数量来找到从哪里拆分这个新级别，并为下一次准备好这个级别的总数量:

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 的字符串外部为它播种了总数量。 ，因为在根级别只有一个节点。对应我们申请head结果是在 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 part是 O( part )

pullLevel (part,cs)是 O( part ) 使用 splitAt 抓取获取 level , 加上 O( part ) 为 map arity level ，所以 O( part )

combineLevel (c:cs)对于 arity c 是 O( splitAt ) , 和 O( sum $ map arity cs ) 用于递归调用

hylomorphism [] combineLevel pullLevel zero (1,cs)

制作 pullLevel每个级别的调用，所以总pullLevel成本是 O( sum 份数) = O(n)

制作 combineLevel每个级别的调用，所以总combineLevel成本是 O(sum $ map arity levels) = O(n)，因为对于有效字符串，整个输入的总数量受 n 的约束。

对 zero 进行 O(#levels) 次调用(即 O( 1 ))和 #levels受 n 约束，所以它也低于 O(n)

因此 karvaToTree在输入的长度上是线性的。
我认为这使您需要使用可变性来获得线性算法的断言搁置。

演示

让我们来看看结果(因为 Tree 的语法太丰富了，很难阅读输出!)。你必须cabal install 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', subForest = []},Node {rootLabel = 'a', subForest = []}]},Node {rootLabel = 'c', subForest = []}]},Node {rootLabel = 'b', subForest = []}]}]}]}

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

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