Imagine you have a function in a public API that needs to return some kind of collection. Its type is something like
foo :: a -> b
b is some kind of collection.
As far as I can see, there a three major kinds of collections -- at least those are the ones used most often:
- Sequences (order matters, there might be duplicates)
- Sets (order doesn't matter, no duplicates)
- Maps (elements are key-value pairs, order doesn't matter, no duplicate keys)
What should you use for
b in these three cases?. I have considered three alternatives, but there might be more.
A. Just return a list
In this alternative, you just return lists for everything:
foo :: a -> [c]
foo :: a -> [c](and document that there are no duplicates)
foo :: a -> [(k, c)](and document that there are no duplicate keys)
The advantage of this is that the client can construct any collection they want from the returned list.
The disadvantage for 2 and 3 is that
- the type does not have the "no duplicates" guarantee and that the client has to do more work to get a set/map out of it
- construction of the list in 2 and 3 might be less efficient, because something like a
unionfor sets is obviously faster than for lists
- you might construct an intermediate list (depends on the problem at hand).
B. Return a concrete type matching the guarantees
In this alternative, you return a type that precisely matches the guarantees you are giving:
foo :: a -> [c](or maybe
foo :: a -> Data.Sequence.Seq c)
foo :: a -> Data.Set.Set c(lazy or strict?)
foo :: a -> Data.Map.Map k c(lazy or strict?)
The advantage is that the type accurately describes the guarantees you want to express and that the client doesn't have to do any extra work.
The disadvantage is that you're locked into a particular implementation. If you just want to switch to a different set implementation, you break the public API. That might be a good thing in case of a switch between lazy and strict, because those can matter for correctness of the calling code. But in general you want to be able to swap implementation without your clients noticing.
C. Let the client decide
In this alternative, you just constrain the return type with a type class and let the client decide on the concrete type:
1. `foo :: Sequence b c => a -> b` 2. `foo :: Set b c => a -> b` 3. `foo :: Map b c k => a -> b`
(The names I used are from collections-api, but it doesn't really matter.)
The advantage of this is that the client can choose which collection type to use.
The disadvantage is that you have no control over the collection you construct anymore. This means, e.g., that you cannot assume laziness or complexity of inserts. Another problem is that the client can get ambiguous types, e.g., when they immediately fold the returned collection:
Data.Foldable.fold (foo whatever)
b is ambiguous.
Are there any other alternatives? What would you recommend?
I don't want
foo to be able to return a different kind of collection on every call.
The three cases considered are completely separate.
In each case the question is "if I have a function that needs to return an X, what type should it have?" where X can be a sequence, set, or map (or any other kind of collection you can think of).