Video 4-1: Types of Persistent Data Structures

0:03 In unit four, we'll look at persistent data structures, which is a completely different angle for data structures where we will talk about keeping versions of past status of past versions of the data structure around, but in a way that we don't pay much for it. Uh you'll see precisely what this means in a second. Um you could say we attempt to do time travel, but we'll restrict it to the harmless version where we don't modify the past and see what happens in the present. So, just the boring stories. What do I mean by time travel? The standard mode for data structures is to use them in an ephemeral way, which means they're passing. Uh again, English. So, any kind of updates destroy the past version of a data structure. That's usually what we want because we care about changing uh objects, and then only the current version is is the one that counts. Um which is in another way, you could say all the queries and all the updates always apply to the latest version, the newest version of your data structure.

1:16 It may go through past versions, but we forget about them. Not always is this um what you want though. Uh a persistent data structures are the general idea of keeping all the past versions around. You can think of it as the uh the Git repository of data structures. We can still access past versions. Um and at least read access is useful whenever you have legal requirements to be able to audit the changes to be able to tell what changes were made over time. Uh we'll also see that there's a a clever way how you can swap one dimension in space for the dimension of time and thereby make a very clever uh simple algorithm for a problem that otherwise may need much more thinking. Um it's also for for functional programming languages a fairly natural thing to assume that every kind of data is immutable. You can never change anything really. You can only move.

2:22 Uh you can only add to something and move to the new version of the same thing. Uh in that sense many of the early results were also inspired from implementing functional programming languages. Uh but by now it's a bit more general. Now it turns out if you look at it closely, uh you can define what is allowed to varying degree of of uh extreme. Um the simplest version is partial persistence where we allow queries to any past version, but updates always refer to the most recent version. So this is already more restrictive than Git. I cannot go back in time and uh branch off that past moment in time. Even though I'll I'll say it's how I use Git 99.9% of the time. I keep a history of past things in case I ever need something back. And most of the time that's all you need uh looking back at the history.

3:25 Uh whereas updates uh only to the recent thing, that keeps life a bit easier. So it also means that if you if you look at the versions of your data structure, this is a linear arrangement. There's one version following after the other. Right? Uh of course you could also do something more general where you also allow updates on past versions. And that's the full version of of what Git does or what Git allows. You can branch off at any past moment and generate a new version. And then, uh I guess Git could even do the next thing, which is even more crazy. Uh For every update and every query, you have to specify what version you're working on. And the versions are no longer linear. They may form a tree because you always have a parent version, the one that you started your update on. But then it branches off, and you may have many incomparable versions of your data structure around.

4:24 Uh and people have thought about even more general things. Um I'm not going to talk about those here because in a way, there's many uh questions still open and not so much definitive to be told yet. Uh in particular, you can talk about confluent persistence, where you can bring two past uh branches back together. And Git allows this with merges to some degree, but kind of uh tells you to manually do it. Right? All the hard work of what does it mean if you have two conflicting updates? Which one should win? Well, you have to decide manually. And functional persistence is a bit closer to what functional programming want. Uh and then you could go even crazy, uh retroactive data structures. I'm just listing the buzzwords in case you're curious and want to look for it. is data structures where you can do updates in past versions, and then they should be reflected in in future queries and so on.

5:22 Uh this is One reason I didn't dig further into this is also I I I wasn't convinced of the applications. >> [laughter] >> Whereas for uh partial and maybe full persistence, there's a more convincing arguments. That's That's roughly the plan. Now, of Of you can for every data that you uh can think of, you can start building a persistent version. And for every notion of persistence and every data structure, you can try to build some. So, that's that gets very messy in a huge space. Uh we'll see that we fortunately don't have to do that. Okay, for for large parts.