Meetup summary

2025-01-24 - generatingfunctionologypracticum - lazy sequence (functional) edition

  • All the introductory reading on formal power series and computation from the classical methods meetup. on formal power series.
  • Review how painful it was to extract coefficients of a composition of power series even in O(n3)O(n^3) time using classical techniques.
  • 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.
  • Spend some time thinking about your novel knot/novel knot integration for show and tell.

Agenda:

  • Work through the Power Series, Power Serious paper. The goal is to get through all basic series operations (including series composition; the same stuff we did with classical techniques).
    • I don’t expect to get through “advanced” use cases involving reversion, differentiation/integration, or differential equations. We can do a follow-up session on that if there’s interest.
  • Compare the lazy technique to the classical technique from last time.
    • Ease or difficulty of implementation.
    • Understandability (especially for somebody without the requisite background).
    • Runtime and space usage.

Notes:

As expected, we did not get through the later operations (involving differentiation of series, etc) due to lack of interest. Instead, we dug into my simple OCaml implementation of lazy series. Note that while it’s easy to implement basic series operations (it’s essentially a direct translation of the math), it’s much harder to actually implement all admissible constructions, especially in the face of lazy sequences. In particular, the exp-log transformations require function composition over infinite sequences with an additional layer of nesting (you’re not just composing a series with another, but taking an infinite sum over parameterized series). This means that—practically speaking—you have to deal with truncated series at some point. This goes against the grain of the lazy sequence abstraction, which is (implicitly) infinite. We’ll probably revisit these details at a later meetup to build up a repertoire that will allow us to extract coefficients from the full suite of admissible constructions.

tags: