Have you ever used a "random-access list"?

Learn
#1

A random-access list is a data structure that supports O(1) cons/head/tail (like a standard linked list), plus index/update in O(log n) time.

I first heard about it in Purely Functional Data Structures, which contains a couple implementations in the chapter on numerical representations. Probably due to this prominent feature, there are three packages that implement the interface, each with a shorter name than the ones that came before it:

… but I can’t say I’ve ever actually reached for this data structure!

From the chapter,

Skew binary random-access lists are a good choice for applications that take advantage of both the list-like aspects and the array-like aspects of random-access lists. Although there are better implementations of lists, and better implementations of (persistent) arrays, none are better at both.

I’m curious, what are some examples of such applications? Thanks!

4 Likes
#2

Huh, I thought Data.Sequence had this market cornered. A Seq has the same asymptotic performance characteristics as this thing, doesn’t it? I wonder what the difference is.

#3

Yeah, Sequence (2-3 finger tree) supports this API and more: O(1) access to both ends of the list, and logarithmic splitting and catenation. But constant factors would be different; I haven’t benchmarked but it’s plausible that the less powerful data structure would be faster.

2 Likes