8

上下文

这个问题的背景是我想玩基因表达编程（GEP），一种进化算法的形式，使用Erlang。GEP 使用基于字符串的 DSL，称为“ Karva notation ”。Karva 表示法很容易翻译成表达式解析树，但翻译算法假设实现具有可变对象：不完整的子表达式在翻译过程的早期创建，并且它们自己的子表达式稍后用原来的值填充在创建它们时未知。

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

问题

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

4

4 回答 4

9

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

不可变的数据结构只有在不断变化，或者你以错误的方式构建它们时才会成为效率问题。例如，在不断增长的列表末尾不断追加更多内容是二次的，而连接列表列表是线性的。如果您仔细考虑，您通常可以以一种明智的方式构建您的结构，而懒惰的评估是您的朋友 - 承诺解决它并停止担心。

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

案例研究：纯函数 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 是变形（build up，展开）和 catamorphism（combine，foldr）的组合。这些术语在开创性论文Functional Programming with Bananas, Lenses and Barbed wire中介绍给 FP 社区。

我们将拉出关卡（ana/unfold）并将它们重新组合在一起（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结果应用到类同态之后让这个单例退出。

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)是 O( arity c) splitAt，而sum $ map arity cs递归调用 是 O( )

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

    • 对每个级别进行pullLevel调用，因此总pullLevel成本为 O( sumparts) = O(n)
    • 对每个级别进行combineLevel调用，因此总combineLevel成本为 O( sum $ map aritylevels) = O(n)，因为对于有效字符串，整个输入的总元数受 n 约束。
    • zero对(O( ))进行 O(#levels) 调用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

这与本教程的预期输出相匹配，我在其中找到了示例：

http://www.gepsoft.com/gxpt4kb/Chapter06/section3/pt02.gif

于 2014-02-23T02:20:38.983 回答
3

没有单一的方法可以做到这一点，它确实必须逐案尝试。我通常会尝试使用折叠和展开将它们分解为更简单的操作，然后从那里进行优化。正如其他人所指出的，Karva 解码案例是广度优先树展开，所以我从 treeUnfoldM_BF 开始。也许 Erlang 中也有类似的功能。

如果解码操作过于昂贵，您可以记住解码并共享/重用子树......尽管它可能不适合通用树展开器，您需要编写专门的函数来这样做。如果适应度函数足够慢，则可以使用像我在下面列出的那样简单的解码器。它将在每次调用时完全重建树。

import Control.Monad.State.Lazy
import Data.Tree

type MaxArity = Int
type NodeType = Char

treeify :: MaxArity -> [Char] -> Tree NodeType
treeify maxArity (x:xs) = evalState (unfoldTreeM_BF (step maxArity) x) xs
treeify _ [] = fail "empty list"

step :: MaxArity -> NodeType -> State [Char] (NodeType, [NodeType])
step maxArity node = do
  xs <- get
  -- figure out the actual child node count and use it instead of maxArity
  let (children, ys) = splitAt maxArity xs
  put ys
  return (node, children)

main :: IO ()
main = do
 let x = treeify 3 "0138513580135135135"
 putStr $ drawTree . fmap (:[]) $ x
 return ()
于 2011-08-06T00:31:08.047 回答
2

我想我想出了如何用 K 树解决您的特定问题（一般问题太难了：P）。我的解决方案以某种可怕的类似 Python 的伪代码（我今天的 FP 速度很慢）呈现，但在创建节点后它不会更改节点（诀窍是自下而上构建树）

首先，我们需要找出哪些节点属于哪个级别：

levels currsize nodes = 
    this_level , rest = take currsize from nodes, whats left
    next_size = sum of the arities of the nodes
    return [this_level | levels next_size rest]
(initial currsize is 1)

因此，在+/*abcd示例中，这应该给您[+, /*, abcd]. 现在您可以将其转换为自下而上的树：

curr_trees = last level
for level in reverse(levels except the last)
    next_trees = []
    for root in level:
        n = arity of root
        trees, curr_trees = take n from curr_trees, whats left
        next_trees.append( Node(root, trees) )
    curr_trees = next_trees

curr_trees should be a list with the single root node now.

我很确定我们现在可以很容易地将其转换为单一分配 Erlang/Haskell。

于 2011-07-30T14:04:18.140 回答
2

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

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

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

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

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

于 2011-07-30T13:30:25.393 回答