如何在haskell中顯示派生樹？ (how can i show a derivation tree in haskell?)

問題描述

如何在haskell中顯示派生樹？ (how can i show a derivation tree in haskell?)

我正在做一個構建 while 語言派生樹的練習。我的 while 語言實現由代數數據類型組成，例如“Aexp”（算術表達式）“Bexp”（布爾表達式）和“Stm”（語句）：

type  Var   =  String
data  Aexp  =  N Integer
        |  V Var
        |  Add Aexp Aexp
        |  Mult Aexp Aexp
        |  Sub Aexp Aexp
        deriving (Show, Eq)

data  Bexp  =  TRUE
        |  FALSE
        |  Eq Aexp Aexp
        |  Le Aexp Aexp
        |  Neg Bexp
        |  And Bexp Bexp
        deriving (Show, Eq)

data  Stm   =  Ass Var Aexp
        |  Skip
        |  Comp Stm Stm
        |  If Bexp Stm Stm
        |  While Bexp Stm
        |  Repeat Stm Bexp
        deriving Show

在這些代數數據類型之後，我創建了更多的代數數據類型來表示while語言程序的派生樹

type  State  =  Var ‑> Z

data Config = Inter Stm State  ‑‑ <S, s>
        | Final State      ‑‑ s

data Transition = Config :‑‑>:  State

data DerivTree = AssNS     Transition
           | SkipNS    Transition
           | CompNS    Transition DerivTree DerivTree
           | IfTTNS    Transition DerivTree
           | IfFFNS    Transition DerivTree
           | WhileTTNS Transition DerivTree DerivTree
           | WhileFFNS Transition
           | RepeatTTNS Transition 
           | RepeatFFNS Transition DerivTree DerivTree

我怎樣才能顯示這種派生樹？？

<z:=x, s> ‑> s'    <x:=,s1> ‑> s''
‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑
    <z:=x; x:=y,s> ‑> s''             <y:=z,s''> ‑> s'''
    ‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑
            <z:=x; x:=y; y:=z, s> ‑> s'''

每個構造函數的期望值如下所示：

參考解法

方法 1:

Here is a simple example of using the boxes package to produce something derivation‑tree‑like. You should be able to adapt it to your needs without too much trouble ‑‑ either by producing a Tree String, or by using the ideas inside pp to produce a Box directly from your derivation trees. (I chose to use Tree String here rather than your type mainly to avoid having to figure out all the pretty‑printing details of a data type with lots of constructors.)

import Data.Tree
import Text.PrettyPrint.Boxes

pp :: Tree String ‑> Box
pp (Node here []      ) = text here
pp (Node here children) = vcat center1 [premises, separator, conclusion]
    where
    premises   = hsep 4 bottom (map pp children)
    conclusion = text here
    width      = max (cols premises) (cols conclusion)
    separator  = text (replicate width '‑')

sampleTree :: Tree String
sampleTree = Node "<z:=x; x:=y; y:=z, s> ‑> s'''"
    [Node "<z:=x; x:=y,s> ‑> s''"
        [Node "<z:=x, s> ‑> s'" []
        ,Node "<x:=,s1> ‑> s''" []
        ]
    ,Node "<y:=z, s''> ‑> s'''" []
    ]

Here's a sample run in ghci:

*Main> printBox (pp sampleTree)
<z:=x, s> ‑> s'    <x:=,s1> ‑> s''                       
‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑                       
      <z:=x; x:=y,s> ‑> s''           <y:=z, s''> ‑> s'''
‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑
              <z:=x; x:=y; y:=z, s> ‑> s'''              

(by eduardogr、Daniel Wagner)

參考文件

1. how can i show a derivation tree in haskell? (CC BY‑SA 2.5/3.0/4.0)