Рекурсивная прогулка по AST с использованием foldl и монады Reader без шаблонов

Question

Я пересекаю AST, используя простое сопоставление с образцом и Reader монада

В другом месте в моем проекте я определил walk функция для прохождения AST, которая в своей основе использует foldl сократить результаты посещения каждого узла в дереве до единого моноидального результата (например, создать "таблицу символов" из специальных узлов в дереве).

У меня вопрос: возможно ли объединить эти два подхода и использовать функцию, подобную моей? walk функция:

walk :: Monoid a => (Node -> a) -> a -> Node -> a
walk f acc n = foldl (walk f) (acc <> f n) children
  where
    children = case n of
      Blockquote b           -> b
      DocBlock d             -> d
      FunctionDeclaration {} -> functionBody n
      List l                 -> l
      ListItem i             -> i
      Paragraph p            -> p
      Unit u                 -> u
      _                      -> [] -- no Node children

и Reader - как обход в коде ниже (некоторые биты опущены для краткости) - в то же время?

markdown :: Node -> String
markdown n = runReader (node n) state
  where state = State (getSymbols n) (getPluginName n)

node :: Node -> Env
node n = case n of
  Blockquote b            -> blockquote b >>= appendNewline >>= appendNewline
  DocBlock d              -> nodes d
  FunctionDeclaration {}  -> nodes $ functionBody n
  Paragraph p             -> nodes p >>= appendNewline >>= appendNewline
  Link l                  -> link l
  List ls                 -> nodes ls >>= appendNewline
  ListItem l              -> fmap ("- " ++) (nodes l) >>= appendNewline
  Unit u                  -> nodes u

Моя мотивация использования здесь заключается в том, что мой walk Функция уже кодирует знания о том, как получить дочерние элементы для каждого шаблона и как выполнить упорядоченный обход AST. Я не хочу переопределять это для каждого обхода, поэтому было бы неплохо использовать walk в большем количестве мест, в том числе тех, где мне нужно использовать Reader (и, вероятно, позже, Stateвидимо в стеке).

Можно ли эти вещи плодотворно сочетать?

Answer 1

Линзовый подход

Момент для общего программирования! Именно эта проблема, проблема сворачивания рекурсивного типа данных без шаблона, является мотивацией для библиотеки uniplate/biplate. Этот дизайн теперь живет в своей самой современной форме в Control.Lens.Plated с / о lens пакет. Чтобы воспользоваться этим:

• Включи DeriveDataTypeable и добавить deriving (Data) на ваш Node, ArgumentList, Argument,

• Сразу же вы можете воспользоваться uniplate от Data.Data.Lens, Это обходной путь, объект, который - при передаче правым помощникам линз - даст вам все значения типа Node внутри данного Node, В основном это выполняется один шаг вашего рекурсивного walk функция.

• Пример:

  λ> Blockquote [BreakTag, Blockquote [BreakTag]] ^.. uniplate
  [BreakTag,Blockquote [BreakTag]]
  λ> Blockquote [BreakTag, Blockquote [BreakTag]] ^.. uniplate . uniplate
  [BreakTag]
  λ> Blockquote [BreakTag, Blockquote [BreakTag]] ^.. uniplate . uniplate . uniplate
  []
  

• Но подождите, это еще не все. Если uniplate это один маленький шаг для генериков, то cosmosOf uniplate это один большой шаг для программиста. cosmosOf неоднократно использует uniplate извлекать детей, внуков, правнуков и т. д. из заданного Node,

  λ> Blockquote [BreakTag, Blockquote [BreakTag]] ^..  cosmosOf uniplate
  [ Blockquote [BreakTag,Blockquote [BreakTag]]
  , BreakTag
  , Blockquote [BreakTag]
  , BreakTag]
  

• В обоих примерах мы используем преимущества lens обходы (и складки) есть. Иерархия линз и то, почему они так хорошо сочетаются, выходит за рамки этого небольшого текстового поля, но достаточно сказать, что они супер мега полезны.

• Использовать foldlOf помощник в Control.Lens.Fold реализовать свой walk функция:

  walk' :: Monoid a => (Node -> a) -> a -> Node -> a
  walk' f acc n =
    foldlOf (cosmosOf uniplate . to f) (<>) acc n
  

  Не так плохо. to f создает получатель из вашего f и он состоит из космической складки, чтобы достичь всех потомков; каждое значение из этого геттера складывается и накапливается в нашем моноиде.

