Как я могу показать дерево деривации в haskell?

Question

Я работаю над упражнением, которое создает дерево деривации языка. Моя реализация в то время как язык состоит из алгебраических типов данных, таких как «Àexp» (Арифметические выражения) «ехр» (логические выражения) и «СТМ» (заявления):

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''' 

Ожидаемое значение для каждого конструктора выглядит следующим образом:

Answer 1

Вот простой пример использования boxes пакета, чтобы произвести что-то вывод-древовидная. Вы должны быть в состоянии адаптировать его к своим потребностям без особых проблем - либо путем создания Tree String, либо используя идеи внутри pp, чтобы получить Box непосредственно из ваших деревьев деривации. (. Я решил использовать Tree String здесь, а не вашего типа, главным образом, чтобы избежать того, чтобы выяснить все детали довольно-печать данных определенного типа с большим количеством конструкторов)

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'''" [] 
    ] 

Вот пример работы в 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'''