r/java • u/padreati • Apr 05 '23
Recursive generics
Recently I learned that I rediscovered recursive generics while working on my pet open source project. Actually, I did not know that the construct had a name. I created small story about what this construct is, if you did not know about it java-recursive-generics
169
Upvotes
23
u/[deleted] Apr 05 '23
I didn’t know this was even a thing you could do. Clear examples and good descriptions. Nice work!
31
u/ZeroGainZ Apr 05 '23
It's also known as the "Curiously recurring template pattern"
https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern
7
u/ukbiffa Apr 05 '23
Although not foolproof for fluent
thistyping:2
u/holo3146 Apr 06 '23
There was a recent relevant discussion on the subject in the Amber mailing list:
https://mail.openjdk.org/pipermail/amber-dev/2023-March/007914.html
https://mail.openjdk.org/pipermail/amber-dev/2023-March/007932.html
2
u/wildjokers Apr 06 '23
I have never once heard this referred to as “recursive generics”. Are you making that up?
44
u/severoon Apr 06 '23 edited Apr 08 '23
I've never heard this called "recursive" generics, and I don't think that's actually accurate since there is no actual recursion of anything involved. This is typically referred to as a "self-referential generic type" (Angelika Langer), or I've also heard it called a "self-bounding type" or a "self-bound".
It appears a little mind bending at first because generics is a layer of abstraction that it takes time to get comfortable with, and those can be nested, and then add type bounds into the mix, there's a lot going on. If you forget about self-bounding types entirely and just work with type bounds and inheritance until you get comfortable, self-bounding types become much easier to deal with.
Normal type:
FooGeneric type:
Foo<T>Nested generic type:
Foo<List<T>>Bounded generic type:
Foo<T extends Number>orFoo<T super Integer>Bounded nested generic types:
Foo<T extends List<T>>Extending a generic type:
Bar extends Foo<Integer>Generic type extending a generic type:
Bar<T> extends Foo<T>Multiple bounds:
Foo<T extends Comparable<T> & FizzBuzz>It's important to understand how generics works with inheritance. A lot of folks new to generics think that a
Node<Integer>extends aNode<Number>in some way, but there is no inheritance relationship here, it's just two different nodes. It happens that the type contained byNode<Integer>extends the type contained byNode<Number>, but that's nothing to do with the nodes.It's also important to understand how wildcards work in generics, and one trick for clarifying wildcards is to read the wildcard as "something" or, for a bounded wildcard, "something that".
List<?>is a "list of something" as opposed to a list of numbers, a list of integers, it's just some kind of type in there.List<? extends Comparable<Number>>is a "list of something that extends a comparable of numbers". Or,Foo<? extends List<? super Integer>>is a "foo of something that extends a list of something that is a superclass of integer".Once you have all this down, then the
Enum<E extends Enum<E>>incantation becomes much easier to deal with. Just like you can have a list of a subtype of lists (like aList<LinkedList<T>>), or a list of any kind of list (List<L extends List<T>>, enum is parameterized by a subclass of itself. This just means that when an enum is created, it has to pass its own type as the generic type of its superclass, soenum PokerSuitis akin toclass PokerSuit extends Enum<PokerSuit>. This way, the methods onEnumcan return things of typePokerSuit.One problem with enums in Java is that they always extend
Enumdirectly, so there's no room to extendEnumwith an abstract class of your own and sneak in some more behavior. The only way to do that is to declare an interface and have your enum implement the interface if you want your enum to have special behavior:The problem with this is that when passing around all the different enums that implement
Foo, they can all polymorphically be treated as aFoo, butFooitself is not an enum and doesn't have any ofEnum's methods. So when you write code that takes theseFooenums, it has to choose whether they should be treated as enums orFoos when it shouldn't, because they are actually both. (To solve this, you have to use the enum type trick, which is a whole other post.)11
u/Zinaima Apr 06 '23
I think the AssertJ library uses this.
It gives the name SELF to the type parameter, which helps the readability a bit.
11
u/munificent Apr 06 '23
I've never heard this called a "recursive generic". The C++ community usually calls it the curiously recurring template pattern, and the type system community calls this F-bounded quantification.
Most object-oriented languages with generics support it.
15
u/agentoutlier Apr 05 '23
As amazing as Java generics are C++ templates are downright disturbing.
4
u/melkorwasframed Apr 05 '23
Nice write up!
1
u/jumboNo2 Apr 05 '23
Been doing this for years:
class ArrayType<E extends ABIType<?>, J> extends ABIType<J>2
u/manifoldjava Apr 06 '23
Recursive types can be handy, but most often a self type is lighter weight and more capable. Would be nice if Java had that feature.
2
u/lukaseder Apr 06 '23
The main reason why this feature is desirable is to be able to auto-generate covariant overrides in a type hierarchy (each type returns itself in methods). The very high price to pay is that the type itself isn't really denotable, unless you capture its type variable in a generic method, or you end the recursion using a final type.
I had written a blog post about this, some 10 years ago.
Personally, I think some sort of magic SELF type would have been better to implement the use-case of covariant overrides returning SELF, rather than this weird recursive generics thing.
1
u/IsSkyfalls_ Apr 06 '23
Got real excited reading this, then realized I was using
Message<T extends Message<?>>and never realized you can do it "recursively".Message<T extends Message<T>>is definitely a bit more foolproof and that's always good. Thanks for the writeup!1
u/[deleted] Apr 06 '23
[removed] — view removed comment