как я могу показать дерево вывода в 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'''

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

введите здесь описание изображения


functional-programming tree haskell semantics algebraic-data-types
person eduardogr    schedule 16.11.2015    source источник
comment
Просто сделайте это рекурсивно. Как вы хотите визуализировать дерево, текст, латекс, что-то еще?   -  person Bergi    schedule 16.11.2015
comment
Что такое Config и State?   -  person Bergi    schedule 16.11.2015
comment
Что пробовали и с какими проблемами столкнулись? Действительно ли Aexpr, Bexpr и Stm имеют какое-либо отношение к вашей проблеме с отображением DerivTree?   -  person Cirdec    schedule 16.11.2015
comment
Латекс @Bergi был бы хорош! Дело в том, что я точно не знаю, как реализовать рекурсивную функцию для отображения этого   -  person eduardogr    schedule 16.11.2015
comment
@Cirdec Aexp, Bexp и Stm не имеют ничего общего, я написал это, чтобы вы знали, что это за выражения в дереве. Моя проблема заключается в том, как правильно распечатать дерево, чтобы получить удобную визуализацию. Тип производного дерева изображения является хорошей целью...   -  person eduardogr    schedule 16.11.2015
comment
Если вы собираетесь использовать латекс, это должно быть легко, так как латекс также является просто синтаксическим деревом. Просто преобразуйте каждый узел в соответствующую латексную команду. Вызовите функцию рекурсивно для дочерних узлов. Нет, вам не нужно начинать печать с самого глубокого узла, это просто структурная рекурсия.   -  person Bergi    schedule 16.11.2015
comment
Хорошо, я понимаю, @Bergi, можешь показать мне, как это сделать в хаскеле?   -  person eduardogr    schedule 16.11.2015
comment
Можете ли вы сказать нам, каков ожидаемый результат латекса для каждого из этих конструкторов?   -  person Bergi    schedule 16.11.2015
comment
Да, я отредактировал пост @Bergi   -  person eduardogr    schedule 16.11.2015
comment
Это все еще образ. Латекс — это текст, не так ли?   -  person Bergi    schedule 16.11.2015
comment
Я вижу здесь потенциальную проблему: ваши состояния являются семантическими (функциями), поэтому их сложно распечатать. Для формального вывода вы хотите, чтобы они были синтаксическими (например, s) или, по крайней мере, с синтаксическим аналогом.   -  person chi    schedule 16.11.2015
comment
Несвязанный: почему Config имеет две формы? В семантике большого шага используется только первый. Вам действительно нужен второй, а? Если вам это нужно для малошаговой семантики, рассмотрите возможность использования другого типа для двух типов конфигураций.   -  person chi    schedule 16.11.2015
comment
@ Берги, я знаю, что латекс - это текст, я тебя не понял. Но я не знаю латексный текст, чтобы показать конструкции...   -  person eduardogr    schedule 16.11.2015
comment
@EduGR: Если ваш вопрос заключается в том, какой латексный синтаксис использовать для создания этих изображений, здесь это не по теме. Вы можете спросить на TeX - LaTeX. Затем вернитесь, если у вас все еще есть проблемы с Haskell.   -  person Bergi    schedule 16.11.2015
comment
@Bergi, я разместил это здесь, потому что мне нужен способ сделать это в haskell, он не возражает, если он использует латекс или печатает строку в консоли.   -  person eduardogr    schedule 16.11.2015
comment
@chi: ты прав. В семантике большого шага нам не нужна промежуточная конфигурация. Это просто для выразительной реализации, в реализованных семантических функциях возвращаются только окончательные конфигурации.   -  person eduardogr    schedule 16.11.2015
comment
@EduGR: Тем не менее, это не подходящий вопрос для SO, если вы не можете сказать нам, как должен выглядеть вывод. Пожалуйста, покажите нам, какую латексную разметку или многострочную строку вы хотели бы создать, и мы можем помочь вам с реализацией haskell.   -  person Bergi    schedule 16.11.2015
comment
@Bergi, я заменяю одно изображение многострочной строкой, которую я хотел бы создать.   -  person eduardogr    schedule 16.11.2015

Ответы (1)


arrow_upward
3
arrow_downward

Вот простой пример использования boxes package для создания чего-то похожего на дерево вывода. Вы должны быть в состоянии адаптировать его к своим потребностям без особых проблем - либо путем создания 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'''
person Daniel Wagner    schedule 16.11.2015
comment
Спасибо!! Это мило! - person eduardogr; 17.11.2015