Can trees be generalized to allow any traversable sub-tree?

Question

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.

Answer 1

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!