Data.Tree uses a list to represent the subtree rooted at a particular node. Is it possible to have two tree types, for example one which uses a list and another which uses a vector? I want to be able to write functions which don't care how the sub-tree is represented concretely, only that the subtree is traversable, as well as functions which take advantage of a particular subtree type, e.g. fast indexing into vectors.
It seems like type families would be the right tool for the job, though I've never used them before and I have no idea how to actually define the right family.
If it matters, I'm not using the containers library tree instance, but instead I have types
data Tree a b = Node a b [Tree a b] deriving (Show, Foldable, Generic)
and
data MassivTree a b = V a b (Array B Ix1 (MassivTree a b))
where the latter uses vectors from massiv.
You could use a typeclass - in fact the typeclass you need probably already exists.
Consider this:
data Tree t a = Tree a (t (Tree t a))
Argument t is a higher-kinded type which represents a container of as.
Now define a set of Tree operations, constrained on Traversable like so:
:: (Foldable t) => Tree t a -> b
And you can now create and manipulate trees that use any Foldable. You would need to choose the right typeclass for the set of operations you want - Functor may be enough, or you may want Traversable if you are doing anything with monadic actions. You can choose the typeclass on a per-function basis, depending on what it does.
You can now define Tree types like so:
type ListTree a = Tree [] a
type MassivTree r ix a = Tree (Array r ix) a
You can also define instance-specific functions, with access to a full range of functionality:
:: ListTree a -> b
-- or
:: Tree [] a -> b
Happy Haskelling!