我是否可以始终将仅可变算法转换为单一分配并仍然有效？

Question

上下文

这个问题的背景是我想要使用基因表达式编程(GEP),这是一种使用Erlang的进化算法.GEP使用基于字符串的DSL称为" Karva表示法 ".Karva表示法很容易翻译成表达式解析树,但是翻译算法假定一个实现具有可变对象:在翻译过程的早期创建不完整的子表达式,并且他们自己的子表达式随后用值填充.在他们被创建时不知道.

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

问题

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

Answer 1

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

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

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

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

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

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

码

(导入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是一个变形(建立,展开)和一个变形(组合,折叠)的组成.这些术语在开创性的香蕉,镜片和带刺铁丝网功能编程中引入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.请注意,我们使用字符串外部的总arity来播种它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)是part使用splitAt获取的levelO(part),加上O()map arity level,所以O(part)
• combineLevel (c:cs)为O( arity c)的splitAt,和O( sum $ map arity cs),用于递归调用

• hylomorphism [] combineLevel pullLevel zero (1,cs)

  • 使得pullLevel对于每个电平的呼叫,所以总pullLevel成本是O(sum份)= O(n)的
  • 使得combineLevel对于每个电平的呼叫,所以总combineLevel成本是O(sum $ map arity水平)= O(n)的,由于整个输入的总元数为n为有效字符串约束.
  • 使O(#levels)调用zero(即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  

它匹配本教程中预期的输出,我在其中找到了示例:

Answer 2

当函数式编程中需要可变状态时，有几种解决方案。

1. 使用不同的算法来解决相同的问题。例如，快速排序通常被认为是可变的，因此在功能设置中可能不太有用，但合并排序通常更适合功能设置。我无法判断这个选项是否可行或对您的情况是否有意义。

2. 即使是函数式编程语言通常也提供某种改变状态的方法。（这篇博文似乎展示了如何在 Erlang 中做到这一点。）对于某些算法和数据结构，这确实是唯一可用的选项（我认为，关于该主题的研究正在进行中）；例如，函数式编程语言中的哈希表通常是用可变状态来实现的。

就您而言，我不太确定不变性是否真的会导致性能瓶颈。你是对的，（子）树将在更新时重新创建，但 Erlang 实现可能会重用所有未更改的子树，导致每次更新的复杂度为 O(log n)，而不是可变状态的 O(1) 。此外，不会复制树的节点，而是复制对节点的引用，这应该相对有效。您可以在冈崎的论文或他基于该论文的书“纯函数数据结构”中阅读有关功能设置中的树更新的内容。我会尝试使用不可变的数据结构来实现该算法，如果遇到性能问题，则切换到可变的数据结构。

另请参阅此处和此处的一些相关 SO 问题。