Add strict array operations and perhaps arrays

[treeowl]

Currently, unordered-containers has a Data.HashMap.Array module that's pretty similar to Data.Primitive.SmallArray. I'd love to stack unordered-containers on top of primitive to avoid this duplication. Aside from the bugs currently being fixed in primitive, I'm missing some operations. Notably, I need operations like strict map (map over an array, forcing the results) and strict traverse (traverse an array, forcing the results as they're installed). Could we add such operations?

Furthermore, some strictness bugs that have turned up in unordered-containers were caused by failure to force things before installing them in arrays. One possible fix would be to add modules full of strict array operations (the way we have Data.HashMap.Lazy and Data.HashMap.Strict with the same types). Another option would be to offer a separate type for notionally strict arrays, offering only strict operations (and no Functor instance). This would make it easy to avoid goofing up, but users could break open the abstraction if necessary to implement things like efficient Functor and Traversable instances for types using "strict" arrays.

[andrewthad]

I prefer the approach of making Data.Primitive.Array.Strict and Data.Primitive.SmallArray.Strict modules that share the same Array and SmallArray types that are already used (basically following the convention of containers and unordered-containers). Also, could we get imap, itraverse, and generate in there while we're at it? I feel like I reimplement those all the time.

[andrewthad]

Actually, as I think about it more, you may want a Data.Primitive.Array.Lazy module as well. Currently, primitive uses the import-everything-unqualified name scheme by including the name of the type of every operation. If we did start introducing additional helper functions for common operations on arrays, we would probably want to use the always-import-this-module-qualified approach for these functions.

[andrewthad]

My work on #106 suggests that the functions you describe would be named:

mapArray' :: (a -> b) -> Array a -> Array b
traverseArrayP :: PrimMonad m => (a -> m b) -> Array a -> m (Array b)

With the caveat that traverseArrayP is unsafe and that it doesn't give you strictness. You would need to force the value in your traversal.

[andrewthad]

As you pointed out, a strict traverseArrayP' would be pretty much worthless since you can do this trivially with traverseArrayP. As best I can tell, the answer to your original question about a strict traverse is no. The thing you would get would be suboptimal. But a strict map, yes. I think we should add that.

I'm weakly against offering separate types for strict variants. More types tends to mean worse interoperability, and I'm not fully convinced this would be useful to many people. At the least, I would prefer to see this implemented in a primitive-strict package first. Also, why wouldn't you just give strict array a Functor instance that's strict in the elements? I understand that Functor instances for data types that have a strict field of the polymorphic type technically don't pass the laws w.r.t. bottoming out, but I feel like this is a deviation from the laws that has largely been embraced. Control.Monad.Trans.State.Strict.StateT has a Functor instance, and people seem to be ok with that.

[treeowl]

I haven't embraced strict Functor instances. Note that strict StateT is strict in neither the state nor in the result, the latter of which is relevant here. In fact, lazy StateT is the one that fails the Monad laws; its laziness leads to a mild identity law violation.

[andrewthad]

Thanks for clarifying that. I had that totally wrong.

I've put up a PR adding strict map functions for Array and SmallArray. I'm interested in making it possible for unordered-containers to use primitive. It seems like a shame that it currently reimplements some of what primitive does. As I've mentioned earlier, I'm not sure how I feel about bringing over a strict traversal. The only other good candidate I see for something to bring over from Data.HashMap.Array is filter.

[treeowl]

I should mention that @tibbe has indicated that he has had trouble getting primitive stuff to specialize reliably enough to use for unordered-containers. Blech.

[andrewthad]

Maybe I'll look into this more as a future endeavor. The good thing is that unordered-containers has a ton of benchmarks, so it should be easy to spot a performance regression from swapping out the implementation of arrays.