Exploring the compiler forest in Haskell

The combinators from the Compiler Forest paper can be implemented in Haskell as follows.  (Note: This requires recent GHC with options -XKindSignatures -XGADTs -XTypeFamilies.)
First, we define a type for partial compilers:

data PC :: * -> * -> * where
  PC :: (s -> (s', t' -> t)) -> PC (s,t) (s', t')

In Haskell terms, this is a "generalized algebraic data type", but this is solely so that we can think of PC as a two-argument type constructor instead of four.

We can introduce type families for extracting the source and target types from a pair:

type family Src a
type instance Src (s,t) = s

type family Tgt a
type instance Tgt (s,t) = t

applyPC :: PC p q -> 
          (Src p -> (Src q, Tgt q -> Tgt p))
applyPC (PC f) = f

The identity on partial compilers is:

idPC :: PC (s, t) (s, t)
idPC = PC (\s -> (s, id))

and composition of partial compilers is as follows:

compPC :: PC q r -> PC p q -> PC p  r
compPC (PC g) (PC f) =
  PC (\s -> let (s',f') =  f s in
            let (s'', g') =  g s' in
            (s'', f' . g'))


Likewise, tensor product of partial compilers can be defined.  First, we introduce a type family for tensors:

type family Tensor a b
type instance Tensor (s1,t1) (s2,t2) = 
                     ((s1,s2), (t1,t2))

tensorPC :: PC p1 p2 -> PC p1' p2' -> 
            PC (Tensor p1 p1') (Tensor p2 p2')
tensorPC (PC f) (PC g) =
  PC (\(x1,x2) -> 
        let (y1,f') = f x1 in
        let (y2,g') = g x2 in
        ((y1,y2),\(z1,z2) -> (f' z1, g' z2)))

The conditional combinator is:

condPC :: (Src p -> Bool) -> 
          PC p q -> PC p q -> PC p q
condPC p (PC f) (PC g) =
  PC (\s -> if p s then f s else g s)

and the (very similar) case combinator is:

casesPC :: (s -> Either s1 s2) -> 
           PC (s1,t) q -> 
           PC (s2,t) q -> PC (s,t) q
casesPC w (PC f) (PC g) =
  PC (\s -> case w s  
              of Left(s1) -> f s1 ;
                 Right(s2) -> g s2)

The "functor" operation that constructs a pair of functions $f:(s \to s')$ and $g:(t'\to t)$ to a partial compiler is:

functorPC :: (s -> s') -> (t' -> t) -> 
             PC(s,t) (s',t')
functorPC f g = PC (\s -> (f s,g))

and finally the iterator combinator is:

iterPC :: Int -> PC p p -> PC p p
iterPC 0 pc = pc
iterPC n pc = compPC pc (iterPC (n-1) pc)

Exercise for the reader: Implement some of the atomic partial compilers in Haskell and use the above combinators to combine them...