Что касается node Вам нужно будет создать пользовательский фолд. cosmosOf uniplate здесь не очень хорошо работает, потому что иногда вы замыкаете рекурсию (например, в Blockquote дело). Вам придется написать cosmosOf foo и построить foo по частям из линз помощников; обратите внимание, что вы все еще можете использовать uniplate разгрузить большую часть случаев в вашу обычную складку. Это довольно большой кусок кода, и он ужасно запаздывает, поэтому я оставлю это в качестве упражнения для читателя. Я на 90% уверен, что это возможно.

Что касается монады читателя, вы можете использовать foldlMOf или обратите внимание, что type Env = Reader State String изоморфен State -> String и обратите внимание, что State -> String имеет Monoid экземпляр, потому что Monoid String существует. Это все означает, что вы должны быть в состоянии реализовать node с немонадическим foldlOf как мы делали выше - все, что мы действительно хотим сделать, это объединить несколько моноидальных значений, в конце концов.

Это решение не является идеальным: оно требует, чтобы будущие читатели кода знали немного об объективе и о том, как обходы / сгибы / геттеры склеиваются с Data.Data и почему у всех этих функций есть забавный маленький Of суффиксы на них. Но вы должны признать, что есть прекрасный вид Plated которая абстрагирует скучную рекурсивную часть свертывания от пользовательских типов данных, так что вам нужно только сопоставить шаблон с листьями структуры данных (например, BreakTag в node) и крайние случаи (как Blockquote в node).

Answer 2

Ваш walk функция очень похожа на Foldable класс, который является суперклассом Traversable (который dfeuer также указывает в комментарии). В вашей позиции я бы взглянул на mono-traversable пакет

Но у меня есть догадка, что ваш Node тип на самом деле не окажется хорошим MonoTraversable экземпляр, как в настоящее время сформулировано. Неформальная причина в том, что между этими понятиями нет хорошего разделения:

1. Структура AST: какие узлы являются дочерними для чего.
2. Содержимое AST: "атрибуты" на каждом узле.

Один очень неформальный способ думать о Functor а также Traversable классы в том, что они оперируют "содержимым" значения, не изменяя его "структуры" (но остерегайтесь слишком буквально воспринимать эту аналогию). Я подумал написать MonoTraversable экземпляр для вашего Node типа, но отступил быстро после некоторой мысли:

{-# LANGUAGE TypeFamilies #-}

import Data.MonoTraversable

-- Here is the root of the problem.  The type function 
-- `Element` is supposed to pick out which pieces of a 
-- `Node` are its "content" as opposed to its "structure,"
-- but with `Node` as formulated there isn't a distinction!
type instance Element Node = Node

Учитывая это, otraverse метод, который имеет этот основной тип:

otraverse :: Applicative f => (Element mono -> f (Element mono)) -> mono -> f mono

... будет в конечном итоге с этим специализированным типом, когда mono := Node:

otraverse :: Applicative f => (Node -> f Node) -> Node -> f Node    

... и я боюсь, что кто-то может попытаться позвонить otraverse с функцией, которая отбрасывает дочерние элементы корневого узла, например, насколько это зло, когда кто-то пытается otraverse (return Separator)?

Я не проверил, являются ли эти случаи незаконными, так что, возможно, я ни о чем здесь не беспокоюсь, стоит проверить, не ошибаюсь ли я. Но это, конечно, "пахнет плохо" в соответствии с моим дизайном.

---

Так что делать? Я бы посмотрел в переформулировании Node введите немного, разделив его на два типа:

1. Content тип, который выражает информацию, которая видна на каждом шаге обхода AST слева направо, но не как Contentгнездо;
2. Structure тип, который определяет возможные формы дерева - как Contentгнездо

Как только это будет сделано, вы сможете переформулировать свой walk функционировать так:

walk :: Monoid a => (Content -> a) -> a -> Structure -> a

Обратите внимание, что второй аргумент этой функции (начальный acc :: Monoid a => a значение) излишне, эти две функции выглядят взаимозависимыми:

walk' :: Monoid a => (Content -> a) -> Structure -> a
walk' f = walk f mempty

walk :: Monoid a => (Content -> a) -> a -> Structure -> a
walk f acc tree = acc <> walk' f tree

И мой walk' подпись выглядит так, как будто это будет ofoldMap метод из mono-traversable:

ofoldMap :: Monoid m => (Element mono -> m) -> mono -> m

Который тогда сделал бы естественным спросить, можете ли вы реализовать MonoTraversable для вашего переформулированного типа и получить otraverse операция, подпись которой я упоминал выше, которая специализировалась на f := Reader r, а также mono := Structure а также Element mono := Content было бы:

otraverse :: (Content -> Reader r Content) -> Structure -> Reader r Structure