"OOP solution is to use inheritance. Typical ML solution is to use type-classes."
Yes, type classes can "work" to help a NonEmptyList degenerate to a normal List of some sort, if the function accepting the list accepts the type class instead of a hard-coded List. Unfortunately, at least for this exact task, taking hard-coded types is pretty common. I've sometimes wondered about the utility of a language that provided all of its most atomic types solely as typeclasses within its standard library, so that calling for a "List a" or "[a]" automatically was turned into the relevant type class.
Inheritance doesn't actually work here. I assume you mean inheriting a NonEmptyList from some sort of List, from the perspective of a user facing a language that has a standard List and they want to create a NonEmptyList that things taking List will accept. Unfortunately, that is a flagrant violation of the Liskov Substitution Principle and will create architecturally-fragile code.
Compilers can't enforce the LSP (with anything short of the dependently typed code you mention), so you can bash out a subclass that will throw an exception if you try to take the last element out of a NonEmptyList or violate the rules some other way, and if you pass your new NonEmptyList to something that happens to not do anything broken, you may get away with it, but by the standards of OO theory you're definitely "getting away" with something, not solving the problem.
I haven't studied this extensively beyond just thinking here for a moment, but I don't think you can LSP-legally go the other way either. A subclassed List can't revoke a parent's NonEmptyList property that the list is guaranteed to not be empty. Again, you can bash the methods into place to make it work, but as this is a very basic standard library sort of thing for a language it really needs to be right.
Edit: Yes, it's certainly illegal. You can take a List inherited from the NonEmptyList, have it be empty, but you have to be able to pass it to something accepting a NonEmptyList, but it will then be empty. So you can't LSP-legally inherit either way.
(This is one of the "deep reasons" why inheritance is actually not a terribly useful architectural tool. It technically breaks really, really easily... like, probably most non-trivial uses of inheritance in most code bases is actually wrong somehow, even if never happens to outright crash. We tend to just code past the problem and not think about it too hard.)
Neither direction works. More directly (since I was working it out as I typed above):
A NonEmptyList promises that its .Head method will always produce a value. An inherited List can not maintain that property, it must add either an error return or a possible exception (which is the same thing from this point of view), and so violates the LSP.
A List promises that if it has an element, you can remove it and have another List, whether by mutation or returning a new List. A NonEmptyList breaks that promise. If that sounds like a "so what", bear in mind that "removing an element" includes things like a "Filter" method, or a "split" method, or any of several other such methods beyond just iteration that a List is likely to have that a NonEmptyList is going to need a different type signature and/or exception profile to implement properly.
You could define a bare-bones superclass for both of them that allows indexing, iteration, appending, and a length method, without much else, and that does work. However, if you start trying to get very granular with that, across more data structures, you'll start to need multiple inheritance and that becomes a mess really quickly. There's a reason that, for instance, the C++ STL does not go the "inheritance hierarchy" route for this stuff.
Like I said, inheritance done properly is really restrictive. We often do a lot of sweeping under the rug without even realizing it, and that "works" but it still eats away at the architecture, all the more so if the people involved don't even realize what they are doing.
> A List promises that if it has an element, you can remove it and have another List, whether by mutation or returning a new List. A NonEmptyList breaks that promise.
I don't follow. Remove the head from a NonEmptyList and the tail will be a List. It might not be a NonEmptyList, but that's not the contract of List.
I didn't spell it out adequately, only implied it, but I am talking about a fully loaded List, not one that just barely works, e.g., it has filter, it has all the other things you'd expect from a List. I did discuss the "just barely works" case at the end.
But the nonempty list never has an element, so we don't need to worry about the type mutation of removing an element from it. Filter just returns a nonempty list.
Yes, type classes can "work" to help a NonEmptyList degenerate to a normal List of some sort, if the function accepting the list accepts the type class instead of a hard-coded List. Unfortunately, at least for this exact task, taking hard-coded types is pretty common. I've sometimes wondered about the utility of a language that provided all of its most atomic types solely as typeclasses within its standard library, so that calling for a "List a" or "[a]" automatically was turned into the relevant type class.
Inheritance doesn't actually work here. I assume you mean inheriting a NonEmptyList from some sort of List, from the perspective of a user facing a language that has a standard List and they want to create a NonEmptyList that things taking List will accept. Unfortunately, that is a flagrant violation of the Liskov Substitution Principle and will create architecturally-fragile code.
Compilers can't enforce the LSP (with anything short of the dependently typed code you mention), so you can bash out a subclass that will throw an exception if you try to take the last element out of a NonEmptyList or violate the rules some other way, and if you pass your new NonEmptyList to something that happens to not do anything broken, you may get away with it, but by the standards of OO theory you're definitely "getting away" with something, not solving the problem.
I haven't studied this extensively beyond just thinking here for a moment, but I don't think you can LSP-legally go the other way either. A subclassed List can't revoke a parent's NonEmptyList property that the list is guaranteed to not be empty. Again, you can bash the methods into place to make it work, but as this is a very basic standard library sort of thing for a language it really needs to be right.
Edit: Yes, it's certainly illegal. You can take a List inherited from the NonEmptyList, have it be empty, but you have to be able to pass it to something accepting a NonEmptyList, but it will then be empty. So you can't LSP-legally inherit either way.
(This is one of the "deep reasons" why inheritance is actually not a terribly useful architectural tool. It technically breaks really, really easily... like, probably most non-trivial uses of inheritance in most code bases is actually wrong somehow, even if never happens to outright crash. We tend to just code past the problem and not think about it too hard.)