Блог

Главная - Вопросы по программированию - Использование Text.Generic.Diff для генерации выходных данных, содержащих «вставленные» / «удаленные» маркеры

Использование Text.Generic.Diff для генерации выходных данных, содержащих «вставленные» / «удаленные» маркеры

#haskell #tree #diff

#haskell #дерево #разница

Вопрос:

Я использую пакет Haskell gdiff для вычисления различий между деревьями. Результатом алгоритма diff является «сценарий редактирования», который описывает последовательность операций, преобразующих дерево «до» в дерево «после». gdiff предоставляет функцию «исправления», которая применяет сценарий редактирования к дереву «до», следовательно, генерируя дерево «после».

Что мне нужно сделать, так это изменить эту операцию исправления, чтобы выходные данные представляли собой дерево «после», в котором выделены изменения.

В качестве примера представьте, что дерево — это документ AST. Я хочу сгенерировать выходные данные, которые показывают вставки / удаления, встроенные в документ «после».

На данный момент я написал программу, которая успешно использует gdiff для вычисления различий между экземплярами простой структуры данных двоичного дерева. Чего я не могу понять, так это как изменить результирующий скрипт редактирования так, чтобы он вводил маркеры «вставлено» и «удалено» при выполнении операции исправления.

Кто-нибудь может помочь?

Различение двух двоичных деревьев

Вот моя структура данных двоичного дерева: 

 data Tree = Node String Tree Tree
          | Empty
          deriving Show

И вот мой пример деревьев «до» и «после»:

 before :: Tree
before =
  Node "root"
    (Node "A"
      (Empty)
      (Empty)
    )
    (Empty)

after :: Tree
after =
  Node "root"
    (Node "A"
      (Node "B" Empty Empty)
      (Empty)
    )
    (Empty)

Diff выполняется следующим образом:

 runDiff :: EditScript TreeFamily Tree Tree
runDiff = diff before after

main :: IO ()
main = do
  putStrLn ("before     = "    (show before))
  putStrLn ("after      = "    (show after))

  let edit = runDiff
  putStrLn ("edit       = "    (show edit))

  let compressed = compress edit
  putStrLn ("compressed = "    (show compressed))

  let result = patch edit before
  putStrLn ("result     = "    (show result))

(Я вернусь к определению TreeFamily через мгновение.)

Выходные данные:

 before     = Node "root" (Node "A" Empty Empty) Empty
after      = Node "root" (Node "A" (Node "B" Empty Empty) Empty) Empty
edit       = Cpy Node $ Cpy "root" $ Cpy Node $ Cpy "A" $ Ins Node $ Ins "B" $ Cpy Empty $ Cpy Empty $ Cpy Empty $ Ins Empty $ End
compressed = Cpy Node $ CpyTree $ Cpy Node $ CpyTree $ Ins Node $ Ins "B" $ CpyTree $ CpyTree $ CpyTree $ Ins Empty $ End
result     = Node "root" (Node "A" (Node "B" Empty Empty) Empty) Empty

Предлагаемая стратегия: обработать сценарий редактирования

I think that I can implement the «generate marked-up after tree» operation by processing the edit script so that ... $ Ins Node $ ... is replaced with ... $ Ins InsNode $ ... , where InsNode is another Tree constructor:

 data Tree = Node String Tree Tree
          | InsNode String Tree Tree
          | Empty
          deriving Show

(And similarly for deletions, but this post focuses only on insertion.)

The processed edit script would then be fed to the existing gdiff patch function.

TreeFamily definition

The gdiff library requires the user to define a «family datatype». Here is my definition. Note that I have included the InsNode type. Although this doesn’t appear in the input data, I think gdiff will need to know about it in order to perform the Node to InsNode substitution described above.

 data TreeFamily :: * -> * -> * where
    Node'       ::           TreeFamily Tree (Cons String (Cons Tree (Cons Tree Nil)))
    InsNode'    ::           TreeFamily Tree (Cons String (Cons Tree (Cons Tree Nil)))
    String'     :: String -> TreeFamily String Nil
    Empty'      ::           TreeFamily Tree Nil


