HList selector that also choose children

[Francois Armand]

Hello,

I'm starting to look at Shapeless, and the possibilities seem amzing... But for now, I'm a little lost.

So that's my problem: I would like to implement a method alike "select" on HList, but:

1. that also select children instance, so that if hlist.select[Foo] is used, and hlist contains a bar: Bar with Bar extends Foo, then bar is returned;
2. is a compilation error if not exactly one instance of the selected type is in the hlist, so that: ("foo" :: "bar" :: HNil).select[String] is a compilation error.
   

Is this possible ? I believe that at least the first one is rather simple (I mean, for someone literated in shapeless things). I'm also really interested in any documentation of resources that could help myself undertanding Shapeless.

Thanks fo any information,

[Alois Cochard]

Hi Francois,

About 1. maybe related to covariance, I'll give it a try as I have to test some stuff around that.

2. is definitely possible imo, you can try to start trying to implement it by coping the Select type class and work on changing the implicits

Cheers,

Alois

[Travis Brown]

Hi Francois, Alois, (and Miles),

Is there any reason not to change FilterAux to work like this?

https://github.com/travisbrown/shapeless/commit/1169e8a56ce1811ac39a7765024657c5c5d19390#commitcomment-2686334

This would allow a very clean solution to this problem (given in the comment there), and seems easy enough to motivate for other reasons.

Travis

--
You received this message because you are subscribed to the Google Groups "Shapeless Dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to shapeless-de...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Alois Cochard]

Hi Travis,

Can't you make it work without any change to FilterAux but instead comibing with LUBConstrain?

