Tue 25 Aug 2026 11:24 - 11:42 at IP126 Auditorium - Types, Testing, and Data Structures Chair(s): Steve Zdancewic

A transient data structure is a combination of an ephemeral data structure, a persistent data structure, and fast conversions between them. We present a transient sequence data structure that supports efficient read and write access at an arbitrary index with worst-case cost $O(K\log_K n)$, insertion and extraction at either end with worst-case cost $O(K\log_K n)$, and splitting and concatenation with worst-case cost $O(K\log^2_K n)$, where $K$ is a user-defined chunk size. We provide a detailed analysis of this data structure and show that, in many favorable scenarios, it performs much better than these pessimistic worst-case bounds might suggest. Furthermore, we describe its implementation and provide an experimental evaluation of its performance. We believe that it is a good candidate for a one-size-fits-all, general-purpose sequence data structure.

Tue 25 Aug

Displayed time zone: Eastern Time (US & Canada) change

10:30 - 12:00
Types, Testing, and Data StructuresICFP Papers at IP126 Auditorium
Chair(s): Steve Zdancewic University of Pennsylvania
10:30
18m
Talk
Inlining as a space optimization: a simple time- and space-invariant implementation of the weak lambda-calculusDistinguished PaperRemote
ICFP Papers
Thibaut Balabonski LMF, CNRS, Université Paris-Saclay
DOI
10:48
18m
Talk
First-Class Constrained Types: Elaboration, Type Inference, Approximation, and a Characterization of TerminationDistinguished Paper
ICFP Papers
Chun Kit Lam The Hong Kong University of Science and Technology (HKUST), Florent Ferrari-Dominguez ENS de Lyon, Lionel Parreaux HKUST (The Hong Kong University of Science and Technology)
DOI
11:06
18m
Talk
Programmable Property-Based TestingDistinguished Paper
ICFP Papers
Alperen Keles University of Maryland at College Park, Justine Frank University of Maryland, College Park, Ceren Mert University of Maryland, College Park, Harrison Goldstein University at Buffalo, SUNY, Leonidas Lampropoulos University of Maryland at College Park
DOI
11:24
18m
Talk
A Catenable, Splittable, Transient Sequence Data StructureDistinguished Paper
ICFP Papers
DOI
11:42
18m
Talk
Adapting the MVVM pattern to C++ frontends and Agda-based backendsJFP First Paper
ICFP Papers
Viktor Csimma Eötvös Loránd University, Eötvös József Collegium (Budapest, Hungary)
Link to publication DOI Pre-print