CODEWITHSUNDEEP
haskell
Isaac
Isaac

Reputation: 1401

How to model hierarchical data types in Haskell?

I have a bunch of types where their hierarchy stores some useful information. I'm trying to avoid having to bake in knowledge of the hierarchy of the types into the functions that operate on them.

The following is a little excerpt of Stanford's Typed Dependencies for natural language processing:

root - root
dep - dependent
  aux - auxiliary
    auxpass - passive auxiliary 
    cop - copula
  arg - argument 
    agent - agent

I would like to create some data types that mirror this structure so that I can define some functions that can only operate on certain types. When I have a function that operates on an arg, the type that I use to represent arg should also include agent but the type for agent should not include arg. The type for dep should include anything below it.

Is this possible in haskell? I've been trying to declare various data types to model this, but I can't get it to work since a data type cannot use the constructor of another data type.

I suspect that maybe this approach doesn't work very well with Haskell, so if that's the case how do you usually deal with these cases where flattening the hierarchy is definitely undesirable?

Upvotes: 5

Views: 1050

Answers (2)

Alec
Alec

Reputation: 32319

Subtyping in general does not play too well with Haskell. However, in the case that you are just trying to model (non-multiple) inheritance (so you have a tree of subtypes instead of a lattice), you can actually build sub typing up using type classes. Here is a short gist that does exactly this. Working from there, you define your data types

data Root = Root ...
data Dep = Dependent ...
data Aux = Auxiliary ...
data AuxPass = PassiveAuxiliary ... 
data Cop = Copula ...
data Arg = Argument ...
data Agent = Agent ...

And the corresponding instances 

instance Subtype Aux where
  type SuperType Aux = Dep
  embedImmediate = ...

instance Subtype AuxPass where
  type SuperType AuxPass = Aux
  embedImmediate = ...

instance Subtype Cop where
  type SuperType Cop = Aux
  embedImmediate = ...

instance Subtype Arg where
  type SuperType Arg = Dep
  embedImmediate = ...

instance Subtype Agent where
  type SuperType Agent = Arg
  embedImmediate = ...

How you fill in the ... is up to you. A couple things you could do for this:

  • if your subtype adds lots of fields on top of the supertype, consistently, just add to it a field that has the supertype and make embedImmediate return that field
  • if your subtype adds only a couple of fields, you might want to manually unpack them. Your data definitions will look neater, but your embedImmediate definition will be a bit longer
  • if your subtypes doesn't add any fields to the supertype, you can just make a newtype around the super type and embedImmediate = coerce (from Data.Coerce)

Then, you can't quite just use the subtypes in functions that expect supertypes, but almost: you just have to add a call to embed (different from embedImmediate!) to convert from the subtype to whichever supertype is needed (based on type inference). You may want to check out some example uses.

Note that you can now use <: as a constraint: the type of something that is a subtype of Aux, for example, is (a <: Aux) => a. Whenever you want this thing treated as an Aux (or a super type of Aux), call embed on it.

The one big downside of this approach is that the input and output types must be annotated (else it isn't clear which supertype you want to embed into and you'll get "ambiguous type" errors). If you already write lots of signatures, you should be fine though.

Upvotes: 1

user1937198
user1937198

Reputation: 5358

Use typeclasses.

First define each of the concrete types as a seperate data declaration.

Then for each type with subtypes declare a typeclass with a constraint on its parent. An example of this sort of relationship is Functor => Applicative => Monad structure in prelude.

So to define the example structure:

class Root where
    ...

class Root => Dep where
    ...

class Dep => Aux where
    ...

class Aux => Auxpass where
    ...

class Aux => Cop where
    ...

class Dep => Arg where
    ...

class Arg => Agent where
    ...

Upvotes: 0

Related Questions