Java: binary-search;binary-search-tree;custom-set;linked-list;simple-linked-list: use generics?

[jtigger]

linked-list's tests only insert and expect integers. However, the tests force the practitioner to generify the class.

We should:

1. remove type variables from the class signature in the tests and either expect Number or Integer
2. or expand the test suite to put all kinds of objects in the collection.

What do you think?

[matthewmorgan]

@jtigger I think the use of generics is a good idea. We don't use them much in this track, and it's a key feature of the language. I think we should go 'all in' for generics here.

[stkent]

@jtigger neither of these options seem to be consistent with our recent discussion on binary-search?

@matthewmorgan good point, but how should we handle existing canonical test data? Add tests above and beyond the canonical tests? PR into the canonical test data with new tests that use different data types for all tracks, or for statically typed tracks only?

[jtigger]

@stkent said:

@jtigger neither of these options seem to be consistent with our recent discussion on binary-search?

Ahhh... my apologies, Stuart. I was not paying close enough attention / thinking holistically enough to catch the fact that the type variable was being required by the test suite. In my comments in that discussion, I was focused on the example code, not the test.

Whether or not the example code uses more language features than are strictly required by the test suite, I currently believe is largely an implementation detail. If the contributor wants to write a super generic solution... as long as it passes the tests and at least covers the behavior, I'm personally not too terribly concerned... I'm sure there's a length to the leash, but I haven't seen it yet.

But the tests themselves.... well! That's another story! I think we should be strict and intentional in the tests as they are the heart of the user experience on the track.

Did I clear things up?

[jtigger]

I see this is also the case for binary-search-tree... and there are other collections like simple-linked-list and custom-set. I guess this question is in three parts:

1. should we use generics (especially in exercises that call for creating a collection)?
2. if so, should we do it for exercise X?
3. if so, should we extend the test coverage on our own, or should we also submit back to x-commons?

I'm hearing rough consensus that the answer to 1 is "YES!"

[stkent]

@jtigger nicely summarized, thank you! Very clear :) And my answer for part 1 of the question would indeed be yes! Part 2 is probably yet another decision that is dependent on #142 (still planning on getting to that over the weekend; triaging another OS project of mine at the moment), and we could ask part 3 in x-common now to see how other tracks feel. There may be other languages that have already explored this path some?

[jtigger]

Doing some homework on this...

Java

There's some history/prior conversation around generics on this track (even including yours truly).

• In #99 we specifically generified simple-linked-list ... though we didn't add tests to exercise that feature.
• in #105, there was some confusion and real back-and-forth on the same exercise... although the confusion seemed to stem from why we are apparently dipping our toe in the generic waters (through the asArray() method) but not fully supporting generics. I've inadvertently revived the question with #229.

X-Common

exercism/x-common#488 notes that some circular-buffer implementations use generics. It's exactly the same kind of question we're entertaining here.

Objective-C

Looks like the Objective-C camp went "all in" on generics: exercism/xobjective-c#45. In that issue, @kytrinyx does poke at the added complexity and looks like Mr. Jimenez (@masters3d) opted to pull back on the first so many exercises.

C

• Avoids generics in binary-search, binary-search-tree
• Implements generics in custom-set, linked-list, simple-linked-list.

[javaeeeee]

Some programming languages, as well as earlier Java versions, do not have Generics. So, exercise descriptions may mot contain references to it, as well as test specifications, but it seems like a good idea to prod a learner to explore new language features.

It might not be a problem if such exercises are not at the beginning of a track. Also, one can submit whatever solution, may be containing only the method _main()_ and learn how others solved the problem.

In addition, one can learn from JCP where different implementations of the same JSR innovate on their own, they add new features on their own, which can later be added to the JSR. So, various implementation of exercises can be used to update test descriptions. Not necessarily right now.

Maybe using generics in some exercises is YAGNI, but adding some unnecessary functionality using Generics is not high cost and it teaches one about Java as well.

As to tests, for example, The C# implementation for list-ops contains some tests for different data types, like Integer, String, and List, so the Java track would not be the first if tests for different data types are added. Also, not all exercises have test descriptions, so it's time to come up with proposals.

[stkent]

Having watched a Java learner go through these exercises, I will say that requiring support for but not exercising generics causes confusion. I'd recommend we update the tests where possible.

[jtigger]

Having watched a Java learner go through these exercises, ...

... you wouldn't be referring to a professor friend of yours, would you?!!? :)

I will say that requiring support for but not exercising generics causes confusion. I'd recommend we update the tests where possible.

