[Haskell-cafe] Runtime selection on types while capturing a dictionary?

[Tom Ellis]

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.