# Fusion Rules in filepather
## What is Fusion?
A `FilePather f a` is a function `FilePath -> f a`. Mapping over it twice,
as in `fmap f (fmap g x)`, builds an intermediate `FilePather` and maps over
`f` twice for every file path it is applied to. The rewrite rules replace such
compositions with a single map, so that `f` is traversed once.
## Rule Categories
The rules are written on the worker functions `mapFilePather` and
`mapMaybeFilePather`, and `mapTracked` and `mapMaybeTracked`, never on the
class methods: `fmap = mapFilePather` and `mapMaybe = mapMaybeFilePather` (and
likewise for `Tracked`), and each instance method is `INLINE`, so that it is
rewritten to its worker before the rules are tried.
### 1. Functor Fusion
* `mapFilePather/mapFilePather`:
`mapFilePather f (mapFilePather g x) = mapFilePather (f . g) x`
* Removes the intermediate `FilePather` of `fmap f . fmap g`.
* Based on the Functor composition law of `f`.
### 2. Filterable Fusion
* `mapMaybeFilePather/mapMaybeFilePather`:
`mapMaybeFilePather f (mapMaybeFilePather g x) = mapMaybeFilePather (g >=> f) x`
* `mapMaybeFilePather/mapFilePather`:
`mapMaybeFilePather f (mapFilePather g x) = mapMaybeFilePather (f . g) x`
* Based on the Filterable composition laws of `f`.
### 3. Tracked Fusion
* `mapTracked/mapTracked`, `mapMaybeTracked/mapMaybeTracked` and
`mapMaybeTracked/mapTracked`: the same rules for `Tracked`, which maps
inside `f`, the `Either Cycle` of a stopped chain, and the pair of outputs
and result.
## Phase Control
The workers are `NOINLINE [1]`, and the rules are active before phase 1
(`[~1]`). In phases 2 and 1 the rules fuse compositions of workers; from
phase 1 the workers may inline, exposing the `fmap` and `mapMaybe` of `f` to
the rules of `f` itself.
## Verifying Fusion
Check the rules fire in a module that composes the operations:
```bash
cabal build --ghc-options="-ddump-rule-firings"
cabal bench
```
## Performance Impact
The `FilePather/fmap x1000` benchmark maps over a `FilePather` 1000 times.
Build steps spend almost all of their time in the external programs they
run, so fusion matters for pure `FilePather` values, such as those used as
predicates and rules over many files.
## Law Foundation
| Rule | Law |
|---|---|
| `mapFilePather/mapFilePather` | `fmap f . fmap g = fmap (f . g)` |
| `mapMaybeFilePather/mapMaybeFilePather` | `mapMaybe f . mapMaybe g = mapMaybe (g >=> f)` |
| `mapMaybeFilePather/mapFilePather` | `mapMaybe f . fmap g = mapMaybe (f . g)` |
| `mapTracked/mapTracked` | `fmap f . fmap g = fmap (f . g)` |
| `mapMaybeTracked/mapMaybeTracked` | `mapMaybe f . mapMaybe g = mapMaybe (g >=> f)` |
| `mapMaybeTracked/mapTracked` | `mapMaybe f . fmap g = mapMaybe (f . g)` |