Syntax trees: free monad + Bound.Scope

Question

I'm attempting to define an abstract syntax type using ekmett's libraries bound and free. I have something working, which I can strip down to the following minimal example:

{-# LANGUAGE DeriveFunctor #-}

import Bound
import Control.Monad.Free

type Id = String

data TermF f α =
    AppF α α
  | BindF Id (Scope () f α)
  deriving Functor

newtype Term' α = T {unT :: Free (TermF Term) α}
type Term = Free (TermF Term')

Those last two lines are, uh, not what I was hoping for. They make it kind of a PITA to actually exploit the open recursion for annotations (or whatever).

Is there a better way of using these two libraries together, and/or should I just give up on trying to make Term a free monad?

Answer 1

Make it simple

You can simplify the last two lines into.

newtype Term α = T {unT :: Free (TermF Term) α}

This should help you know to consistently use T and unT everywhere instead of only at every other level.

Make it complicated

Both Free and TermF have the kind (*->*)->(*->*), which is the kind of a transformer. You are looking for the fixed point of the composition of Free and TermF. We can write the composition of transformers in general.

{-# LANGUAGE PolyKinds #-}

newtype ComposeT g h f a = ComposeT { unComposeT :: g (h f) a}
    deriving Functor

We can also write the fixed point of transformers in general.

{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UndecidableInstances #-}

newtype FixT t a = FixT { unFixT :: t (FixT t) a }

deriving instance Functor (t (FixT t)) => Functor (FixT t)

Then you could write

type Term = FixT (ComposeT Free TermF)

Then use FixT . ComposeT everywhere you would have just used T and unComposeT . unFixT everywhere you would have used unT.