haskell - 在haskell中解析Karva符号

基因表达式编程中使用 Karva 符号来表示数学表达式。

看这里 http://www.gene-expression-programming.com/Tutorial002.asp

您可以通过读取关闭的基因并从左到右、从上到下填充节点来创建表达树。

因此，例如在“+*+1+2*3456”中使用运算符 (+, *) 和终结符 (1,2,3,4,5,6) 的计算结果为 39。

我将如何使用 attoparsec(或 parsec)在 haskell 中做到这一点？

karvaParser :: Parser Int
karvaParser = ????????????

Prelude> parse karvaParser "+*+1+2*3456"
Done 39

最佳答案

(我已经证明这是 this answer 中针对评论中提到的问题的线性时间算法。在这个答案的 previous revision 中有一个更长的手动解决方案。)

基因表达编程:Karva 符号。

使用 continuation 传递 monad Cont 可能有一个巧妙的解决方案，但我还没有想到。这是该问题的一个相当干净的纯函数式解决方案。在此过程中，我将借此机会列举一些优秀的通用递归方案。

计划:

使用前一行的总数量将输入拆分为列表，每层一个。这是一种变形，即从种子 ( [] ) 生成一个列表，可以使用 unfoldr :: (b -> Maybe (a, b)) -> b -> [a] 或等效的 unfoldr' :: (b -> (a, b)) -> (b -> Bool)-> b -> [a] 编写

input:   "Q/a*+b-cbabaccbac"
arities:  12022020000000000
output:  ["Q","/","a*","+b","-c","ba"]

递归地使用 splitAt 将子级粘合到父级下。这是一个 catamorphism，即将列表折叠为单个(树)值，并且可以使用 foldr :: (a -> b -> b) -> b -> [a] -> b

编写

将变形和变形合二为一。这就是所谓的hylomorphism。
这些术语在开创性论文 Functional Programming with Bananas, Lenses and Barbed wire 中介绍给 FP 社区。

代码

如果您不熟悉它，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

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

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 函数，因为 1 使顶层成为包含一棵树的列表。

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

演示

让我们来看看结果(因为 Tree 的语法太丰富了，很难阅读输出!)。你必须 cabal install pretty-tree 才能获得 Data.Tree.Pretty 。

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

ghci> arity '+'
2

ghci> pullLevel (3,"+a*bc/acb")
("+a*",(4,"bc/acb"))

ghci> combineLevel "a*" [Node 'b' [],Node 'c' []]
[Node {rootLabel = 'a', subForest = []},Node {rootLabel = '*', subForest = [Node {rootLabel = 'b', subForest = []},Node {rootLabel = 'c', subForest = []}]}]

ghci> see . Node '.' $ combineLevel "a*" [Node 'b' [],Node 'c' []]
   .
   |
 ---
/   \
a   *
    |
    --
   /  \
   b  c

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 = []}]}]}]}

哪个匹配

正如我们在 see 时看到的:

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

评估

一旦你有了树，就很容易把它转换成其他东西。让我们用 Karva 表示法计算一个表达式:

action :: (Read num,Floating num) => Char -> [num] -> num
action c = case c of
   'Q' -> sqrt.head
   '+' -> sum
   '*' -> product
   '-' -> \[a,b] -> a - b
   '/' -> \[a,b] -> a / b
   v -> const (read (v:""))

eval :: (Read num,Floating num)  => Tree Char -> num
eval (Node c subforest) = action c (map eval subforest)

ghci> see $ karvaToTree "Q+-*826/12"
      Q
      |
      +
      |
  -------
 /       \
 -       *
 |       |
 --    ---
/  \  /   \
8  2  6   /
          |
          --
         /  \
         1  2

ghci> eval $ karvaToTree "Q+-*826/12"
3.0

关于haskell - 在haskell中解析Karva符号，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11869206/