Add fusion rules

[treeowl]

I certainly don't know which ones we want, but it would be nice to get some sort of fusion. Here's one possibility to consider:

The hoist, maps, and >>= operations can be combined into a single operation

hoistMapsBind :: (Monad m, Functor f)
               => (forall x. f x -> g x)
               -> (forall x. m x -> n x)
               -> (r -> Stream g n s)
               -> Stream f m r
               -> Stream g n s
-- hoistMapsBind phi psi thn str ~= hoist psi (maps phi str) >>= thn
hoistMapsBind phi psi thn = loop where
  loop :: Stream f m r -> Stream g n s2 thn2 (thn1 r)) str
  loop (Return r) = thn r
  loop (Effect m) = Effect $ psi (liftM loop m)
  loop (Step f) = Step $ phi (fmap loop f)

If we so desire, we can rewrite applications of hoist, maps, and >>= to applications of hoistMapsBind, and then fuse them using the following rule:

"hmb/hmb" forall (phi1 :: forall x. f x -> g x) (psi1 :: forall x. m x -> n x) (thn1 :: r -> Stream g n s)
                 (phi2 :: forall x. g x -> h x) (psi2 :: forall x. n x -> o x) (thn2 :: s -> Stream h o t)
                 (str :: Stream f m r).
            hoistMapsBind phi2 psi2 thn2 (hoistMapsBind phi1 psi1 thn1 str) =
              hoistMapsBind (\x -> phi2 (phi1 x)) (\x -> psi2 (psi1 x))
                            (\r -> hoistMapsBind phi2 psi2 thn2 (thn1 r)) str

But of course there could be much more general fusion opportunities we should be considering instead. I am especially curious about whether there's any way to convince GHC to do some of the heavy lifting itself.

[andrewthad]

I like this idea. Although, it does require rewriting a bunch of other functions in terms of hostMapsBind. In my own code, I often end up with chains of Streaming.Prelude.mapM, which I believe should be able to fuse together. It's hard to know if hoistMapsBind is the best choice though.

[treeowl]

Has anyone tried generalizing the streams in Data.Vector.Fusion.Stream.Monadic?

data Stream f m r where
  Stream :: (s -> StreamF s f m r) -> s -> Stream f m r

data StreamF s f m r =
    Step (f s)
  | Effect (m s)
  | Return r

I really don't have time to look into that this week, but it might be worth thinking about. I suspect the overly weak constraint on hoist could be troublesome, but that's mmorph's fault.

[treeowl]

Nope, that doesn't work, because it doesn't give a way to change the s type mid-stream. The Monad instance seems impossible. There might be some other way....

[treeowl]

Huh... Actually, using the same approach vector applies to ++ actually does seem to work. But only, of course, if there's enough inlining. It would probably still be worth some benchmarking.