Background
I am trying to set up something akin to recursion-schemes for a data structure that contains several mutually-recursive types as well as other type variables. In this simplified example, there are 4 pieces (“types”, “expressions”, “annotations”, and “namespaces”) representing an (incomplete) AST:
data Expression ns ann typ expr
= Typed ann expr typ
| Add ann expr expr
| Literal ann Int
data Typ ns ann typ expr
= Name ann ns String
| Function typ [typ]
Then I’ve also defined fixpoints for “expressions” and “types” (with “namespaces” and “annotations” still parameterized):
newtype FTyp ns ann =
FixT { unFixT :: Typ ns ann (FTyp ns ann) Never }
newtype FExpression ns ann =
FixE { unFixE :: Expression ns ann (FTyp ns ann) (FExpression ns ann) }
And I’ve defined a typeclass for folding (cata) and unfolding (ana) the data structure (and successfully implemented instances for both FTyp
and FExpression
):
class MyClass fix where
cata ::
(ns -> ns')
-> (ann -> ann')
-> (Typ ns' ann' t' e' -> t')
-> (Expression ns' ann' t' e' -> e')
-> fix ns ann
-> Either t' e'
ana ::
(ns' -> ns)
-> (ann' -> ann)
-> (t' -> Typ ns' ann' t' e')
-> (e' -> Expression ns' ann' t' e')
-> Either t' e'
-> fix ns ann
You can find my current full working code here: https://repl.it/repls/ParchedWornOctagons
Question
I’d like to get rid of the Either t' e'
in both functions – in instance MyClass FTyp
, the Either will always be a Left value, and in instance MyClass FExpression
, the Either will always be a Right value. Furthermore, it seems like it should always be clear from context which it will be; the choice of fix
should determine whether it should be t'
or e'
. Is it possible to make a typeclass that allows for this?
If t'
and e'
were concrete types, I think something could be done with MultiParamTypeClasses
and FunctionalDependencies
, or TypeFamilies
; but given they are universally quantified within each function, I’m not sure how to use either of those to any effect.
Other questions
I also realize that maybe I just shouldn’t be using a typeclass here and just define cataTyp/anaTyp/cataExpression/anaExpression
separately. Would that be the preferred approach? (If so, I’d still be interested to know if it can be done with typeclasses).
For the general problem of writing reusable code that manipulates mutually-recursive, parameterized data types, is there are there better approaches I should be aware of? I’d be happy to receive any pointers to books, papers, libraries, examples, etc that cover this topic.
Thanks!