CODEWITHSUNDEEP
haskellrecursiontypes
MathematicalOrchid
MathematicalOrchid

Reputation: 62808

Switching type recursion on and off

I'm working on a simple compiler. It starts off with a complicated data structure which is recursive (i.e., it's an expression tree), and ends up with exactly the same data structure, but with recursion disallowed.

"No problem", I thought to myself, "I'll just make the recursion type a type parameter, and then define type synonyms for the recursive and non-recursive types".

...ah, yes, but it turns out you can't actually do that. You see, type synonyms are not allowed to be recursive. >facepalm<

Any idea how I can achieve what I'm after?

Here's a very simplified example. Suppose I have these two data types:

data Type1 = Foo ID | Bar [Type1] | Baz Type1 Type1

data Type2 = Foo ID | Bar [ID] | Baz ID ID

My plan was to simply do this:

data Type r = Foo ID | Bar [r] | Baz r r

type Type1 = Type Type1
type Type2 = Type ID

But obviously that doesn't actually work.

Currently, it appears my options are these:

  1. Ignore the problem, and don't try to enforce this restriction in a type system.
  2. Duplicate the entire type definition (including renaming all the constructors).

Neither of these is really satisfactory. For the trivial example above, duplicating the type isn't too bad; for a big type definition, you do not want to be doing this!

Upvotes: 1

Views: 84

Answers (2)

Petr
Petr

Reputation: 63349

This sound like you might use recursion-schemes. You basically have two options:

  • Use Fix (or Mu or Nu) for creating the recursive variant, which means some nuisance with (un)wrapping its constructor all the time.

    data TypeF r = FooF ID | BarF [r] | BazF r r
  deriving (Functor)

type Type1 = Fix TypeF
type Type2 = TypeF ID

  • Define your own variant for the recursive case and implement project/embed as needed:

    data Type = Foo ID | Bar [Type] | Baz Type Type

type instance Base Type = TypeF

instance Foldable Type where
    project (Foo ID) = FooF ID
    project (Bar xs) = BarF xs
    project (Baz x y) = BazF x y

instance Unfoldable Type where
    embed (FooF ID) = Foo ID
    embed (BarF xs) = Bar xs
    embed (BazF x y) = Baz x y

    The type family Base provides the connection between the two: project and embed witness the isomorphism between Type and Base Type Type, and Base Type Type is equivalent to TypeF Type, unwrapping one level of recursion.

In both cases Foldable and Unfoldable implement various *-morphisms for converting between the recursive and non-recursive representations.

Upvotes: 2

Alexey Romanov
Alexey Romanov

Reputation: 170713

You can do this:

data Type r = Foo ID | Bar [r] | Baz r r

newtype Type1 = Type1 (Type Type1)
newtype Type2 = Type2 (Type ID) -- or type Type2 = Type ID, but this is more consistent

You need to remove an extra type constructor in functions dealing with Type1, but this shouldn't be a major problem.

More generally, you can define a fixed-point type constructor and use it for defining Type1.

Upvotes: 2

Related Questions