Hi, everybody!
How we doing?
Got caffeinated?
Feeling good?
Nice.
So, I'm Anjana Vakil, hello!
You can find me on Twitter @AnjanaVakil
and today I'd like to talk to you about immutable data structures
for functional programming in JavaScript.
We're going to take a look at what immutable data structures are,
why they're a really cool way to handle the immutability
that we typically use when we're doing functional programming
and how we can do that in JavaScript
because I hear y'all like JavaScript!
So, a little about me.
I'm probably the only not-web-developer in the room.
I am an engineer for Uber Research.
I work with them to develop a custom query language for data
in the scientific research funding domain.
I'm also an alum of the Recurse Center,
which is a fantastic programming community in New York City,
and I am an alum of the Outreachy Program,
which, if you have haven't heard of it,
is an amazing initiative
to get more women and underrepresented folks
involved in open source projects
by offering paid internships at organizations like Mozilla.
So, I'm also a Mozilla community member
and a Moz tech speaker.
So, I am really happy to chat about those things
if you want to come grab me after the talk.
But you might know that I like functional programming.
I think it rocks.
Anybody else agree with me that functional programming is cool?
Yeah! Yeah!
So, functional programming is a pretty great way
to avoid some of the headaches of other paradigms
like imperative or object-oriented programming.
In functional programming,
what we typically do is conceive of our programs as being just pure functions.
That means that they transform their inputs into outputs,
and that's all they do.
They don't have any side effects,
things like printing to the console
or mutate or changing something in the global state
would be side effect.
Don’t do any of that. None of that.
So, our functions become just pure data in, data out,
like transformers of data.
And one thing that goes hand-in-hand with this avoidance of side effects
is using immutable data.
Immutable data meaning once we've created it, it never changes.
So, this is a really good way
to avoid accidentally changing something outside of your function.
If everything is immutable, you can't change anything.
So, immutability is another thing that rocks
and it rocks pretty hard for some reasons that we'll see in a moment.
But speaking of rocks, let's talk about rocks.
So, this is a rock,
and immutability rocks in the way that rocks rock.
Now, I don't know about you,
but I've been going to a lot of tech conferences recently
and I've been feeling like there hasn't been enough poetry.
So, I'd like to read you a poem.
Nobody sits like this rock sits. You rock, rock.
The rock just sits, and is.
You show us how to just sit here, and that's what we need.
It's so true, so deep.
This is from – Thank you.
Don’t thank me, thank I Heart Huckabees, it's a great movie.
Check it out. Very funny.
So, this is really how immutable data rocks.
It just sits there.
It just is.
Once we've created it, it never changes
and that's amazing
because it helps us avoid some of the headaches of immutability.
So, with immutability, we have some things pretty easy,
but other things become harder
and we'll see how that looks.
So, let's say, I have an array called foo and it's got some numbers in it.
And I'm already bored.
Okay, let's make it more fun.
Let's say I have a zoo with some animals. More fun!
And I decide that I want to change something up about my zoo.
Maybe I want to replace that rabbit there with something a little more exotic.
Like an alien.
So, this is cool.
I'm happy because I wanted a more exotic zoo.
I got an alien in my zoo now.
I didn't have to change anything except for that one little cell in my array.
That's pretty sweet
but my co-worker over there
was expecting zoo to be full of like Earth beings, Earth animals,
and wasn't accounting for there being an alien in it,
and it's like, who put this alien there?
Now my program doesn't work anymore.
Aaah! Who did that?
Immutability has a couple of problems.
We have to manage who's been changing what, when,
who's been putting which animals in the zoo.
We have to have a lot of overhead to manage that state,
and that gives us headaches as individuals and as teams.
We also get bugs in the code
because maybe I was only planning
or my co-worker was only planning to handle terrestrial beings
and didn't have the case of aliens accounted for,
and that broke something.
So, these are some side effects of immutability that don't make us happy.
Let's try doing things the immutable way.
So, in an immutable world,
my array, my zoo, once I've created it, it just sits and is forever.
I cannot change it.
What I can do if I want a new zoo that's more exotic
is I can make a copy that's the same size as my original array,
and I can make the modification that I want,
so I can put my alien in there in place of the rabbit.
And then I can copy over everything else in the array that didn't change.
So, this is pretty sweet because now my co-worker is happy.
They're, like, whoo, nothing broke in my program,
and it's all still Earth creatures
but I had to copy over that whole array.
I had to allocate the space for the entire array,
even all of the stuff that didn't change.
I had to copy all of that over as well.
So, this means that my code runs pretty slow
and it also takes up a lot of memory.
It takes up a lot of space and time.
The complexity on those things are bad
because copying is a waste of both time and space.
It makes a sad face.
We don't want that.
So, if we want to do immutability,
we must be able to find a better way of doing that.
Luckily for us,
a lot of very smart folks
have been thinking very hard about this problem for a while,
and they've come up with some really good solutions
to how we can deal with immutability efficiently.
Immutable data structures!
So, immutable data structures is a term you may have heard bandied about,
especially in conjunction with functional programming,
or perhaps also with React where they also come in very handy.
Technically, an immutable data structure
is just any data structure that’s like the rock.
Once you’ve created it, it just sits, and is.
It never changes.
But also you hear the term persistent data structures bandied about.
Sometimes these are used interchangeably,
although they have slightly different meanings.
So, if immutable data is just data that never changes,
persistent data structures are ones for which
we have some kind of access to old versions.
So, as we've been creating like new modified versions of our data structure,
we keep the old versions around.
You might hear about partially persistent data structures
where we can look at the old versions,
we can access them,
but we can't go back and update any of them.
All we can update is the most current version that we have.
And then you might also hear about fully persistent data structures
where we can actually time travel,
we can go back and update any of our past versions.
And if this is starting to ring a bell
that sounds little bit like version control, like Git,
it's sort of the same idea.
So, we're going to talk about these as persistent immutable data structures,
they're both persistent and immutable.
Let's see how this works.
The key to all of this is that we want the old versions of our data,
like, my original zoo to stay put.
We want them to just sit like the rock
but we want new versions to be created efficiently.
So, what magical tricks do we have to use to make this happen?
Do we have to make invocations?
Do dances to the gods of space and time complexity?
No.
It's very simple.
Trees and sharing.
Isn't that sweet?
These two simple concepts will get us efficient immutable data.
How?
So, let's talk about trees because trees rock pretty hard as well,
although unfortunately I don't have a poem for that, sorry.
Imagine that we could find a way to represent our zoo array as a tree.
So, one thing I could do is I could put all of my animals,
all of my values, in the leaves of a tree,
and I could make it so that each leaf holds one value, one animal.
But they might get lonely,
so let's put them with a buddy.
Let's put them 2 x 2.
So, each of our leaves will have two values
and we'll hope that the buddies get along
and none of them eat each other,
looking at you, tiger, number six, don't eat that koala.
And then we can connect them together with intermediate nodes
and go up and up
until we get to the root node that connects the whole structure,
and that root is now our previously array, now represented as a tree.
So, this is my zoo now in a tree structure.
So, given this type of structure, how do we update something?
Given that my zoo is immutable, it can never change,
how do I get a new version that has my alien in it?
So, here what I need to do is
take the node that contains the value that I want to change.
So, in this case that would be the 0/1 node
which is on the bottom left that you are seeing
and I have to copy that over
changing the thing that I would like to be different.
So, I make a new copy where I've still got my monkey
but I've changed the rabbit to an alien.
And then I need to copy any of the intermediate nodes in the tree
that were pointing to the node that I changed.
So, I basically trace a path up towards the root of the tree,
which now I've got a new root,
which means a new version of the data structure.
So, this technique of making this update
by copying the path from the leaf I changed to the root
is called path copying.
That's pretty cool
because now I didn't have to copy the entire array;
I just had to copy the nodes
on the way from the root to the leaf that I changed.
So, we've turned in something linear
and copying into something logarithmic.
That's pretty cool, that's more performant.
And the beauty of this is that all of these nodes in yellow here,
so most of the tree is shared between the two versions,
between the old version and the new.
So, this saves me a lot of space
because I can actually reuse the parts of the original version that didn't change,
whereas before, I had to copy those over as well.
So, this means that
what was before like a lot of memory consumption becomes much smaller
because I don't have to store as many copies of the things if they didn't change.
That's called structural sharing
because we're sharing the structure of the tree between the two versions.
So, we've been talking about updating things
but how do we get at the values in our data structure?
How do we access them?
Well, it turns out this isn't just a tree,
it's a special type of tree called a TRIE tree,
which originally came from the world "retrieval,"
so people I guess could pronounce it tree
but that’s confusing because we also pronounce T-R-E-E tree,
so we are going to call them "tries"
because that's sort of what it looks like.
So, our tree is a trie.
That’s cool.
A trie is a type of tree where the leaves hold the values of our data as we saw,
and the paths from the root to the values
represent the keys that that data is associated with.
So, often you see tries used for storing things like words as keys.
So, for example, if I have the word T as one of my keys,
what I do to get to the value associated with T
is I traverse the tree one letter at a time.
So, from the root I go to T,
then I go to E,
and then I go to A,
and I get TEA as my key,
and my value there is 3
because everything else sound like "e" in this talk, for some reason.
So, this is pretty cool,
but in our data structure, we weren't using words as keys,
we just wanted an array-type thing, we wanted indices, right?
So, the insight here is that if we treat the index as a binary number,
then we can pretend that that's kind of like our “word”
and we can descend the tree bit-by-bit
as if each bit in our binary representation of our number is a letter.
So, let's see how that works.
If I'm trying to get at item 5 in my array,
so the animal at index 5,
I'd convert that to binary,
so that's 101,
and then I step through that as if it was a word.
I step through it letter-by-letter, bit-by-bit.
So, I go from the root to the branch.
I have a choice of either 0 or 1.
I go to branch 1 first.
Then I go to branch 0,
and then I take the thing on the 1 side.
So, I go 1, 0, 1 down my tree
and I end up at my frog in index 5.
So, this is a pretty simple insight
but it ends up being incredibly powerful
because it allows us to quickly traverse this tree structure,
which lets us use that structural sharing
to more efficiently represent our new copies of our immutable data structure.
And importantly, we don't have to be using a binary tree,
meaning we have two branches from each node.
That fits pretty well on a slide,
but actually what you mostly see is a 32-way branching.
So, in our trees that we've been looking at,
we've kind of had one bit of information per level.
And we've been descending bit-by-bit,
but if we had a 32-way branching tree,
it would be five bits of information
that we would be representing at each level.
So, that would look something like this.
If we had a much bigger number, like 18977,
in binary that's that bunch of 1s and 0s,
this would be a really deep tree
if I had to descend it one bit at a time, right?
It would be like 15-levels deep.
Too much, too long.
So, if I'd make more branches at each level,
then I can chunk this up into kind of 5-bit letters as it were,
and descend the tree that’s now only three levels
using the 32-way branching.
So, this is kind of a tradeoff between how deep your tree is going to be
and how big the nodes are going to be
because if I have just one bit of information at each level
then I have really small nodes.
That's quick to copy over,
but I have to go very, very deep down the tree for a larger array.
And generally, research has found that 32 tends to be a pretty good tradeoff
between the size of the nodes and the depth of the tree.
Okay. So, we've just seen what's called often a Bitmapped Vector Trie.
Sometimes also called a Bit Partitioned Vector Trie.
That's just jargon.
We don't need to care about that.
But if you want something to Google, you can Google that.
This is cool for array-type things,
where we have an index that we want to jump to,
but what about objects?
We also want to be able to associate values with arbitrary keys, not just indices,
so we want non-integers as keys.
How does that work?
So, if I want a version of my data structure where it's no longer an array
but it's something like an object
where I'm associating letters with each of my animals,
like M for monkey, and P for panda, etc.,
what I can do is I can take my keys,
in this case, they're letters,
and hash them to get a number that represents the key,
so that each key will have its own number.
They won't be in order necessarily, but that's okay.
Objects don't have to be in order.
And then we can use the hash of that number in binary
to descend the tree as before.
So, if I wanted to look up the value associated with key "F,"
I could hash F, get some number,
let's say I get 5,
like, A, B, C, D, E, 5,
that would be represented in binary as 101,
and again I descend the tree as before.
Here, for simplicity, just using a one bit at a time,
two-way branching tree.
But typically, we would be doing this with 32 branches per level.
So, again, we just descend the tree using the binary representation of our key.
In this case, we used a hash function to transform it
from some arbitrary object into a number
and we get the animal we want.
In this case, our frog.
Cool.
So, that, if you want to Google it,
the thing you could Google is a Hash Array Mapped Trie.
And this is a data structure that was sort of pioneered by Phil Bagwell,
and then Rich Hickey implemented them in Clojure,
and a lot of what I have been talking about
is kind of inspired by work in languages like Clojure
to implement these data structures efficiently.
There's a ton of other optimizations
that are usually done on these data structures
to make them super-duper fast
and lots of details that we're not covering here,
but this is the basic idea.
Trees to represent our data,
structural sharing
so that we can reuse as much information as possible
between the old versions and the new versions,
and this idea of using binary representations of our keys,
whether indices or hashed keys,
to descend the tree to find the thing we're looking for.
So, to recap, mutability induces headaches.
It is to be avoided especially if you're doing functional programming
where the essential idea is to not have side effects
and only be using pure functions that don't change anything
except do the computation on their input and return a new output.
Immutability, on the other hand, is great
because when I'm using immutable data,
I can't mess up my co-worker's program
by making the zoo that she thought was all Earth animals
suddenly have an alien in it.
But copying is a really bad way of handling immutable data
because it is not efficient neither with respect to time, nor with space.
And structural sharing,
using these tree structures or trie structures,
and using structural sharing
to save as much information as possible from one version to the next
is the really performant way to do this.
So, you're probably thinking, okay, these data structures are cool
but what am I supposed to do with them?
I'm not going to be like building boxes of emoji here, am I?
No, you don't have to.
In JavaScript, there are some really great libraries out there
to help you use these right off the bat.
There are various solutions
but I'm going to talk about a couple of them.
So, one is called mori.
Mori is basically a port of ClojureScript by David Nolen
that allows you to leverage the implementations of these data structures
from ClojureScript,
which is the version of Clojure that targets JavaScript
from the comfort of your vanilla JavaScript.
And it's got a bit more of a Clojure feel to it,
little bit more of a functional language feel.
The API is functional
and we're going to see what that looks like in a moment.
But that's one thing that kind of sets this library apart.
On the other hand, there's also Immutable.js.
This is a library put out by Facebook.
It was created by Lee Byron.
And this is a JavaScript implementation of these data structures.
So, it has a bit more of that native JavaScript feel to it.
It doesn't have the kind of the Clojure background brought in.
And that means it's got a more object-oriented style API,
although it is still returning new versions of data structures
instead of changing mutable structures in place.
So, let's see what those look like.
This is how you might use mori to create what's called a vector.
A vector is the data structure from mori
that you'd probably be using as an array-type thing.
So, I've got a vector that I'm calling 'a' because it's sort of array-ish.
It's got 1 and 2 in it.
And if I want to push something onto that,
the function that I'd use is conj.
This is from the Clojure world lisp-speak.
And what I would pass in to the conj function is the original copy a,
and the thing I want to add on to the end,
so in this case, 3.
And you'll see that that creates a new data structure on the right.
These vectors [1 2] and [1 2 3],
they look a little bit different than regular JavaScript arrays
because they are Clojure vectors,
they are not really JavaScript arrays,
although you can convert back and forth.
But the point is that this conj function returns a new value
which then I can catch as a2
I can capture that,
and I can prove to myself that my original a didn't change
by using the count function to see how many things are in it.
There's only two things still in it.
But I can prove to myself that my version, a2, has the third thing
by trying to access,
by using the get function to access the item at index 2,
the third thing,
which it tells me is indeed 3.
Cool.
This is how you would do the same thing in Immutable.js.
Here you would use Immutable.js.list.of,
it's a little interesting syntax there.
And there it creates something that looks a bit more like a JavaScript array
although it is not a normal array,
it is an immutablejs.list.
That I'll call a
and then if I want to add something onto a new version of a,
I use this sort of dot-method notation that we're used to.
I'd say a.push(3),
but, importantly, this is still not changing a.
It kind of feels like it should be but it's not,
it's just returning a new version of a,
which I'm going to capture as a2
and I can prove it to myself that a didn't change.
a.size tells me it's still 2,
and if I try to get the item at index 2 from a2,
I find that it's 3, as I expected.
So, similarly, for what are called maps,
which is kind of the key-value object that we might be using,
if I create an object o,
which is going to be my mori.hashMap data structure,
I'm associating a with 1, b with 2,
again, we see that the syntax for these is a little bit different
than our regular JavaScript objects
because they are not regular JavaScript objects.
They're super special immutable data structures,
they need special syntax.
So, if I want to change the value of one of my keys,
I can use this asoc function,
pass in my original map o,
and then change the value of a to 3 in my new version o2,
and again I can prove to myself that the original didn't change
by using the get function
to make sure that a in the original one o, is 1,
and a in o2 is 3,
as I would expect.
And it looks quite similar in Immutable.js
except the data structure is called Map, not hashMap,
and I can pass in a little object, a little JavaScript object,
and it creates me a Map o,
that looks again little bit more JavaScript syntax that we're used to.
This has a bit more of a syntax and a feel
that you might be used to from JavaScript programming.
I can use the set method on o to create a new version where a is now 3,
and I can use the get methods on my old version o, and my new version o2
to prove to myself that the old one didn't change.
So, these are really immutable data structures.
They look really weird if you try to look at them in the console
just as JavaScript objects.
They're really fun to kind of poke down into
because they have this complicated tree structure.
So, I highly recommend you try out these libraries
and see what works for you.
I can tell you really just briefly before I run out of time here,
that how they compare is basically, again, mori is from the Clojure world,
it's ClojureScript.
Immutable.js is from the JavaScript world.
That means the Immutable.js has this more object oriented,
o.get kind of feel to it,
which might be comfortable
if you are used to writing JavaScript that looks like that.
However, for me, I find it a little bit...
it gives me a little bit of a cognitive dissonance there
because it looks like we're mutating things with that method,
those method calls.
We're not, we're not,
but for me, to get more into the mindset of functional programming,
I prefer the functional API of Mori
because we are really getting used to
the way that we want to conceive of everything as pure functions
that just take inputs and return outputs.
We don't even want to be kind of in the mindset
of making changes in place to objects.
There's also some minor performance differences between the two,
Mori is a bit faster, Immutable.js is a bit smaller.
But they're both great options,
try them out,
hope one of them works for you.
So, that's my talk.
I hope it's been useful.
Go forth and don't mutate your data.
Here's some references for you.
Thanks.