... and by that do you mean that we should explicitly exercise generics?

[stkent]

🎓 😉

I propose that for exercises whose tests force implementations with support for generic types we:

1. update the tests to exercise those generic types if possible;
2. remove the requirement to support generic types if not

in that order.

[jtigger]

Here are the difficulty rankings of the exercises in question:

• linked-list (6)
• binary-search (6)
• simple-linked-list (7)
• binary-search-tree (7)
• custom-set (10)

Seems like at least the last three in that list should be massaged into clear requirements for generics (including, perhaps, a short introduction to generics and references).

Two questions:

1. are there other exercises that I've missed?
2. Is "6" too early to introduce generics?
   
   
   
   • if so, would we adjust the difficulty of linked-list and binary-search if we _did_ insist on generic solutions?
   
   

[stkent]

• strain (5) uses generics but is scheduled for deprecation.
• list-ops (not ranked; end of track) uses generics.
• accumulate (5) uses generics but is scheduled for deprecation.

A good first step would seem to be to actually deprecate strain and accumulate right away. Then... I'd say linked-list is harder than minesweeper and robot-simulator (all are 6's), so we could probably stand some reordering there at least. Maybe moving linked-list to the _end_ of the 6's would be better. I also think binary-search is simpler conceptually for non-CS grads than linked-list, so maybe we execute a swap so that binary-search is the first, gentlest introduction to generics?

[Aside: I've been trying to encourage Rebecca to post issues here rather than telling me when she thinks an exercise is awkwardly placed... no luck yet, but I'll keep asking her!]

[jtigger]

[Aside: I've been trying to encourage Rebecca to post issues here rather than telling me when she thinks an exercise is awkwardly placed... no luck yet, but I'll keep asking her!]

Please do! Least she forget, she's made significant contributions in mere suggestions (e.g. more exercises with starter code); great source of ideas!

[jtigger]

A good first step would seem to be to actually deprecate strain and accumulate right away.

Agreed.

Then... I'd say linked-list is harder than minesweeper and robot-simulator (all are 6's), so we could probably stand some reordering there at least. Maybe moving linked-list to the end of the 6's would be better.

I have yet to do these, so I'll defer (with confidence).

I also think binary-search is simpler conceptually for non-CS grads than linked-list, so maybe we execute a swap so that binary-search is the first, gentlest introduction to generics?

Sounds very well reasoned, @stkent.

@FridaTveit, you good with all this?

[FridaTveit]

Sounds good :)

[rstockbridge]

I did simple-linked-list today, and I found the test suite's handling of generics extremely confusing. Specifically:

• Unlike linked-list, the class is not explicitly specified as generic in the test suite. My IDE did not make the class generic when auto-creating the class. I only realized generics were necessary when I looked closely at the tests canReturnListAsArray() (which expects an Integer array) and canReturnEmptyListAsEmptyArray (which expects an Object array).
• I tried to proceed with a non-generic class treating the input values as ints, but got tripped up trying to write asArray(), which has to return a generic type array to pass the tests. I couldn't figure out how to convert the values from ints to type T for array returned.
• (Side note: this was in interesting introduction into the difficulties of creating generic arrays in Java!)
• After consulting @stkent, I made the class generic, and was able to complete the exercise.

I think it would be very helpful to more closely align simple-linked-list with linked-list and make the class generic up front in the tests. I thought this exercise would be a simpler version of my solution to linked-list and was surprised at how much trouble I was having solving it.

[stkent]

So these exercises should be reviewed/cleaned up, it seems.

• [x] linked-list
• [x] binary-search
• [x] simple-linked-list
• [x] binary-search-tree
• [x] custom-set
• [x] list-ops

I'm starting out with linked-list now.

[stkent]

Taking list-ops next.

[FridaTveit]

From what I can tell, custom-set is slightly confusing in terms on generics at the moment. It requires the implementation to use generics but then only uses integers in the tests. But it's ticked in the list above to indicate that it has been cleaned up/reviewed. Is that a mistake? Or do you think it's fine as it is @stkent? :)

[stkent]

I think custom-set still needs a rewrite?

[FridaTveit]

I agree, I'll untick it in the list then and hopefully do a PR for it soon :)

[stkent]

@rstockbridge all these exercises featuring generics have been rewritten (thanks, @FridaTveit!). They have also been reordered within the track, if you would like to revisit them:

1. binary-search
2. linked-list
3. simple-linked-list
4. binary-search-tree
5. list-ops
6. custom-set