You would need to add the required implementations, but there's really no way around that since the logic has to go somewhere.
And as soon as you start actually dispatching on multiple arguments, using sum types to solve the same prolem quickly turns into spaghetti.
Sure there is. If I have a function that takes a Foo and a Bar, and it calls a generic method on them, the generic method must have methods that cover the real subtypes of Foo and Bar. If someone had created subtypes of Foo and Bar and defined methods on all the generic methods that they knew about, and now you create a new generic method, you have absolutely broken the interface just as much as adding a new method to Iterable in Java.
Assuming you're running a version of Java that supports default implementations, which may often be used to avoid breaking the interface.
Sum types are a different story, as you would have to dive into existing code.
It does, more or less, since any subtype will have to implement the "accept" method for the visitor, which has been defined to only 'accept' the values that can be represented by the GADT. Any subtype will need to define how its possible values map to that of the supertype.
Here is an example: https://github.com/rust-lang/regex/blob/master/regex-syntax/...
The idea here is that you can have an opaque interface. Then, adding new implementations of that interface is very easy. But, if you want to extend the interface, you need to modify all of the existing implementations. Multiple dispatch suffers of this problem just as much as single dispatch.
In the other case, you have a transparent interface - anyone can build code based on your data type. But, if you add more cases to your data type, anyone who had functionality built on it needs to take into account the new cases.
I think that this is in inherently an unavoidable problem. You can of course expose both kinds of constructs in your language, but you can't make interface implementation easily modifiable, and you can't make sum types easily extensible. The programmer ultimately has to choose the one that they believe will best capture the domain and its probable evolution.
What multiple dispatch can do is take some cases where sum types are obviously preferable to single dispatch (operations on related objects) and apply the interface abstraction to those cases as well (without reaching for horrible solutions like the visitor pattern).
Edit: thinking a bit more about the article, what they are showing is that you can essentially use the visitor pattern (and multiple dispatch) to implement GADTs instead of using them for regular multiple dispatch with inheritance. Basically, you can use them bring completely disparate types under the same umbrella, just like a GADT. I'm not sure that this still allows subtyping of that GADT as if it were a regular class.