Unrolling Lists

Add to your list(s) Download to your calendar using vCal

• Jake Bennett-Woolf (University of Cambridge)
• Monday 18 November 2024, 13:00-14:00
• FS07, Computer Laboratory.

If you have a question about this talk, please contact Ariadne Si Suo .

Lists are used throughout functional programming and the idea of defining lists with multiple heads for optimisation is almost as old as the subject itself. We present a theoretical justification for $\mathbb{N}$-indexed (multi-headed) lists as the natural datatypes that comes from unrolling the defining equation $X = 1 + A \times X$ for lists, and give $\mathbb{N}$-indexed implementations of functions that normally use intermediate lists and that satisfy certain conditions.

We then discuss staged metaprogramming and use this to speed up these functions so that they are at least as fast as their usual list counterparts. Our guiding examples will be tail-recursive $\map$ and $\filter$ for lists in OCaml.

This talk is part of the SANDWICH Seminar (Computer Laboratory) series.

This talk is included in these lists:

• FS07, Computer Laboratory

Note that ex-directory lists are not shown.