haskell / haskell/cabal

Apply codensity to Progress

Open
#3,640 3 comments 0 reactions 0 assignees View on GitHub
cabal-install: other Cabal: other old-milestone: ⊥ type: discussion
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.