It's hard to know exactly what to suggest but I can offer some ideas. Firstly, you defined a tree like this: data Graph (IntMap Node) (IntMap Edge) data Forest = Forest Graph {- Assert that the Graph is a Forest -} data TreeViaGraph = Tree Forest {- Assert that the Forest is a Tree -} Then you said you wanted perhaps to also define graphs like this data TreeViaBranching = Leaf {parent :: Maybe Tree } | Internal { left:: Tree, right:: Tree, parent:: (Maybe Tree)} and wanted to be polymorphic over the type of graph. I probably won't be polymorphic the way you're thinking. Instead I'd just define data EitherSortOfTree = MkTreeViaGraph TreeViaGraph | MkTreeViaBranching TreeViaBranching Now you can define everything in terms of EitherSortOfTree. Doesn't that do what you want? You can also parametrize EitherSortOfTree so the presence of absence of certain sorts of annotations is observable at the type level. I would really suggest avoiding shenanigans with existential type classes, by which I mean wrapping them in GADTs. There are probably some cases where that's the right thing to do. I doubt yours is one such. If you really think it is then please come back with some additional info. Regarding the constraint that all node time trees should be rooted, then you can use this parametrization data EitherSortOfTree nodeTimes roots = MkTreeViaGraph (TreeViaGraph, nodeTimes, roots) | MkTreeViaBranching (TreeViaBranching, nodeTimes, roots) and define newtype NodeTimedRootedEitherSortOfTree = MkNodeTimedRootedEitherSortOfTree (IntMap Double) [NodeId] I wouldn't try to enforce the constraint that all node time trees should be rooted on the base type (EitherSortOfTree) itself. That seems like a higher level property that's better represented with a newtype. Hope that helps, Tom On Mon, Oct 14, 2024 at 09:19:56AM -0500, Benjamin Redelings wrote:
On 10/9/24 10:11 AM, Benjamin Redelings wrote:
Interesting! And thanks. I've been able to move the labels into the Graph class, and just use () as the label type when I don't want labels. Somehow I was expecting a Haskell mailing list to recommend something involving DataKinds.
The other augmentations are a bit more tricky. The tree can have either a BranchLength augmentation OR a NodeTime augmentation, but not both. The NodeTime augmentation only makes sense when the tree is rooted. Additionally, it makes sense on rooted forests and directed acyclic graphs. When using the NodeTime augmentation, we can CALCULATE the branch lengths as the time difference between the nodes at the two ends of a branch. This provides some motivation to make the branchLength function polymorphic, so that some of the downstream code can be agnostic as to whether the branch lengths are directly augmented, or computed from NodeTimes. And then there is also a BranchRate augmentation that only makes sense if we have a NodeTime augmentation.
I think your ADT makes more sense than just creating a lot of (AddAugmentationX ExtraInfo Graph) data types. So, I'll have to think how to do that.
On the other hand, I would like to retain some polymorphism. For example, it would be nice to allow multiple tree representations. Sometimes a generic graph is what you want, but in other cases the tree-generation process makes a data structure like
data Tree = Leaf {parent :: Maybe Tree } | Internal { left:: Tree, right:: Tree, parent:: (Maybe Tree)}
more natural. So, having an IsGraph *class* versus just a single Graph data structure seems valuable.
QUESTION: Given that, can you expand on what counts as a type-class "shenanigan"? I fully agree that the class structure and the data type structure isn't very good yet. (It was implemented in haste to make something "just work". The standard format for printing trees -- Newick format -- really prints rooted trees, so I ended up creating a 'type family Rooted t' to make a rooted tree type from an unrooted tree type. That seems very hacky.) But I would like to retain some generality across common features between NodeTime and BranchLength augmented trees, as well as (perhaps) generality across different implementations of Graph / Tree.
QUESTION: For the constraint that a NodeTime tree should be rooted, do you think I should encode this constraint at the data-type level, or at the function level? I was initially thinking of encoding this at the data type level, so that you couldn't construct a tree with node times that was not rooted. But I suppose one could simply make all the functions that USE node-time trees require some kind of Rooted constraint by calling a function like 'parent node'. This would decouple the Rooted/Unrooted augmentation from the BranchLength / NodeTime / Nothing augmentation. Thoughts?
-BenRI
On 10/7/24 6:13 PM, Tom Ellis wrote:
On Mon, Oct 07, 2024 at 05:38:30PM -0400, Benjamin Redelings wrote:
I'm new to Haskell, and I'm writing a class for evolutionary trees. Since I'm new to Haskell, trying to encode information at the type level is new to me. In C++ I'd use runtime checks to ask whether (for example) a tree is rooted. Or I'd have the getRoot function return Maybe NodeID and then make the methods for checking if a branch points rootward throw an exception if the tree is unrooted. I think I'd just do
data AugmentedTree roots lengths labels = MkAugmentedTree { tree :: Tree, labels :: labels, roots :: roots, lengths :: lenghts }
and then just do stuff like
type FullyAugmentedTree = AugmentedTree [NodeId] (IntMap Double) (IntMap (Maybe l)) type PartiallyAugmentedTree = AugmentedTree [NodeId] () (IntMap (Maybe l))
For rootedness-independence I strongly recommend against any type class shenanigans. Instead you can do
data PossiblyRootedTree lengths labels where RootedTree :: AugmentedTree [NodeId] lengths labels UnrootedTree :: AugmentedTree () lengths labels
and then
isRooted :: PossiblyRootedTree lengths labels -> Bool isRooted = \case RootedTree {} -> True UnrootedTree {} -> False
(but `isRooted` is not really very useful compared to just pattern matching every where you need to know.)
Tom _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.
Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.