(like proposed here by Miles: https://groups.google.com/d/msg/shapeless-dev/GwNgqeiAFY8/ukosHfBdr7IJ)

Not sure if possible in this specific case, BTW I'm all for supporting subtype in filter/filterNot ;)

Cheers

Alois

[Miles Sabin]

On Mon, Feb 25, 2013 at 12:13 PM, Travis Brown
<travisro...@gmail.com> wrote:
> Hi Francois, Alois, (and Miles),
>
> Is there any reason not to change FilterAux to work like this?
>
> https://github.com/travisbrown/shapeless/commit/1169e8a56ce1811ac39a7765024657c5c5d19390#commitcomment-2686334
>
> This would allow a very clean solution to this problem (given in the comment
> there), and seems easy enough to motivate for other reasons.

Assuming that doesn't break any tests, then no, no reason not to
change it to work like that. PR will be merged as soon as it arrives.

Cheers,


Miles

--
Miles Sabin
tel: +44 7813 944 528
skype: milessabin
gtalk: mi...@milessabin.com
g+: http://www.milessabin.com
http://twitter.com/milessabin

[Travis Brown]

I'd have two concerns about rolling this out right away:

1. Even though that commit on my demo branch doesn't break any tests, it's a pretty big change in behavior—it's not inconceivable that someone out there is using code that expects filter not to return subtypes of the query type. I'm not, and the behavior in my version makes good sense to me, but it isn't an insignificant change.
2. If we make this change to FilterAux, we'll also need at the very least to change FilterNotAux for consistency, and there'd be a strong argument for making Remove and Replace and Select match as well. Which makes the possibility of breaking other people's code even more of a problem.

I do think the second part of my change—ensuring that you can't create instances like FilterAux[Foo :: Foo :: HNil, Foo, Foo :: HNil]—could be implemented immediately (it could be done independently of the first part by using =:!= instead of <:!<). I was actually pretty surprised this morning to see that Shapeless would happily pull these things out of the air.

Travis

[Miles Sabin]

On Mon, Feb 25, 2013 at 3:56 PM, Travis Brown
<travisro...@gmail.com> wrote:
> I'd have two concerns about rolling this out right away:
>
> Even though that commit on my demo branch doesn't break any tests, it's a
> pretty big change in behavior—it's not inconceivable that someone out there
> is using code that expects filter not to return subtypes of the query type.
> I'm not, and the behavior in my version makes good sense to me, but it isn't
> an insignificant change.
> If we make this change to FilterAux, we'll also need at the very least to
> change FilterNotAux for consistency, and there'd be a strong argument for
> making Remove and Replace and Select match as well. Which makes the
> possibility of breaking other people's code even more of a problem.

Other options:

* We could introduce a new (pair of) method(s) which also filter subtypes.

* We could introduce a single new method which normalizes subtypes to
a common supertype, ie. Foo :: Bar :: String :: HNil => Foo :: Foo ::
String :: HNil, then use the existing Filter/FilterNot on the result
of that.

* We could and come up with a more general idea of type-level
predicate and have a revise filter work in terms of that.

> I do think the second part of my change—ensuring that you can't create
> instances like FilterAux[Foo :: Foo :: HNil, Foo, Foo :: HNil]—could be
> implemented immediately (it could be done independently of the first part by
> using =:!= instead of <:!<). I was actually pretty surprised this morning to
> see that Shapeless would happily pull these things out of the air.

Agreed. Both with the proposal and the surprise.

[Alois Cochard]

On Monday, 25 February 2013 16:37:20 UTC, Miles Sabin wrote:

On Mon, Feb 25, 2013 at 3:56 PM, Travis Brown
<travisro...@gmail.com> wrote:
> I'd have two concerns about rolling this out right away:
>
> Even though that commit on my demo branch doesn't break any tests, it's a
> pretty big change in behavior—it's not inconceivable that someone out there
> is using code that expects filter not to return subtypes of the query type.
> I'm not, and the behavior in my version makes good sense to me, but it isn't
> an insignificant change.
> If we make this change to FilterAux, we'll also need at the very least to
> change FilterNotAux for consistency, and there'd be a strong argument for
> making Remove and Replace and Select match as well. Which makes the
> possibility of breaking other people's code even more of a problem.

Other options:

* We could introduce a new (pair of) method(s) which also filter subtypes.

* We could introduce a single new method which normalizes subtypes to
a common supertype, ie. Foo :: Bar :: String :: HNil => Foo :: Foo ::
String :: HNil, then use the existing Filter/FilterNot on the result
of that.

I like this approach, it's composable and could be reused in other place too... best of all that would make possible to keep supporting both behavior without (hopefully) breaking code that use current version!

As when using LUB with FilterNot.

[Grant Beaty]

I've used the below code in my project, and it caused some pretty horrendous compilation times, up to ten minutes on four files. It seems to get worse as you add more elements which are removed by the filter. Elements which aren't removed by the filter don't have much of an affect.

If there's a better way to filter subtypes, please let me know. I'm filtering subtypes of Field.

/Grant

[Miles Sabin]

On Sun, Jun 23, 2013 at 5:17 PM, Grant Beaty <gbe...@gmail.com> wrote:
> I've used the below code in my project, and it caused some pretty horrendous
> compilation times, up to ten minutes on four files. It seems to get worse as
> you add more elements which are removed by the filter. Elements which aren't
> removed by the filter don't have much of an affect.

Is the code (or some reduction of it which still shows the excessive
compile times) available somewhere we could take a look at it?

[Grant Beaty]

Miles,

Here you go:

https://gist.github.com/gbeaty/5846987

The difference between compilation times of objects and vals is rather striking. I may move all my objects which use shapeless to vals, to see if that cuts down on compilation times for my whole project.

/Grant

[Miles Sabin]

Try putting explicit result types on all of your implicit methods and
see if that improves compilation times (my expectation is that it
will).

[Grant Beaty]

Miles,

I updated the gist with explicit result types and a "non-Aux" implementation. Neither had any affect on compilation times for me.

/Grant

[Paul Phillips]

On Mon, Jun 24, 2013 at 8:18 AM, Grant Beaty <gbe...@gmail.com> wrote:

I updated the gist with explicit result types and a "non-Aux" implementation. Neither had any affect on compilation times for me.

Nothing will impact compile times. Each element you add to the HList will double compile time after adjusting for a constant factor.

You're using a spectacularly inefficient machine for performing computation. It doesn't know how to efficiently implement "filter". It only knows how to traverse the implicit search space - exhaustively.

[Grant Beaty]

Yeah, I kind of gathered that. The offenders seem to be the inclusion of the "st: H <:< U" and "nst: H <:!< U" implicits which are not n shapeless's original filter implementation.

Simply removing the implicits and changing the first function to "implicit def hlistFilter1[H <: U, L <: HList, U, Out <: HList] ..." seems to fix all the issues and work fine. I wonder why the author used implicits in the first place?

Miles would you like a PR with this typeclass?

/Grant

[Miles Sabin]

On Mon, Jun 24, 2013 at 6:42 PM, Grant Beaty <gbe...@gmail.com> wrote:
> Yeah, I kind of gathered that. The offenders seem to be the inclusion of the
> "st: H <:< U" and "nst: H <:!< U" implicits which are not n shapeless's
> original filter implementation.
>
> Simply removing the implicits and changing the first function to "implicit
> def hlistFilter1[H <: U, L <: HList, U, Out <: HList] ..." seems to fix all
> the issues and work fine. I wonder why the author used implicits in the
> first place?

Interesting ... Travis? Any comments?

> Miles would you like a PR with this typeclass?

Well it does seem as though the compile times using filter in its
current form are unacceptably long, so quite possibly yes.

[Travis Brown]

Without that constraint you're able to generate FilterAux instances like this:

    implicitly[FilterAux[String :: String :: HNil, String, HNil]]

    implicitly[FilterAux[String :: String :: HNil, String, String :: HNil]]

Which doesn't make a lot of sense and can cause problems in certain circumstances.

It also makes the behavior consistent with FilterNotAux, where you prepend the current element to the output when you can find this evidence of inequality.

Travis

[Grant Beaty]

I wasn't thinking to replace the normal Shapeless Filter/Aux implementations, unless Miles want to I guess. I was just thinking a FilterSubs would be useful (I've needed it at least).

