I have an AST that I'm annotating using
data ExprF a = Const Int | Add a a | Mul a a deriving (Show, Eq, Functor)
type Expr = Fix ExprF to represent untagged ASTs, and
type AnnExpr a = Cofree ExprF a to represent tagged ones. I've figured out a function to transform tagged ASTs into untagged ones by throwing away all the annotations:
forget :: Functor f => Cofree f a -> Fix f forget = Fix . fmap uncofree . unwrap
This looks like it might be some sort of catamorphism (I'm using the definition from Kmett's recursion-schemes package).
cata :: (Base t a -> a) -> t -> a cata f = c where c = f . fmap c . project
I'd think the above rewritten using a catamorphism would look something like this, but I can't figure out what to put for
alg to make it typecheck.
forget :: Functor f => Cofree f a -> Fix f forget = cata alg where alg = ???
Any help figuring out if this really is a cata/anamorphism, and some intuition for why it is/isn't would be greatly appreciated.
import Data.Functor.Foldable (cata) import Control.Comonad.Cofree (Cofree) import Control.Comonad.Trans.Cofree as CofreeT (CofreeF(..)) import Data.Fix (Fix(..)) forget :: Functor f => Cofree f a -> Fix f forget = cata (\(_ CofreeT.:< z) -> Fix z)
N.B.: be careful where
:< are imported from.
One is from
Control.Comonad.Cofree, the other from
Control.Comonad.Trans.Cofree (as part of the
CofreeF data type).
If you import
....Trans.Cofree instead, the
cata looks like this instead:
import Data.Functor.Identity (Identity(..)) import Data.Functor.Compose (Compose(..)) import Data.Functor.Foldable (cata) import Control.Comonad.Trans.Cofree as CofreeT (Cofree, CofreeF(..)) import Data.Fix (Fix(..)) forget :: Functor f => Cofree f a -> Fix f forget = cata (\(Compose (Identity (_ CofreeT.:< z))) -> Fix z)
Looking only at the types, we can show that there is really only one way to implement
forget. Let's start with the type of
cata :: Recursive t => (Base t b -> b) -> t -> b
t ~ Cofree f a and the type instance of
type instance Base (Cofree f a) = CofreeF f a
data CoFreeF f a b = a :< f b -- N.B.: CoFree also defines a (:<) constructor so you have to be -- careful with imports.
i.e., a fancy pair type. Let's replace it with an actual pair type to make things clearer:
cata :: Functor f => ((a, f b) -> b) -> Cofree f a -> b
Now we're really specializing
cata with a more concrete
-- expected type of `cata` in `forget` cata :: Functor f => ((a, f (Fix f)) -> Fix f) -> Cofree f a -> Fix f
forget is parametric in
f, so the function we give
cata can do nothing with the
a in the pair, and the only sensible way to implement the remaining
f (Fix f) -> Fix f is the
Fix is the identity, so
(\(_ :< z) -> Fix z) is really
(\(_ :< z) -> z) which corresponds to the intuition of removing the annotation, i.e., the first component of the pair
(_ :< z).