cats' NonEmptyList vs scala stdlib ::

Question

I am studying the cats library recently, and I have come across this class called NonEmptyList.

After reading the api, I couldn't help wondering what is it that made the cats authors to create a new class, instead of utilizing something that is built in (::) and use type classes to extend it. It is not even listed in the cats github page, so I have come here to ask about it. Maybe it is because cons is a subtype of List? (Though I do not know the implications of it)

What are the differences between :: and NEL? And why did cats authors have to write NEL instead of using ::?

Answer 1

The main reason for having NonEmptyList which doesn't extend from List is developer experience of including assumptions in the APIs.

Firstly, note that :: has all the methods List has which can be misleading and it makes it harder to design better APIs with more powerful assumptions. Additionally, List doesn't have any methods that directly return ::, which means that developer needs to maintain non-empty abstraction manually.

Let me show you an example which shows what I mean in practice:

// NonEmptyList usage is intuitive and types fit together nicely
val nonEmpty: NonEmptyList[Int] = NonEmptyList.of(1, 2, 3)
val biggerNonEmpty: NonEmptyList[Int] = 0 :: nonEmpty
val nonEmptyMapped: NonEmptyList[Int] = nonEmpty.map(_ * 2)

// :: has lots of problems
// PROBLEM: we can't easily instantiate ::
val cons: ::[Int] = 1 :: 2 :: 3 :: Nil // type mismatch; found: List[Int]; required: ::[Int]
val cons: ::[Int] = new ::[Int](1, ::(2, ::(3, Nil)))

// PROBLEM: adding new element to Cons returns List
val biggerCons: ::[Int] = 0 :: cons // type mismatch; found: List[Int]; required: ::[Int]

// PROBLEM: ::.map returns List
val consMapped : ::[Int] = cons.map(_ * 2) // type mismatch; found: List[Int]; required: ::[Int] 

Note that NonEmptyList has methods that return List, namely filter, filterNot and collect. Why? Because filtering through NonEmptyList may mean that you filter out all elements and the list can become an empty one.

This is what makes the whole non-empty abstraction so powerful. By properly using function input and output types, you can encode assumptions about the API. :: doesn't provide this abstraction.