Corecursion, Codata, and Just a Little Combinatorial Game Theory
summary
Claims that top-down recursion converts to bottom-up behaviour by using corecursive streams and infinite codata trees implemented in Haskell (Prelude functions like iterate and zipWith). Shows Fibonacci as an O(n) stream via zipWith sharing thunks versus exponential naive recursion, Newton–Raphson as an approximating generator plus a consumer, and modeling game search by generating trees then applying alpha-beta pruning to cut infinite trees to fixed depth. Warns about unproductive codata and notes no full game engine was finished.
AI-written summary · about
chapters (10)
- 0:00Start
- 3:26Concepts
- 4:58Use infinite data? How?
- 6:39Implications of
- 7:23What is Data?
- 12:20Recursion
- 18:03The Miracle Explained
- 19:44Creating your own
- 27:21Tree Example
- 29:04Combinatorial
related talks
25mInductive Synthesis of Structurally Recursive Functional Programs from Non-recur...
58mMonoidal Catamorphisms
44mPeeling The Banana: Recursion Schemes from First Principles
40mDynamic programming - 101
01h 00mType Theory Behind the Glasgow Haskell Compiler Internals (Part 5)
01h 47mAgda from Nothing: Order in the Types
48mTyping the Y Combinator
26mAffine Monads and Lazy Structures for Bayesian Programming