在haskell中解析Karva符号 [英] Parsing Karva notation in haskell

查看：135
本文介绍了在haskell中解析Karva符号的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

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



请看 http：// www.gene-expression-programming.com/Tutorial002.asp



通过读取基因并填充从左到右的节点来创建表达式树右，从上到下。



因此，例如在+中使用运算符（+，*）和终端（1,2,3,4,5,6） * + 1 + 2 * 3456将评估为39。

如何使用attoparsec（或parsec）在haskell中执行此操作？

  karvaParser :: Parser Int 
 karvaParser = ???????????? 
 
前奏> paar karvaParser+ * + 1 + 2 * 3456
完成39


解决方案

（我已经证明这是一个线性时间算法，在这个答案中提到的问题在这个答案的以前的版本中有更多的手动解决方案。）



基因表达式编程：Karva符号



使用继续传递monad可能是一个很好的解决方案， Cont ，但我没有想到它。这是一个相当干净的纯功能解决方案。



计划：




  1. 将输入分割成列表，每个图层使用前一行的总数。这是一个变形，即从一个种子（ [] ）增长一个列表，并且可以使用 unfoldr ::（b - > Maybe（ a，b）） - > b - > [a] 或等价地， unfoldr'::（b - >（a，b）） - > （b→Bool）→> b - > [a] 

     输入：Q / a * + b-cbabaccbac
     arities：12022020000000000 
     output：[Q，/，a *，+ b， -  c，ba] 
          pre>

  2. 递归地使用 splitAt 来粘合父项下的子项。这是一种变形（catamorphism），即将列表折叠成单个（树）值，并且可以使用 foldr ::（a-> b-> b） - > b - > [a] - > b


  3. 将变形和变形合并为一个变形。这就是所谓的hylomorphism。
    这些条款在开创性论文中引入FP社区用香蕉，镜头和铁丝网功能编程。




代码



如果您不熟悉它， Data.Tree 耗材数据树a =节点{root标签： ：a，subForest :: Forest a} 其中 type Forest a = [Tree a] 。

  import Data.Tree 
 import Data.Tree.Pretty  - 来自漂亮树包
 
 arity :: Char  - > Int 
 arity c 
 | c`elem`+ *  -  /= 2 
 | c`elem`Q= 1 
 |否则= 0 
 
 hylomorphism :: b  - > （a  - > b  - > b） - > （c  - >（a，c）） - > （c  - > Bool） - > c  - > b 
 hylomorphism base结合拔出停止seed = hylo seed其中
 hylo s |停止s = base 
 |否则=合并新（hylo s'）
其中（新，s'）=撤销s



<为了拉出一个关卡，我们使用前一关卡的总人数来寻找拆分这个新关卡的位置，并为下一次关卡准备这个关卡。

  pullLevel ::（Int，String） - > （String，（Int，String））
 pullLevel（n，cs）=（level，（total，cs'））其中
（level，cs'）= splitAt n cs 
 total = sum $ map arity level

要将级别（作为字符串）与下面的级别（即已经是森林），我们只是取消每个角色需要的树数。 

  combineLevel :: String  - >森林字符 - > Forest Char 
 combineLevel[] = [] 
 combineLevel（c：cs）levelBelow = Node c subforest：combineLevel cs theRest 
其中（subforest，theRest）= splitAt（arity c）levelBelow

现在我们可以使用一个hylomorphism来解析Karva。请注意，我们从 1 字符串之外的所有元素种子，因为在根级别只有一个节点。我已经使用头函数，因为 1 会导致顶层为包含一棵树的列表。

  karvaToTree :: String  - > Tree Char 
 karvaToTree cs = let 
 zero（n，_）= n == 0 
 in $ hylomorphism [] combineLevel pullLevel zero（1，cs）



Demo



让我们画一个结果（因为Tree是如此完整的语法很难读取输出！）。您必须 cabal install pretty-tree 才能获得 Data.Tree.Pretty 。

 请参阅：树字符 - > IO（）
 see = putStrLn.drawVerticalTree.fmap（：）
  





  ghci> arity'+'
 2 
 
 ghci> pullLevel（3，+ a * bc / acb）
