Karva 表示法在基因表达编程中用于表示数学表达式。
看这里http://www.gene-express-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
（我已经证明这是一个线性时间算法这个答案对于评论中提到的问题。有一个更长的、更手动的解决方案之前的修订版这个答案。）
使用连续传递 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将孩子粘在父母下面。这是一种变形，即将列表折叠为单个（树）值，并且可以使用以下方式编写foldr :: (a -> b -> b) -> b -> [a] -> b
将变形和变形合二为一。这就是所谓的hylomorphism。 这些术语在开创性论文中被引入到 FP 社区使用香蕉、镜头和铁丝网进行函数式编程.
如果你不熟悉的话，Data.Tree补给品data Tree a = Node {rootLabel :: a, subForest :: Forest a} where 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 to get 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 = []}]}]}]}
Which matches
as we see when we see it:
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