instance Family TreeFamily where
    decEq Node' Node'                  = Just(Refl, Refl)
    decEq InsNode' InsNode'            = Just(Refl, Refl)
    decEq (String' s1) (String' s2)
                | s1 == s2             = Just (Refl, Refl)
                | otherwise            = Nothing
    decEq Empty' Empty'                = Just(Refl, Refl)
    decEq _ _                          = Nothing

    fields Node' (Node s t1 t2)        = Just (CCons s (CCons t1 (CCons t2 CNil)))
    fields InsNode' (InsNode s t1 t2)  = Just (CCons s (CCons t1 (CCons t2 CNil)))
    fields (String' _) _               = Just CNil
    fields Empty' Empty                = Just CNil
    fields _ _                         = Nothing

    apply Node' (CCons s (CCons t1 (CCons t2 CNil)))    = Node s t1 t2
    apply InsNode' (CCons s (CCons t1 (CCons t2 CNil))) = InsNode s t1 t2
    apply (String' s) CNil                              = s
    apply Empty' CNil                                   = Empty

    string Node'       = "Node"
    string InsNode'    = "InsNode"
    string (String' s) = show s
    string Empty'      = "Empty"


instance Type TreeFamily Tree where
    constructors = [ Concr Node', Concr InsNode', Concr Empty' ]

instance Type TreeFamily String where
    constructors = [ Abstr String' ]

Первая попытка функции processEdit

Функция, которая обрабатывает EditScript для выполнения подстановки Node в InsNode , должна иметь ту же подпись, что и compress функция, а именно:

 processEdit :: (Family f) => EditScriptL f txs tys -> EditScriptL f txs tys

Я могу написать следующие уравнения идентификации…

 processEdit End         = End
processEdit (Ins  c  d) = Ins  c   (processEdit d)
processEdit (Del  c  d) = Del  c   (processEdit d)
processEdit (CpyTree d) = CpyTree  (processEdit d)
processEdit (Cpy  c  d) = Cpy  c   (processEdit d)

… но я не знаю, как изменить Ins уравнение для выполнения замены. Кто-нибудь может помочь?

Завершите тестовую программу для справки

 {-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE GADTs                 #-}
{-# LANGUAGE KindSignatures        #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE NoImplicitPrelude     #-}


module Main where

import Prelude
import Data.Generic.Diff


-- Data types --

data Tree = Node String Tree Tree
          | InsNode String Tree Tree
          | Empty
          deriving Show


-- GADT Family --

data TreeFamily :: * -> * -> * where
    Node'       ::           TreeFamily Tree (Cons String (Cons Tree (Cons Tree Nil)))
    InsNode'    ::           TreeFamily Tree (Cons String (Cons Tree (Cons Tree Nil)))
    String'     :: String -> TreeFamily String Nil
    Empty'      ::           TreeFamily Tree Nil


instance Family TreeFamily where
    decEq Node' Node'                  = Just(Refl, Refl)
    decEq InsNode' InsNode'            = Just(Refl, Refl)
    decEq (String' s1) (String' s2)
                | s1 == s2             = Just (Refl, Refl)
                | otherwise            = Nothing
    decEq Empty' Empty'                = Just(Refl, Refl)
    decEq _ _                          = Nothing

    fields Node' (Node s t1 t2)        = Just (CCons s (CCons t1 (CCons t2 CNil)))
    fields InsNode' (InsNode s t1 t2)  = Just (CCons s (CCons t1 (CCons t2 CNil)))
    fields (String' _) _               = Just CNil
    fields Empty' Empty                = Just CNil
    fields _ _                         = Nothing

    apply Node' (CCons s (CCons t1 (CCons t2 CNil)))    = Node s t1 t2
    apply InsNode' (CCons s (CCons t1 (CCons t2 CNil))) = InsNode s t1 t2
    apply (String' s) CNil                              = s
    apply Empty' CNil                                   = Empty

    string Node'       = "Node"
    string InsNode'    = "InsNode"
    string (String' s) = show s
    string Empty'      = "Empty"


instance Type TreeFamily Tree where
    constructors = [ Concr Node', Concr InsNode', Concr Empty' ]

instance Type TreeFamily String where
    constructors = [ Abstr String' ]


-- Input trees --

before :: Tree
before =
  Node "root"
    (Node "A"
      (Empty)
      (Empty)
    )
    (Empty)

after :: Tree
after =
  Node "root"
    (Node "A"
      (Node "B" Empty Empty)
      (Empty)
    )
    (Empty)


{-
Function for modifying the edit script

The objective is to transform edit script fragments of the form
    ... $ Ins Node $ ...
to
    ... $ Ins InsNode $ ...
-}

processEdit :: (Family f) => EditScriptL f txs tys -> EditScriptL f txs tys
processEdit End         = End
processEdit (Ins  c  d) = Ins  c   (processEdit d)
processEdit (Del  c  d) = Del  c   (processEdit d)
processEdit (CpyTree d) = CpyTree  (processEdit d)
processEdit (Cpy  c  d) = Cpy  c   (processEdit d)


-- Test --

-- For some reason, this signature is required for type inference to work --
runDiff :: EditScript TreeFamily Tree Tree
runDiff = diff before after

main :: IO ()
main = do
  putStrLn ("before     = "    (show before))
  putStrLn ("after      = "    (show after))

  let edit = runDiff
  putStrLn ("edit       = "    (show edit))

  let compressed = compress edit
  putStrLn ("compressed = "    (show compressed))

  let processed = processEdit compressed
  putStrLn ("processed  = "    (show processed))

  let result = patch edit before
  putStrLn ("result     = "    (show result))

Ответ №1:

Просто специализируйтесь processEdit на том, чтобы быть на TreeFamily (потому что очевидно, что то, чего вы пытаетесь достичь, специфично для TreeFamily ) и сопоставьте шаблон с (первым) аргументом Ins .

 processEdit :: EditScriptL TreeFamily txs tys -> EditScriptL TreeFamily txs tys
processEdit End         = End
processEdit (Ins  Node' d) = Ins  InsNode'   (processEdit d)
processEdit (Ins  c  d) = Ins  c (processEdit d)
processEdit (Del  c  d) = Del  c   (processEdit d)
processEdit (CpyTree d) = CpyTree  (processEdit d)
processEdit (Cpy  c  d) = Cpy  c   (processEdit d)

Однако мне не нравится такой подход. Это требует изменения вашего исходного типа данных, и вы теряете различие на уровне типа между «исходным» деревом и «исправленным» деревом. Лучшим решением было бы создать другой тип данных (например. ChangedTree ) и переопределить patch' :: EditScriptL TreeFamily Tree Tree -> Tree -> ChangedTree . Если вы отслеживаете как вставки, так и удаления, может быть, вам также потребуется изменение типа «заменить»?

О, и runDiff нужна подпись типа, потому что в противном случае он не знает, какой Type _ Tree экземпляр использовать. например. diff @TreeFamily before after (Расширение TypeApplications) исправило бы это. Классы типов Haskell открыты, поэтому он не будет автоматически определять, что вам нужно, instance Type TreeFamily Tree а не какой-либо другой instance Type XXX Tree , только потому, что он не видит другого подходящего XXX по области видимости прямо сейчас, не означает, что он догадается, что это то, что вы намеревались использовать.

Комментарии:

1. Предлагаемое изменение в processEdit дает желаемый эффект.

2. Что касается предложения реализовать новый тип для измененного дерева, есть две причины, по которым я бы предпочел этого не делать: 1. Тип данных дерева, показанный в моем примере, урезан из реального приложения. Последний уже имеет общий тип узла, который имеет атрибуты, включая список меток. Я планирую использовать эти метки для обозначения вставки / удаления. Я понимаю, что в Haskell обычно предпочтительнее использовать строго типизированный подход, но использование меток лучше подходит для моего приложения.

3. 2. При просмотре Diff.hs функция исправления зависит от большого количества подфункций. Предположение о том, что входные и выходные деревья имеют один и тот же тип, глубоко заложено в сигнатуры этих функций. Поэтому для реализации patch’ потребуется повторная реализация значительной части кода базовой библиотеки.

4. @GarethStockwell, это звучит как отличное улучшение, которое вы могли бы внести в библиотеку!

5. @dfeuer Эта программа — первая программа на Haskell, которую я когда-либо писал. Я пытаюсь пройти, прежде чем смогу запустить 🙂