The Free and the Furious: And by 'Furious', I mean Codensity
summary
Shows that using Codensity on Free Monads converts left‑nested binds into right‑associated continuations and yields huge speedups: reversing 10,000 chars drops from ~71s to ~0.7s, a free‑monad list example drops from 145s to ~80ms, and a 20,000 countdown using lists goes from 18s to 20ms by switching to DList. The key tool is the improve/lowering combinator (continuation‑passing), implemented in Haskell; code and benchmarks are on the linked GitHub.
AI-written summary · about
chapters (17)
- 0:00Intro
- 1:48Reddit thread
- 6:35Outline
- 8:52Motivation example
- 12:37Model
- 17:20Results
- 17:54Freeness
- 25:16Great Scott
- 26:02The Problem
- 28:11Monitor Loss
- 29:45Codensity
- 31:12Implementations
- 34:09Solution
- 34:30Teletype
- 36:23GetChar
- 37:16Improve
- 39:08Devious Package
related talks
44mThe Free and The Furious: And by 'Furious' I mean Codensity.
01h 14mBeyond Free Monads
43mFree monad or tagless final? How not to commit to a monad too early
32mDiscussion: Are Free Monads Really Free?
41mWhy the free Monad isn't free
42mMonads you already use without knowing it
01h 06mThe Evolution of Effects
50mHierarchical Free Monads & Software Design in Functional Programming