How to create Haskell containers that fuse?

Question

I'm interested in creating a new Haskell container type (strict lists), and I want to make sure that operations on them are eligible for stream fusion. How do I opt-in to ghc's stream fusion capability?

If my container is Traversable, will it fuse automatically? If I implemented, say, mapAccumL in terms of toList, will Haskell be smart enough to not convert the container to a List at all, instead simply operating on the underlying representation?

Wildon

If you want an in-depth understanding, look over the stream fusion paper. – Schechter

ghc doesn't implement stream fusion. It implements foldr/build fusion. The primary difference is that concats are only fusable via foldr/build fusion (although research is ongoing), whereas zips are only fusable via destroy/unfoldr fusion (to which stream fusion is quite closely related). – Landin

Answer 1

GHC is not actually intelligent at all. It's just (good) software. If you want your new thing to fuse, you have a few options:

1. Build it on top of something that already fuses: Lists fuse using foldr/build fusion, and vectors fuse using stream fusion. If you build your type on top of one of them, you can likely arrange for it to fuse properly without much fuss. If you have the option, this is almost certainly your best choice.

2. Fuse just at interfaces: Even if your type doesn't fuse away, you may want to arrange for a certain amount of fusion when it is converted to or from a list or vector.

3. Write fusion rules yourself: This is not too hard in principle, but in practice you will be pounding your head against the wall, so unless you're crazy like me, you may want to avoid this approach: your rules will not fire when you want, they will interfere in complicated ways with other rules, the inliner will make you its &%$#@, and even when things seem to be working right, the benchmarks will show the opposite of what you want.

Shape