> 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.