A stream that cannot be an instance of traversable
vector-0.1 package has a quite efficient
Stream implementation (
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
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
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
<*> 'pulls in' the
<*> :: f(a->b)->(f a->f b)) whereas here I need the exact opposite, a co-
<*> so to say.
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
Traversable? Or asked differently: What is the actual mathematics behind this impossibility?
This is Traversable, but not in a very interesting way. Because it permits
fromListas 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
fto 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
xvalue 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 sfirst to get a hold of its effects.
You don't want
pure sat 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
svalue you have in scope: call
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.