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

[Benjamin Redelings]

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.