Programming with Data Structures

Now I want to talk a little bit about the data structure library in that we've built in Mathematica. So these data structures are. It's a library, a set of classical data structures. They're built using the compiler, but you don't have to. You can use them without the compiler. And they provide some new features in the system. So they provide a mutable state, which is. There haven't been. It's a new form of mutable state, hasn't been in the system before. And they were introduced in 12.1 and we worked to sort of build them up ever since. So here's an example of to. There we go. Extensible vector. So this is a vector, like a list, but it's something that's fast for appending and prepending. So I can call an append method. And so now this thing has a length of one. Or I can get. I can get like a norm. Why is that? There we go. Or I could ask for the. The elements of the thing and it shows me the. And I can also see, you know, it supports a bunch of operations you might see here. So these are all the operations in the documentation. So one of the benefits of this is that if I want to do lots of like collect results, I can do fast appending and prepending. It's pretty fast. And just to compare, you know, with a traditional list, doing the same operation is a lot slower. So if I want to write some code and pass something like a bag that I want to add things to the end or the beginning, or extract parts or elements or do various operations, this is a nice way to work with it. So let's just have a quick look at some of the data structures that. This is the current list of data structures that we support. So some things, you know, like this is like a core set. So there's a value, just stores and retrieves a value. There's a counter, it's quite useful for passing something around, for incrementing. And there's this thing called an expostruct, which is a way of wrapping up Wolfram expressions, holding them where they can be passed around, but they don't evaluate. We have a bunch of these container type structures. So some of the things that some people like, if you want queues or stacks, those are particularly useful. So that's. People have written packages and things, but this is going to be tons faster and it clears up the memory and everything as you go along. There's various set type of operations. So again, if you want to just collect Some unordered thing. This hash set is particularly useful. There are a bunch of tree type of data structures. KdTree is a bit. Is that really a tree? I don't know. And there's these key value stores. So there's a key and a value. So hash table is a common version of that. So now let's have a little look at the binary tree data structure. It has some. This is for reasons, I'll say this is a bit more pedagogical, but it's good for showing some features. So one of the nice features of the binary tree, of all the data structures is they have a. Some sort of visual representation of the, of the thing. Obviously for a tree type of thing, it plots. Plots the tree. And here are some of the operations of the binary tree. So there's various ways of testing what's. What's there and navigating through the thing. And then you can, you can scan over, do various traversal things. So you can write programs that work with these trees. And so here's something that is going to take a tree and some data and it's going to go down through the tree trying to find a place to insert the data where it's maintaining some sort of order to read all this. Because if you see what this does, it's. So I'm inserting a whole load of. It works. It's all quite nice and I get the visualization. And you can see here, as you pass through the tree, it's ordered everything. So this is quite nice. I can insert things and look things up and it's sorted and ordered. So that's all quite useful. But of course, with people that do data structure courses, quickly learn there's a negative thing because it's not really caring. There's different choices about where you insert things and not taking care of the choices for this, you can get some very unbalanced things. So this thing here, if you want to look up element 20, you've got a lot of work. It's. There are 20 elements and looking up the 20th thing is going to take 20 operations. So you've not really, you're not really saving anything from the tree structure. Now there's another tree structure that's called like an AVL tree. There's a bunch of different ways of balancing. There's a huge, huge amount of study and knowledge on these things. And this is an AVL tree that rectifies these problems. And as you insert things, it rebalances the tree and it has some. It makes sure that it never gets, gets too unbalanced. And so this is always more, much more optimal for inserting and sorting and things like that. So these, these trees are quite useful. And then of course you can use one data structure to build something a bit more, you know, a bit more complicated if, if necessary. Now I want to talk a little bit about how the data structures, you know, they're built with compiled code and see a little bit how they work within compiled code and some ways of working like that. So here I've created a. What I'm doing here is I've created a counter and then I'm doing a scan over a list of data. And if the thing's even, I'm going to increment the counter so I can write compiled code. So here's a compiled function that's doing essentially the same thing. And so it goes scanning over, passing in a packed array and a counter. So the counter itself has a type, which is counter. And then I can run over this and it's set up scan so it returns nothing. But if I look at the counter, I'm getting the same, the same result. So I can work with this in compiled or uncompiled code. Here's another example. So I could write. So the extensible vector that we looked at earlier does not have a reverse function, but this is what a reverse function could look like. So I could create a thing. So I call it. So this is an interpreted version. So now I've reversed the elements. So now I'm going to use down values function. So I just make a declaration using downvalues function. And then I'm going to compile the reverse of that downvalues function. And so I'm taking the same function declaration. So this is now extensible vector. And so when I run this, it reverses it. So that's, that's good. And again, you know, nice thing about this is it's a lot faster too. So that's the uncompiled and the compiled version quite significantly faster. So it's quite easy to add if there's some feature or something that's missing. It's quite easy to add that and then to compile it. And you could put that declaration in a component or something to reuse it. And so again, I'm just showing, you know, you don't have to compile everything in your code. You can just compile perhaps expensive parts or you could just use data structures to sort of speed things up. So this compilation of data structures, it works for you know, all of the data structure things you can do in top level, you can do those in compiled code as well. Like all the operations and create data structure and such like. So now I want to talk a little bit about these data structures because many of them, they're actually parameterized by their contents. So here we can see some of this. So I'm going to compile a. So it takes an extensible vector and it returns the first element, first part. And so actually it's. The result is an inert expression. So this is the, what I'm doing here is the. By default, the extensible vector is being understood to be one that works on expressions. So this is the natural expression of the Wolfram language. So that's, that's, that's, that's all pretty useful. But I could make. Here I've got another function. So I'm taking an extensible vector, but it's, I'm inserting a machine integer. So now it said, aha, this is an extensible vector, but I'm putting an integer into it. So that means it's an extensible vector of integers. And I could do. And here's yet another thing. So I could also write it like, like this. So if I want, if I know I'm always working with extensible vectors of machine integers, I could write it like that. So that's showing that these data structures are polymorphic. And then to create one, I would use create data structure in a compiled function. And then I could work with it like. So. So the key point here is that I can pass these compiled objects in and out of the evaluator. I could also go and set up some nice formatting for that. But that's kind of how these data structures are being built. So another aspect of the data structures, this is another type of data structure is an immutable vector. And this is something that, so I've got, I created one and then I did an append operation. But this append operation returns a new version of the data structure. So this one here, this vector, the thing that I did, the append. If I did like, maybe so if I did like normal of this and. But if I do normal of the original one, it's unchanged. So the operations work. And this is all quite efficient. So it's, you know, it's, you know, it's, you know, it's a lot faster than doing. It's combining sort of immutability, but it's also efficient as well. And so this is a Little bit like the. Whoops. Hang on. So contrast with summary. Yeah, there we go. So it's a bit like. I mean, this is. Actually uses a very similar algorithm to the thing that's built into association, but this is something that looks like a vector, so it has numbered, you know, sequential parts. And so you can append and prepend and look things up in it, but it's immutable. So. And it's quite suited to Wolfram language. So now this is the end of my data structure talk, and I'm doing too badly on time. So I'll just summarize. Showing you the Wolfram data structure library collection of classical data structures, mutable and immutable, and you get a lot of nice speed advantages. You can use these things in compiled code and they all have this sort of polymorphic nature that might be relevant. So, any questions on data structures?

