Design: living with slow instances

[aspiwack]

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.

[nfrisby]

A knee-jerk reaction to what you've already shared:

class SlowOK

slowIsOK :: (SlowOK => a) -> a
slowIsOK = ... unsafeCoerce ...

-- maybe also slowMustBeOK :: SlowOK => a -> a    to avoid "unused constraint" warnings throughout your code

instance SlowOK => Dupable (Mutable.Array a)

This is probably a strawman; it seems too opinionated for a core library, without some severe justification of performance assurances as an key desideratum, eg to the degree of functional correctness.

SlowOK will percolate up through your definitions until you block it by invoking slowIsOK. So there's always at least one opt-in syntactic indication that at least scopes over the use of each slow method, which is similar to being able to grep for the name of a value whose comment includes the "warning: slow".

[facundominguez]

What are the main use cases for a linear Reader?

[aspiwack]

@nfrisby

This is probably a strawman; it seems too opinionated for a core library, without some severe justification of performance assurances as an key desideratum, eg to the degree of functional correctness.

It's not bad, though. I can't say that I dislike. We probably won't find something better. But on the other hand, I have to agree that it's a bit gnarly, and may not fit a standard library.

@facundominguez

What are the main use cases for a linear Reader? It's a bit besides the point, so let's discuss it somewhere else, maybe.

[facundominguez]

It's a bit besides the point, so let's discuss it somewhere else, maybe.

Is it? If we knew what problems are on the table, we could evaluate how badly we need a linear Reader and how the dup problem fits in the story.

I'm not taking for granted that we need linear versions of everything. Not implying that you do, either. It is just that I'm a bit lost at what the purpose of a linear Reader is.

[nfrisby]

This is probably a strawman; it seems too opinionated for a core library...

I have to agree that it's a bit gnarly, and may not fit a standard library.

🙉🙈🙊 That's us, as if the infestation of Slow would be too much honesty :P