Apply codensity to Progress
- Dominant language
- Haskell
- Stars
- 1.7k
- Forks
- 750
- Avg merge
- 4d 3h
- Merged PRs (30d)
- 28
Description
CC @dcoutts, @grayjay, @kosmikus,
The `Progress` type in `Distribution.Client.Dependency.Types` is a great idea and more code in Cabal should use it. However, I am a bit worried about the asymptotic complexity with left associated binds.
Progress is an instance of the free monad over:
```
data ProgressF step fail a = Step step a
| Fail fail
```
As a reminder, the free monad construction is:
```
data Free f done = Free (f (Free f a)) | Done done
```
Inlining `ProgressF step fail` into `f`, we have:
```
Free (ProgressF step fail) done = Step step (Free (ProgressF step fail) done) | Fail fail | Done done
```
which is the current definition of `Progress`.
It is known that free monads have trouble with left associativity, see http://comonad.com/reader/2011/free-monads-for-less/ and http://blog.ezyang.com/2012/01/problem-set-the-codensity-transformation/ so instead we want to apply `Codensity` to avoid this problem.
So, I would like to apply the `Codensity` transformation to `ProgressF`. However, there are some questions:
1. Does `Codensity` retain the incrementality that the original `Progress` had?
2. Should we define `ProgressF`, `Free` and `Codensity`, bring in a dependency to get them, or inline all the data type declarations (just as `Progress` is the inlined version of `Free ProgressF`)
Contributor guide
Assessment
This issue has not been assessed yet.