{-# LANGUAGE QuantifiedConstraints, StandaloneDeriving, ExistentialQuantification, RankNTypes, UndecidableInstances, FlexibleInstances, ExplicitForAll #-} module Data.Hextra.Tree.Generalized where import Data.Bifunctor -- TODO Consider renaming these data XTree f a = XNode (f a (XTree f a)) -- ^ Extremely general tree type -- Generalizes all other examples, -- but is cumbersome to use. -- For example, type Bush [] = XTree G where data G x y = G x [y] -- Split 1 [] = XNode (G 1 []) -- Split 1 [Split 2 [], Split 2 [], Split 2 []] = -- XNode (G 1 [XNode (G 2 []), XNode (G 2 []), XNode (G 2 [])]) unXNode :: forall f a. XTree f a -> f a (XTree f a) unXNode (XNode f) = f -- ^ Unwraps an XTree's XNode. data YTree f g a = YNode (f a (g (YTree f g a))) -- ^ Slightly less general tree type -- Much more useful in general, though unYNode :: forall f g a. YTree f g a -> f a (g (YTree f g a)) unYNode (YNode f) = f -- ^ Unwraps a YTree's YNode. instance (Bifunctor f, Functor g) => Functor (YTree f g) where fmap f (YNode m) = YNode \$ bimap f (fmap (fmap f)) m deriving instance ( Show a, forall x y. (Show x, Show y) => Show (f x y), forall z. Show z => Show (g z) ) => Show (YTree f g a) deriving instance ( Read a, forall x y. (Read x, Read y) => Read (f x y), forall z. Read z => Read (g z) ) => Read (YTree f g a) deriving instance ( Eq a, forall x y. (Eq x, Eq y) => Eq (f x y), forall z. Eq z => Eq (g z) ) => Eq (YTree f g a) deriving instance ( Ord a, forall x y. (Ord x, Ord y) => Ord (f x y), forall z. Ord z => Ord (g z), Eq a, forall x y. (Eq x, Eq y) => Eq (f x y), forall z. Eq z => Eq (g z) ) => Ord (YTree f g a) -- ^ This instance is very weird due to the weirdness that is quantified constraints. -- See https://gitlab.haskell.org/ghc/ghc/-/issues/18364#note_283145 for more details.