Stream to be an instance of traversable

Question

The vector-0.1 package has a quite efficient Stream implementation (Data.Vector.Stream):

data Step s a = Yield a s
              | Skip    s
              | Done

-- | The type of fusible streams
data Stream a = forall s. Stream (s -> Step s a) s Size

Later versions of vector extended this to a monadic version Data.Vector.Fusion.Stream.Monadic, but let's use the old, un-monadic one for sake of simplicity.

Stream is quite naturally an instance of Functor and Foldable:

instance Foldable Stream where
    foldMap f s = foldl' (\a b -> a <> (f b)) mempty s

As a stream, it should also be an instance of Traversable, shouldn't it? At least at first glance it looks like it's an easy one. We need a

sequenceA :: Applicative f => Stream (f a) -> f (Stream a)

which would start out as

sequenceA (Stream step s) = Stream <$> step' <*> (pure s) where
    step' = ...

<*> is the only way to 'pull out' the applicative f from under the Stream. Now, step' should be

step' :: f (s -> Step s a)

and we have available a

step :: s -> Step s (f a)

All I know is that f is an Applicative (and Functor). But <*> 'pulls in' the f (<*> :: f(a->b)->(f a->f b)) whereas here I need the exact opposite, a co-<*> so to say.

Having a Traversable instance isn't crucial in any of my endeavours, and from a performance point of view it might not even be advisable. But it bugs me that I don't really grasp why Stream won't be Traversable. What structural element is missing to make Stream a Traversable?

Answer 1

This is Traversable, but not in a very interesting way. Because it permits fromList as well as toList, we have

sequenceA = fmap fromList . sequenceA . toList

You can't really do anything more interesting: you have a Stream (f a) and wish to produce f (Stream a) instead. Since your Stream is isomorphic to a list, to get the effects in f to the outer level you must walk over each item in your stream, incorporating the effects of each, and finally reconstruct a stream that parrots the objects embedded in the applicative structure, in the same order you saw them.

You could reimplement this yourself with the other functions in the Stream module, if you prefer, but it does basically the same thing. In particular, it is just as lazy. One approach would be:

sequenceA (Stream step init) = case step init of
  Yield x s -> cons <$> x <*> sequenceA (Stream step s)
  Skip s -> sequenceA $ Stream step s
  Done -> pure (Stream (const Done) ())

As you can see, the big departure from your attempt is that you should be fmapping into the x value found in the Yield case - that's the only way to incorporate its effects, because as you noted you cannot extract a value from an f a, only push other values into one. Happily, this is what you want to do after all! You just can't fmap over anything until you've gotten to the interesting part of the structure, which means calling step s first to get a hold of its effects.

You don't want pure s at all, because you are building a new Stream, with a new kind of internal state, unrelated to the Stream you consumed. And you already have a way to make use of the s value you have in scope: call step with it!

This approach is fairly natural once you've written a couple Stream-consuming functions already (which I discovered by implementing Foldable and Functor by hand). The only possible way to consume a Stream is to case-match on step s, and if you start with that you sidestep the red herring that distracted you.