Hacker News Reader

Hacker News

Comment by greener_grass | Hacker News Reader

Parent Full thread

greener_grass

> You can take a List inherited from the NonEmptyList

Shouldn't it go the other way?

All NonEmptyLists are Lists, but not all Lists are NonEmptyList.

So NonEmptyList inherits from List

View on HN

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.

NonEmptyList<'t> has a method Uncons that returns 't * List<'t>

List<'t> has a function TryUncons that gives Option<'t * List<'t>>

List<'t> does not have a method Uncons.

We can define TryUncons for NonEmptyList<'t> in terms of Uncons, specifically:

    this.TryUncons() = 
      this.Uncons() 
      |> Some

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.

It would be an odd "object oriented language" list that lacked such things, e.g., https://docs.oracle.com/javase/8/docs/api/java/util/List.htm... . We're in OO land here, not FP land.

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.

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

NonEmpty always has an element.

Why not in the other direction? If NonEmptyList inherits from List, then head (and tail) would be methods of NonEmptyList but not of List.

> A List promises that if it has an element, you can remove it and have another [..]. A NonEmptyList breaks that promise.

No. Removing an element from a NonEmptyList returns a List. LSP is respected when NonEmptyList is a List.

Reply on news.ycombinator.com