I see what you mean on over-generating Filter instances. Using your implementation this doesn't happen, but compilation is prohibitively slow. However it looks like simply adding the <: U type bound to the H type parameter in hlistFilter1 solves this issue, dropping compilation from 35s to 4s for me. So I guess we can have our cake and eat it too ;)

I've updated the gist with the latest FilterSubs code and some compilation tests:

https://gist.github.com/gbeaty/5846987

I'm still seeing a big difference in "object extends A" vs. "new A" instantiation with classes that take these implicits as constructor parameters. Compilation time goes from 4s with "new"s, to 12s with "object"s. Any idea if this is expected behavior?

/Grant

[Paul Phillips]

On Mon, Jun 24, 2013 at 2:48 PM, Grant Beaty <gbe...@gmail.com> wrote:

I'm still seeing a big difference in "object extends A" vs. "new A" instantiation with classes that take these implicits as constructor parameters. Compilation time goes from 4s with "new"s, to 12s with "object"s. Any idea if this is expected behavior?

It will be the expected behavior as soon as one looks at the implementation to see why it does that. I don't know why, offhand - the point is that we are outside the realm of anyone's conscious expectations. It's like taking a toy car on a journey to the moon. Maybe the car's plastic will make it through the Van Allen belt, maybe it won't - but regardless of outcome, there is no expected behavior. There is only observed behavior.

[Francois]

OK, so I come back to that after a long time. Thanks for all the other messages, they helped a lot.

Now, I'm able to write:

val myService = register.inject[SomeInterface with ChoiceMarker]

thanks to the code here: https://gist.github.com/fanf/6030588

And if I add better looked (or perhaps it was just added recently to Shapeless ?), the combination of the "unique" filter with unifySubtype gives me exactly what I wanted, modulo the type repetition:

  val s2 = register.unifySubtypes[SomeInterface].unique[SomeInterface]

Now, I'm going to see how bad the compilation performance are with a thousand services :)

Cheers,

-- 
Francois ARMAND
http://fanf42.blogspot.com
http://www.normation.com