Filter Equivariant Functions: A symmetric account of length-general extrapolation on lists
This work addresses the challenge of rule-following in list functions for functional programming and AI, though it appears incremental by building on map equivariant functions.
The paper tackles the problem of defining functions that extrapolate beyond known examples by introducing filter equivariant functions, which behave predictably when elements are removed from lists, and presents an amalgamation algorithm that constructs such functions to extrapolate perfectly.
What should a function that extrapolates beyond known input/output examples look like? This is a tricky question to answer in general, as any function matching the outputs on those examples can in principle be a correct extrapolant. We argue that a "good" extrapolant should follow certain kinds of rules, and here we study a particularly appealing criterion for rule-following in list functions: that the function should behave predictably even when certain elements are removed. In functional programming, a standard way to express such removal operations is by using a filter function. Accordingly, our paper introduces a new semantic class of functions -- the filter equivariant functions. We show that this class contains interesting examples, prove some basic theorems about it, and relate it to the well-known class of map equivariant functions. We also present a geometric account of filter equivariants, showing how they correspond naturally to certain simplicial structures. Our highlight result is the amalgamation algorithm, which constructs any filter-equivariant function's output by first studying how it behaves on sublists of the input, in a way that extrapolates perfectly.