Zack Kayser: Demystifying Purely Functional Data Structures in Elixir

Reasoning about data structures and run times in functional languages like Elixir is a far cry from classic analysis of data structures in imperative languages. While working with immutable data structures helps us reason about the flow of state in our programs, it has implications on the data structures we choose to work with and the efficiency of operations on those data structures. We will start by briefly laying some groundwork for analyzing functional data structures and discuss some optimizations used to prevent unnecessary copying while maintaining immutability. We’ll move on to take a look at some basic data structures implemented with examples in Elixir and then discuss their characteristics. Starting from naive implementations of these basic data structures and related operations on them, we will consider how to further optimize operations to draw out more efficient run times. The talk will wrap up with a discussion of how to build an intuition for creating more efficient data structures in Elixir.