API using Applicative (traverse et.al.)

[Shimuuar]

API based on Applicative has been requested multiple times:

• #69 traverse
• #132 weaken constraint on mapM (again traverse)
• #144 generateA

This is quite natural request. Applicative is quite restrictive: we must know length of resulting vector in advance and we can't use result of one applicative value in other computations. This leaves us with four functions:

replicateA :: Int -> f a          -> f (v a)
generateA  :: Int -> (Int -> f a) -> f (v a)
traverse   :: (a -> f b)        -> v a -> f (v b)
itraverse  :: (Int -> a -> f b) -> v a -> f (v b)

Did I forget some? But their implementation runs into several difficulties.

Problems

Applicatives are not compatible with stream fusion. Look at stream type:

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

data Step s a where
  Yield :: a -> s -> Step s a
  Skip  :: s -> Step s a
  Done  :: Step s a

In order to generate next element of stream m must be monad. Thus we can not write traverse in terms of it.

Another problem is functions must work with any applicative. This includes functions, list so f (v a) may require creating multiple vector, may involve complicated sharing. So we have to use pure data structures. This means we have either to go through lists or build chain of closures. AFAIR massiv used latter approach which was more performant.

Existing implementations

Existing implementation in lens goes through list. Maybe its possible to improve upon it.

Proposal

We can't relax constraint of mapM and friends. So we should leave them as they are. Instead we should add set of non-fusible functions which use Applicative. In fact we only need to implement generateA all other functions could be trivially expressed in terms of it.

Selecting optimal implementation will require benchmarks. So I want to improve our benchmarks situation first