Too difficult to write a function which accepts Array or List

Question
20

I mean what can you do with something that may either be a List or a Vector or a Set or a Map or a infinite lazy Stream?

Better question, what can you sanely do?
Because you can do a lot of things, but all can be or very efficient or very inefficient.

For example:

  • Get the head (first elements), actually efficient on all. But what does it means to get the first element of an unordered collection like a set?
  • Get the tail, forgetting about the ordering problem, this is pretty efficient on List and Stream, but it is pretty inefficient on Vector and Array.
  • Check if it contains an element, straight forward on all, but if you require it multiple times, you really hope you have a Set which provides it as an O(1) operation.
  • Get the length, efficient for many of those, inefficient for List, will never terminate for the infinite Stream.
  • etc.

My point is, for most algorithms you write them with an especial kind of structure in mind. And if you want to reason about the complexity of your whole algorithm, you need the complexity of your collection operations (which you can only do with concretes).

And the few algorithms that can be written for multiple collections fallback to three special cases (IMHO):

  1. Algorithms using map & flatMap; i.e. for Monads.
  2. algorithms that basically iterate the collection with an internal state, e.g. foldLeft, traverse. Again for those, it is better to use a typeclass (Foldable / Traverse in this case) instead of trying to model those with subtyping.
  3. Algorithms that are basically data processing pipelines, which you can do for every collection by requiring a TraversableOnce and asking for its iterator; you then chain all the transformations on that iterator (taking advantage on it being lazy) and finally consume the iterator by transforming to a concrete collection again (you may do black magic to ensure that concrete is the same one it was passed to you, but it has always been extremely complex for me, so I never did that).

PS: For the second use case, I would rather use a proper Stream; e.g. fs2, akka streams, monix observables or zio zstreams.

2 Likes