Бесплатная монада для AST> 1-арность? - PullRequest
Новая
       19

Бесплатная монада для AST> 1-арность?

6 голосов
/ 27 апреля 2019

Когда я говорю 1-arity | 2-arity | n-arity, я имею в виду дерево в теории графов k-ary tree :

k-арное дерево - это корневое дерево, в котором каждый узел имеет не более k дочерних элементов

Я использовал Free Monad в своем проекте для создания небольшого eDSL в haskell ... но все, что я видел, это только 1-арное дерево (Linear AST), подобное этому:

enter image description here

этот тип данных на Free Монада: 

data Toy b next =
    Output b next
  | Bell next
  | Done

Я хотел бы реализовать более сложный eDSL, чем линейный ... Является ли Free Monad решением для этого? и если да, у вас есть примеры Free Monad> 1-Ary?

1 Ответ

7 голосов
/ 27 апреля 2019

Представление и состав деревьев с обобщенным понятием арности - фактически одна из основных особенностей свободных монад.

Например, двоичные деревья могут быть определены как свободная монада следующим образом: 

data BinF a = Node a a
type Bin = Free BinF

node :: Bin a -> Bin a -> Bin a
node l r = Free (Node l r)

example :: Bin Int
example = node (node (pure 0)
                     (pure 1))
               (pure 2)
{-
  +---+---0
   \   \--1
    \-2
 -}

Изоморфное представление: 

data BinF a = Node (Bool -> a)
{- The product type (a, a) is isomorphic to (Bool -> a). -}

Идея этого заключается в том, что узел дерева можно рассматривать как требование для ввода (в данном случае, ввода типа Bool), которое используется для выбора одного из дочерних элементов узла. Таким образом, двоичное дерево можно рассматривать как синтаксический анализатор потоков битов. 

type Bin = Free BinF

nextBit :: Bin Bool
nextBit = Free (Node (\b -> Pure b))

example :: Bin Int
example = do
  b1 <- nextBit
  if b1 then do
    b2 <- nextBit
    if b2 then
      pure 0
    else
      pure 1
  else
    pure 2

Конечно, вы можете представить другие арты, изменив тип Bool (или количество полей Node в исходной формулировке).

Для более практического примера, библиотека каналов построена вокруг такой свободной монады .

...