Is there an easy way to make functor instances?

[woehr]

I hope this is an okay place to ask a question.

Basically, if I have a row type, say, "a" .== Foo x .+ "b" .== Bar x, and Foo and Bar are both Functors (or any class, really), is there an easy way to map over the entire structure and get a result of "a" .== Foo y .+ "b" .== Bar y?

I've been trying to use map and transform, but have had no success using them so far (my type-level experience is limited).

Thanks in advance!

[dwincort]

Hi,

This is a totally fine place to ask a question like this. And it's a tricky one!

In the current setup, there's no easy way to do what you're asking, but I just played around with it for a bit and made a new BiForall class that has a biMetamorph function, and with it, I was able to write mapF, which I think does what you want. With it, you can write:

-- | A sample record like the one you mentioned
r = #a .== Just (2 :: Int) .+ #b .== [True]

-- | A function that 'show's the value in the functor
foo :: (Functor f, Show a) => f a -> f (Const String a)
foo x = fmap (Const . show) x

and then:

> Rec.mapF @Functor @Show @(Const String) @("a" .== Maybe .+ "b" .== []) @("a" .== Int .+ "b" .== Bool) foo r
#a .== Just (Const "2") .+ #b .== [Const "True"]

If this is useful to you, I'll try to clean it up and commit the code.

[woehr]

This is very interesting! I'll have to play around with it and see what I can do with it.

