Design: living with slow instances

Something has been bothering me for a while. I'd like to use this issue to record my thoughts and try to communally solve the issue it represents.

Consider Dupable instances:

• The instances for Array or for List are a deep copy, hence are pretty expensive
• The instance for Int, while strict (pretty much every Dupable instance ever will be (technically, I think that, because of the call-by-need semantics, Int could have a lazy Dupable instance, but I digress)), is nevertheless perfectly cromulent.

How do we signal this?

It's not a new concern, or even specific to Linear Haskell: whenever I see .clone() in Rust I wonder whether I'm cloning an Rc (cheap), or something more costly (like a linked datatype). I wonder, by the way, if there is Rust code out there which quantify over the Clone trait.

When exporting a function which is slow, you just write that it's slow in the doc string, and people can audit their code for slow functions. But instances have a way of sneaking up on you.

Consider this instance

instance (Dupable e) => Applicative (Reader e) -- Linear reader

It's quite a bit more ok to use Reader Int (or Reader Pool, which is an actually useful application), but maybe we don't want to use Reader (Mutable.Array a) for that would be quite expensive.

But it's easy to get tricked into it.

Another example that I have in mind is the applicative instance for the Vectors-of-known length library. There is a perfectly reasonable (data) applicative instance for regular vectors. But it does allocate. Whereas there is an efficient instance for the pull-array version of said vectors.

How do we help users avoid using the wrong instance when they want to be precise?

I'll share some more thoughts on this tomorrow.

Start by reviewing the Dupable instances for Array, List, Int, and Reader e described in the issue, along with the vectors-of-known-length applicative examples. Define how users should identify expensive instances and what API or documentation change would communicate that cost; the issue currently supplies no file or test to run.