Why is it impossible to Applicative-traverse arrays? (Or is it?)

Question

While pondering how to best map, i.e. traverse, an a -> Maybe a-Kleisli over an unboxed vector, I looked for an existing implementation. Obviously U.Vector is not Traversable, but it does supply a mapM, which for Maybe of course works just fine.

But the question is: is the Monad constraint really needed? Well, it turns out that even boxed vectors cheat for the Traversable instance: they really just traverse a list, which they convert from/to:

instance Traversable.Traversable Vector where
  {-# INLINE traverse #-}
  traverse f xs = Data.Vector.fromList Applicative.<$> Traversable.traverse f (toList xs)

mono-traversable does the same thing also for unboxed vectors; here this seems even more gruesome performance-wise.

Now, I wouldn't be surprised if vector was actually able to fuse many of these hacked traversals into a far more efficient form, but still – there seems to be a fundamental problem, preventing us from implementing a traversal on an array right away. Is there any “deep reason” for this inability?

Helminthic

The lack of the instance for U.Vector has to do with the Unbox constraint on the elements. See Why are unboxed arrays not an instance of foldable? (the answer, by Snoyman, also includes some relevant comments about mono-traversable). – Rafaelrafaela

Sure, but that's not what I'm asking about. I don't need an actual Traversable instance, I just need an efficient traversal! And mono-traversable doesn't offer this. – Helminthic

Oops -- I didn't notice the "obviously" in your first paragraph :) – Rafaelrafaela

Hmm... If it fuses reliably then I suppose there's not much incentive to look for a different--presumably harder, if not impossible--solution. – Placidia

There seems to be an implicit assumption here that the Traversable instances for records with many fields are "efficient" in some sense. In fact I wouldn't be surprised if traversing a 100-element vector (with the above implementation that converts to and from lists) was cheaper than the derived instance for a record with 100 fields, at least for certain monads. – Bristol

@ReidBarton aha... whence do you infer that implicit assumption? I didn't have any thought about records with many fields here. – Helminthic

Well I guess I don't understand the question. It's obviously possible to traverse an array, since the code you pasted does it. There must be some other constraint... but what? – Bristol

@ReidBarton traversing without creating an intermediate list, for example? Mutable arrays + unsafeDupablePerformIO + unsafeFreeze could do it, I think. – Cupule

@ReidBarton on a second though, it's no good, for example we can't use destructive update when we traverse in the list applicative. – Cupule

Answer 1

After reading through the relevant source of vector and trying to make mapM work with Applicative I think the reason why Data.Vector.Unboxed.Vector doesn't have a traverse :: (Applicative f, Unbox a, Unbox b) -> (a -> f b) -> Vector a -> f (Vector b) function and Data.Vector.Vector doesn't have a native traverse is the fusion code. The offender is the following Stream type:

-- Data/Vector/Fusion/Stream/Monadic.hs  Line: 137

-- | Result of taking a single step in a stream
data Step s a where
  Yield :: a -> s -> Step s a
  Skip  :: s -> Step s a
  Done  :: Step s a

-- | Monadic streams
data Stream m a = forall s. Stream (s -> m (Step s a)) s

This is used internally to implement mapM. The m will be the same as from your initial call to Data.Vector.Unboxed.mapM. But because the spine of this stream is inside the m functor, it is not possible to work with it if you only have an applicative for m.

See also this issue on the vector GitHub repo: Weaken constraint on mapM.

Disclaimer: I don't really know how fusion works. I don't know how vector works.

Weisbart