（+ a *，（4，bc / acb））
 
 ghci> combineLevela *[Node'b'[]，Node'c'[]] 
 [Node {rootLabel ='a'，subForest = []}，Node {rootLabel ='*'，subForest = [节点{rootLabel ='b'，subForest = []}，节点{rootLabel ='c'，subForest = []}]}] 
 
 ghci>见。 Node'''$ combineLevela *[Node'b'[]，Node'c'[]] 
。 
 | 
 --- 
 / \ 
 a * 
 | 
  -  
 / \ 
 b c 
 
 ghci> karvaToTreeQ / a * + b-cbabaccbac
节点{rootLabel ='Q'，subForest = [Node {rootLabel ='/'，subForest = [Node {rootLabel ='a'，subForest = []} ，节点{rootLabel ='*'，subForest = [Node {rootLabel ='+'，subForest = [Node {rootLabel =' - '，subForest = [Node {rootLabel ='b'，subForest = []}，Node { rootLabel ='a'，subForest = []}]}，Node {rootLabel ='c'，subForest = []}]}，Node {rootLabel ='b'，subForest = []}]}]}]}

匹配


当我们看到见 code> it： 

  ghci>请参阅$ karvaToTreeQ / a * + b-cbabaccbac
 Q 
 | 
 / 
 | 
 ------ 
 / \ 
 a * 
 | 
 ----- 
 / \ 
 + b 
 | 
 ---- 
 / \ 
  -  c 
 | 
  -  
 / \ 
ba



Eval



一旦你有一棵树，很容易将它转换为其他东西。让我们来评估Karva表示法中的一个表达式： 

  action ::（Read num，Floating num）=>字符 - > [num]  - > num 
 action c = 
'Q'的情况c  - > sqrt.head 
'+' - > sum 
'*' - >产品
' - ' - > \ [a，b]  - > a  -  b 
'/' - > \ [a，b]  - > a / b 
 v  - > const（read（v：））
 
 eval ::（Read num，Floating num）=>树字符 - > num 
 eval（Node c subforest）= action c（map eval subforest）
  





  ghci>请参阅$ karvaToTreeQ +  -  * 826/12
 Q 
 | 
 + 
 | 
 ------- 
 / \ 
  -  * 
 | | 
  -  --- 
 / \ / \ 
 8 2 6 / 
 | 
  -  
 / \ 
 1 2 
 
 ghci> eval $ karvaToTreeQ +  -  * 826/12
 3.0


Karva notation is used in Gene Expression Programming to represent mathematical expressions.

See here http://www.gene-expression-programming.com/Tutorial002.asp

You create an expression tree by reading the off the gene and filling in nodes from left to right, top to bottom.

So for example using the operators ( +, * ) and terminals (1,2,3,4,5,6) in "+*+1+2*3456" would evaluate to 39.

How would I do this in haskell using attoparsec (or parsec)?

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

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

解决方案

(I've proved this is a linear time algorithm in this answer to the question mentioned in the comments. There's a lengthier more hand-rolled solution in a previous revision of this answer.)

Gene Expression Programming: Karva notation.

There's probably a neat solution using the continuation passing monad, Cont, but I haven't thought of it. Here's a fairly clean pure functional solution to the problem. I'll take the opportunity to name drop some good general recursion schemes along the way.

Plan:

  1. split the input into lists, one for each layer, using the total arity of the previous line. This is an anamorphism, i.e. grows a list from a seed ([]) and can be written using unfoldr :: (b -> Maybe (a, b)) -> b -> [a] or equivalently, unfoldr' :: (b -> (a, b)) -> (b -> Bool)-> b -> [a]

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

  2. Recursively use splitAt to glue the children under the parent. This is a catamorphism, i.e. collapses a list down to a single (tree) value, and can be written using foldr :: (a -> b -> b) -> b -> [a] -> b

  3. Combine the anamorphism and the catamorphism into one. That's called a hylomorphism. These terms are introduced to the FP community in the seminal paper Functional Programming with Bananas, Lenses and Barbed wire.

Code

In case you're not familiar with it, Data.Tree supplies 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

To pull out a level, we use the total arity from the previous level to find where to split off this new level, and pass on the total arity for this one ready for next time:

pullLevel :: (Int,String) -> (String,(Int,String))
pullLevel (n,cs) = (level,(total, cs')) where
                   (level,        cs') = splitAt n cs
                   total = sum $ map arity level

To combine a level (as a String) with the level below (that's already a Forest), we just pull off the number of trees that each character needs.

combineLevel :: String -> Forest Char -> Forest Char
combineLevel "" [] = []
combineLevel (c:cs) levelBelow = Node c subforest : combineLevel cs theRest 
      where (subforest,theRest) = splitAt (arity c) levelBelow

Now we can parse the Karva using a hylomorphism. Note that we seed it with a total arity from outside the string of 1, since there's only one node at the root level. I've used the head function because that 1 causes the top level to be a list containing one tree.

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

Demo

Let's have a draw of the results (because Tree is so full of syntax it's hard to read the output!). You have to 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

Eval

Once you have a Tree, it's easy to convert it to other things. Let's evaluate an expression in Karva notation:

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中解析Karva符号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