Apply labels from a stream to a Bitraversable
The fmap in labelLeft should be (.). Control.Lens.Zoom provides something like withStateLens. Inline definitions that are only used once.

bilabelWith
    :: Bitraversable t
    =&gt; (l -&gt;  indexl -&gt; l') -&gt; (r -&gt;  indexr -&gt; r')
    -&gt; Stream indexl        -&gt; Stream indexr
    -&gt; t l r -&gt; t l' r'
bilabelWith f g xs ys = flip evalState (xs, ys) .
  bitraverse (zoom _1 . pops . f) (zoom _2 . pops . g)

pops :: (s -&gt; a) -&gt; State (Stream s) a
pops = flip fmap $ state $ \(Stream.Cons x xs) -&gt; (x, xs)