Reflection of heterogeneous promoted types back to values, compositionally

Question

I recently played with -XDataKinds and would like the created structure to be built using type families and bring it back to the level of values. I believe this is possible because the constituent components are very simple, and the terminal expressions are also straightforward.

Background

I would like to downgrade / flush simple pink Strings trees that become types of the Tree Symbol view (when using GHC.TypeLits.Symbol as a type level string). Here is my boilerplate code:

 {-# LANGUAGE DataKinds #-} import GHC.TypeLits import Data.Proxy data Tree a = Node a [Tree a] type TestInput = '[ 'Node "foo" '[ 'Node "bar" '[] , 'Node "baz" '[] ] , 'Node "bar" '[] ] 

This is a simple type-level petal that looks like this very detailed diagram:

  *-- "foo" -- "bar" | \_ "baz" \_ "bar" 

Attempt to solve

Ideally, I would like to go through this structure and give a 1 to 1 mapping back to values ​​of the form * , but it is not very obvious how to do this non-uniformly, while preserving the (necessary) instances due to overload.

vanila on #haskell suggested using type classes to bind two worlds, but that seems a bit more complicated than I thought. My first attempt attempted to encode the contents of a pattern match at the type level using an instance restriction, but the type associated with it (to encode the result * -kinded type of the mapping) was overlapping - obviously, the heads of the instances are somewhat ignored by the GHC .

Ideally, I would also like the reflection of lists and trees to be common, which seems to cause problems - he likes to use type classes to organize types / types.

Here is a non-functional example of what I would like:

 class Reflect (a :: k) where type Result :: * reflect :: Proxy a -> Result class ReflectEmpty (empty :: [k]) where reflectEmpty :: forall q. Proxy empty -> [q] reflectEmpty _ = [] instance ReflectEmpty '[] where instance ReflectEmpty a => Reflect a where type Result = forall q. [q] reflect = reflectEmpty -- | The superclass constraint is where we get compositional class Reflect (x :: k) => ReflectCons (cons :: [x]) where reflectCons :: PostReflection x ~ c => Proxy cons -> [c] instance ( Reflect x , ReflectCons xs ) => ReflectCons (x ': xs) where reflectCons _ = reflect (Proxy :: Proxy x) : reflectCons (Proxy :: Proxy xs) instance ( Reflect x , ReflectEmpty e ) => ReflectCons (x ': e) where reflectCons _ = reflect (Proxy :: Proxy x) : reflectEmpty (Proxy :: Proxy e) 

...

There is something in common in this code. Here is what I see:

• I need some form of look to find out the result of a higher kind of reflection for the general type of displaying a list of types - a PostReflection function of type
• I need to create and destroy Proxy on the fly. I am not sure that this will not compile at the moment, but I am not sure that the types will be unified as I expect.

But this hierarchical element looks like the only way to capture a heterogeneous grammar, so this may still be the beginning. Any help with this would be great!

Answer 1

lazy decision

Install the singletons package:

 {-# LANGUAGE TemplateHaskell, DataKinds, PolyKinds, TypeFamilies, ScopedTypeVariables, FlexibleInstances, UndecidableInstances, GADTs #-} import GHC.TypeLits import Data.Singletons.TH import Data.Singletons.Prelude import Data.Proxy $(singletons [d| data Tree a = Node a [Tree a] deriving (Eq, Show) |]) reflect :: forall (a :: k). (SingI a, SingKind ('KProxy :: KProxy k)) => Proxy a -> Demote a reflect _ = fromSing (sing :: Sing a) -- reflect (Proxy :: Proxy (Node "foo" '[])) == Node "foo" [] 

And you're done.

Unfortunately, the library is rarely documented and quite complex. I recommend viewing the additional project page for additional documentation. I am trying to explain the basics below.

Sing is a data family that defines singleton representations. Singletones are structurally the same as disparate types, but their values ​​are indexed by the corresponding raised values. For example, singleton data Nat = Z | S Nat data Nat = Z | S Nat will be

 data instance Sing (n :: Nat) where SZ :: Sing Z SS :: Sing n -> Sing (S n) 

singletons is a template function that generates singletones (and also removes derived instances and can also raise functions).

SingKind is essentially a good class that provides us with the type Demote and fromSing . Demote gives us the corresponding non-overlapped type for the raised value. For example, Demote False is Bool , and Demote "foo" is Symbol . fromSing converts a singleton value to the corresponding unallocated value. So, fromSing SZ is equal to Z

SingI is a class that reflects raised values ​​into solid values. Sing is its method, and sing :: Sing x gives the same value of x . This is almost what we want; to complete the definition of reflect we need to use fromSing on Sing to get an unallocated value.

KProxy - Export Data.Proxy . This allows us to capture view variables from the environment and use them within definitions. Please note that instead of KProxy you can use any type of supported type (* → *). For more on data type promotion, see This.

Note that there is a weaker form KProxy by type, for which KProxy is not required:

 type family Demote (a :: k) type instance Demote (s :: Symbol) = String type instance Demote (b :: Bool) = Bool 

So far so good, but how can we write an instance for the removed lists?

 type instance Demote (xs :: [a]) = [Demote ???] 

Demote a not allowed, of course, because a is a view, not a type. Therefore, we need KProxy to be able to use a on the right side.

Stand alone solution

This happens similarly to the singletons solution, but we intentionally skip single point representations and go directly to reflection. This should be somewhat more productive, and we could even learn a little in this process (I, of course, did!).

 import GHC.TypeLits import Data.Proxy data Tree a = Node a [Tree a] deriving (Eq, Show) 

We implement type dispatching of the open type and provide a type synonym for convenience:

 type family Demote' (kparam :: KProxy k) :: * type Demote (a :: k) = Demote' ('KProxy :: KProxy k) 

The 'KProxy :: KProxy k picture is that we use 'KProxy :: KProxy k whenever we want to specify the form k .

 type instance Demote' ('KProxy :: KProxy Symbol) = String type instance Demote' ('KProxy :: KProxy (Tree a)) = Tree (Demote' ('KProxy :: KProxy a)) type instance Demote' ('KProxy :: KProxy [a]) = [Demote' ('KProxy :: KProxy a)] 

Doing the reflection pretty right now:

 class Reflect (a :: k) where reflect :: Proxy (a :: k) -> Demote a instance KnownSymbol s => Reflect (s :: Symbol) where reflect = symbolVal instance Reflect ('[] :: [k]) where reflect _ = [] instance (Reflect x, Reflect xs) => Reflect (x ': xs) where reflect _ = reflect (Proxy :: Proxy x) : reflect (Proxy :: Proxy xs) instance (Reflect n, Reflect ns) => Reflect (Node n ns) where reflect _ = Node (reflect (Proxy :: Proxy n)) (reflect (Proxy :: Proxy ns))