Free Monad for AST > 1-arity?

Question

When I'm saying 1-arity | 2-arity | n-arity, I'm referring to tree in grap theory k-ary tree :

a k-ary tree is a rooted tree in which each node has no more than k children

I have been using Free Monad in my project to create a small eDSL in haskell... but all the example I have seen are only 1-ary tree (Linear AST) like this one :

this datatype lift on Free Monad :

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

I would like to implement a more complex eDSL than a Linear one... Is Free Monad a solution for that ? and if yes, do you have examples of Free Monad > 1-Ary ?

Answer 1

The representation and composition of trees with a generalized notion of arity is in fact one of the core features of free monads.

For example, binary trees can be defined as a free monad as follows:

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

An isomorphic representation is

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

The idea behind this is that a tree node can be seen as a demand for input (in this case, an input of type Bool), which is used to select one of the children of the node. Thus, a binary tree can be seen as a parser of bitstreams.

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

Of course, you can represent other arities by changing the Bool type (or the number of fields of Node in the original formulation).

For a more practical example, the pipes library is build around such a free monad.