A stream that cannot be an instance of traversable
The vector0.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, unmonadic 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
can't be Traversable
. What structural element is missing to make Stream
a Traversable
? Or asked differently: What is the actual mathematics behind this impossibility?
1 answer

This is Traversable, but not in a very interesting way. Because it permits
fromList
as well astoList
, we havesequenceA = fmap fromList . sequenceA . toList
You can't really do anything more interesting: you have a
Stream (f a)
and wish to producef (Stream a)
instead. Since your Stream is isomorphic to a list, to get the effects inf
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 anf 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 callingstep 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 thes
value you have in scope: callstep
with it!This approach is fairly natural once you've written a couple Streamconsuming functions already (which I discovered by implementing Foldable and Functor by hand). The only possible way to consume a Stream is to casematch on
step s
, and if you start with that you sidestep the red herring that distracted you.