I recently watched a video about the library scalaz, which among other things discussed a “non-empty list” data structure provided by the library. I enjoyed very much when someone in the library asked “isn’t that just
Cons?”… This is an awesome implication of the fact that in Scala, data constructors are actually full-blown types, something that functional programming guys – like myself – can easily forget.
Of course, scalaz’s
NonEmptyList is a bit more than just
:: or whatever it’s called in Scala’s standard library), because it implements standard collection functions like
flatmap, etc. such that they preserve the
NonEmptyList result type.
Anyhow, this video, and my subsequent investigation of scalaz’s
NonEmptyList, got me thinking about this data type.
List is such a fundamental data structure – lists and folds on lists (remember, a data type is completely defined by its catamorphism) basically embody the concept of induction. So, it seemed like
NonEmptyList should have some sort of similarly deep meaning, and a similarly pithy definition.
I was sort of disappointed to find that the scalaz definition of NonEmptyList actually appeals to the definition of List directly, looking something like this (scalaz doesn’t use a case class, but this gets the idea across):
case class NonEmptyList[+A](hd: A, tl: List[A])
I started reading a Haskell-cafe thread about
NonEmptyLists, and saw Edward Kmett (who is one of my favorite writers on functional programming) use a
NonEmptyList that was defined in a very similar way, once again appealing to the definition of List:
data NE a = NE a [a] deriving (Eq,Ord,Show,Read)
I felt kind of dissatisfied with these definitions. I find using the definition of
NonEmptyList to be sort of ugly – it seems to get in the way of understanding the essence of
NonEmptyList, taken as its own concept. From a library implementer’s perspective, I understand the practicality – plenty of functions are already written to work with lists, and this is probably a fairly efficient encoding, performance-wise, as only the first cons cell needs to have any special information compared to a regular
With all those practical considerations aside, I thought this was a much slicker definition:
case class NonEmptyList[+A](hd: A, tl: Option[NonEmptyList[A]])
This seems to get a bit more at the fundamental nature of
NonEmptyLists. Of course it is trivially isomorphic to the above definition, but I like it better since its a bit more self-contained –
Option is simpler than
List (something like
forall X. 1 + X vs.
forall X. mu. x. 1 + X * x).
As far as I understand it, this is the equivalent of calling
toNel produces an
Option[NonEmptyList[A]]) in the scalaz library, so they certainly use it this way. Still, I think its slicker to do it by default rather than relying on extension methods on
List. Don’t get me wrong, I’m not so foolish as to think they hadn’t considered doing it in the way I propose – these guys know a hell a lot more about types and FP than I do (I’ve quoted their blogs a bunch, and I just bought a pre-release of their upcoming book).
As I continued to read the Haskell-cafe thread, I was excited to see that the next (and final) post was by Conor McBride, and showed that same slick formulation:
data NE x = x :> Maybe (NE x)
Conor McBride is a rock-star of type theory – the guy who showed the definition of “differentiation” (think calculus) can be extended to datatypes! What a boss.
It’s always a fun experience when you see people discussing a problem, you think “why don’t you solve it *this* way??”, and then someone whom you look up to offers that same idea. The occasional affirmation that you’re not totally out to lunch. Unfortunately for me, this only ever seems to happen while looking back at things – if I could just have decent ideas *before* other people have them, then I might be on to something.
All kidding aside, I feel like this phenomenon is common with many aspiring academics or budding programmers (at least among my friends and I): first you start reinventing wheels that were invented 50 years ago, then 20, then 5, then 1, then before you know it you’re actually doing some original research!
Anyhow, I just really liked the idea of
NonEmptyList, and this particular slick little formulation, and wanted to share it with everybody. I know above I speculated as to whether
NonEmptyList had some sort of similarly deep meaning as
List, and I’ll let you know if I read of (or think of) any.