I did manage to get a working prototype of what I am after, which are reusable "Data types a la carte"-style constructors using row-types (here: https://gist.github.com/woehr/a24a363465aef345deb695fdf3cef000). I managed this by shamelessly using the same approach as http://hsyl20.fr/home/posts/2018-05-22-extensible-adt.html. Indeed, I was originally using this library, but the compile times started to be come unbearable with larger variants. (I don't think what I've implemented will hurt compile times, but I'm still new to type level programming like this, so I'm not 100% sure).

I am unsure, however, whether this approach is a good fit for row-types because I'm "manually" poking around the Row internals. Perhaps BiForall could be used more effectively instead.

Edit:
In the approach demonstrated in the gist (now updated), operations on data types are declared as type classes with appropriate constructors implementing instances if they support the operation. While flexible, this approach requires quite a bit of boiler-plate that I hope can be eliminated.

I apologise for the rambling and open-ended question. I'm going to experiment with Biforall now. Suggestions welcome. :)

[dwincort]

Interesting! I have some questions and thoughts.

So, are you saying you were initially using just the standard row-types library, but the compile times got really bad? How large were your variants? I've found that one thing that can make a big difference is how two row types are joined together (that is, associativity has no bearing on behavior, but it definitely affects performance), so you might be able to get better performance by tweaking the syntax of your definitions.

I'm really intrigued and happy that you're using variants. Most people are only interested in records, so I haven't done much work on variants. For instance, Forall has a function metamorph' which is designed for variants, but I didn't even put in a biMetamorph'. Perhaps I should!

Unfortunately, "manual poking around the internals" is pretty necessary right now to do interesting behaviors with row-types. If you look at the definitions of erase, map, transform, etc., they all use the unsafe functions, and I specifically expose them in the interface so that users can write their own functions like this.

The design of Forall is an attempt to get rid of boilerplate. Rather than having type classes for each of map, erase, etc., there is just the one type class Forall that captures all of that behavior. Perhaps you can find a similar way to reduce the boilerplate in your code.

The reason BiForall would be necessary over Forall is if you were making heterogeneous lists. Since you're not, that power isn't necessary. In fact, you're really close to just being able to use Forall -- the only reason you can't is because there's no type level flip. That is, you have:

newtype VarWrapF (r :: Row (* -> *)) x = VarWrapF {unVarF :: Var (ApplyRow x r)}

Clearly, the x needs to be the final parameter so that you can make this a Functor instance. However, if you had written:

newtype VarWrapF x (r :: Row (* -> *)) = VarWrapF {unVarF :: Var (ApplyRow x r)}

then this would be an easy candidate for metamorph (your logic in lines 56-68 of your gist would be much the same, but instead of writing recursive instances, you would use metamorph to write it as a single function). It makes me think maybe we should introduce Forall2, which would allow an extra type parameter after the row type or something. It might be rather complicated though.

[woehr]

So, are you saying you were initially using just the standard row-types library, but the compile times got really bad?

I meant the compile times of the library discussed in the linked blog. I haven't had any compile length issues with row-types yet.

your logic in lines 56-68 of your gist would be much the same, but instead of writing recursive instances, you would use metamorph to write it as a single function

This would be very convenient since every operation implemented as a type class requires a similar instance (for example, OverList in the gist).

[dwincort]

Of course, if we can use metamorph for VarWrapF when the row type is the second argument, we can use some newtype trickery to make it work for your version:

-- This is the type you've already defined
newtype VarWrapF (r :: Row (* -> *)) x = VarWrapF {unVarF :: Var (ApplyRow x r)}
deriving instance Forall (ApplyRow x r) Eq => Eq (VarWrapF r x)
deriving instance Forall (ApplyRow x r) Show => Show (VarWrapF r x)

-- Some newtype helpers
newtype VarWrapF' x (r :: Row (* -> *)) = VarWrapF' {unVarF' :: Var (ApplyRow x r)}
newtype FlipApp (a :: *) (f :: * -> *) = FlipApp (f a)

instance Forall r Functor => Functor (VarWrapF r) where
  fmap :: forall r a b. Forall r Functor => (a -> b) -> VarWrapF r a -> VarWrapF r b
  fmap f = VarWrapF . unVarF' . go . VarWrapF' . unVarF
    where
      go = metamorph' @_ @r @Functor @(VarWrapF' a) @(VarWrapF' b) @(FlipApp a) Proxy doNil doUncons doCons
      doNil = impossible . unVarF'
      doUncons l = (FlipApp +++ VarWrapF') . flip trial l . unVarF'
      doCons :: forall ℓ f ρ. (KnownSymbol ℓ, Functor f)
             => Label ℓ -> Either (FlipApp a f) (VarWrapF' b ('R ρ)) -> VarWrapF' b ('R (ℓ :-> f ': ρ))
      doCons l (Left (FlipApp x)) = VarWrapF' $ unsafeMakeVar l $ f <$> x
      doCons _ (Right (VarWrapF' v)) = VarWrapF' $ unsafeInjectFront v

I'm not sure why I didn't think of that earlier.

[woehr]

Thanks for showing me how fmap can be implemented with metamorph'. My apologies for not responding, I haven't had a chance to work on this recently.

[woehr]

Me again... I hope it's okay for me to solicit feedback from this thread.

I've gone ahead and wrapped up what I was asking about in this thread into its own package, and would love to get some feedback before I release it to the wider world (especially if I'm using/abusing row-types appropriately).

The repo is at https://github.com/woehr/open-adt and I've written documentation and a tutorial module which I've uploaded at https://woehr.github.io/open-adt/.

Thanks!

[dwincort]

Cool! I'll definitely take a look, but I may not get to it for a week or two.

[woehr]

Thank you, and whenever you get to it is fine, of course. I greatly appreciate the feedback.

[dwincort]

I like it! It took me a bit to really get what you're trying to do (I don't have that much experience with recursion schemes, but reading this forced me to learn quickly), but it's pretty interesting, and it's a neat use case for row types.

I also looked specifically at the implementations of some of the functions (like varFAlg, reduceVarF, and the VarF functor instance), and they look good. It's cool that reduceVarF, despite its crazy type constraints, really just comes down to a multiTrial followed by caseOn, and I'm glad that you were able to use metamorph' instead of multiple type class instances on the internals of Var. I mean, sure, using metamorph' isn't always pretty, but it's nicer than the alternative.

Cool stuff!

[woehr]

Thank you so much for the feedback! It's very reassuring to get the positive feedback.