Yes, or something like. I don't know what the internal structure is, but for reap and so functions.

Right.

Those automatically using these.

No, those are older things, so they're not. But they certainly could be using data structures. And this is an alternative way of. Of working with things. So you could. Yes, so you're right. This is functionally similar, but if you want to accumulate things, it might be sometimes that the reap and SOW pattern is a bit restrictive, so it's harder to fit that into what you want. So you could pass things around and you could do a little bit of sowing wherever you want in some ways, or you could re. Enter the thing and do a bit more sewing outside of the reap. So it's. There's advantages and disadvantages to doing that. But yes, that's. You understand the correct. You're understanding correctly there. Yep. Yes.

What's the status for the documentation?

Well, there's documentation that's. That's built in and we add examples and things like that.

So it's like.

Well, I mean, it depends what you mean by fully documented. So, I mean, you can look up, I don't know, Extensible vector, some of more. I mean, this is a documentation page. This typical. I'm not sure there's examples. Some of them have more examples and some of them have fewer. So, yeah, this is one that's got a bunch of sorting algorithms. So some of them have fewer. So. But that's the idea. I mean, if there. If there are weaknesses in this, then, you know, you know, sort of file them and then we could improve that. So. Yes. Right. Do you want some other form of documentation or.

I think mainly it's just curious. Just the functions or.

No, they're individually some of them have better good like the binary tree has lots because they're kind of fun. Or that that, you know, we implemented a bunch of algorithms, so. But yes.