Meetup summary

2024-11-22 - 2-3 Finger Trees (part 3) and Generating Functions Practica

  • M. Douglas McIlroy’s Power series, power serious functional pearl from JFP. This is a wonderful introduction to practical computing with power series, which themselves have direct connections to Analytic Combinatorics through generating functions. It shows how lazy (but automatically memoized) stream types (such as Haskell’s lists) make these computations signifcantly simpler than doing things the “direct” way.
  • Wikipedia’s entry on formal power series, particularly the section on operations on formal power series.
  • Don Knuth’s treatment of power series in TAOCP (Volume 2, section 4.7). I believe this is only available starting in the third edition.
  • If you didn’t have a chance to read it the last two times, Hinze and Paterson’s 2-3 Finger Trees paper.

Agenda:

  • Go over the remaining finger tree operations we didn’t get to last time
  • Play around with Neil’s dynamic finger tree visualizations to get a better feel for how they work.
  • Go through some basic generating function problems with simple constructions.
  • Discuss how to numerically pick out GF coefficients with simple programming techniques. Sadly, it turns out that working directly with GFs on real, complex problems quickly becomes infeasible on paper (modulo asymptotics), so we need a way to actually compute answers to the problems we care about.
  • Work through some simple Python and Haskell implementations that I’ve written for manipulating power series.

Notes:

We did not get to any worked combinatorics problems or to the lazy sequence paper on coefficient extraction, but did get through formal power series convergence and summation of two power series(es?). We will pick up next time with classical techniques for coefficient extraction.

tags: