Functional Data Structures

on YouTube ↗10m

" summary

Compares four Elm binary-tree implementations and concludes Elm’s union types produce the clearest code. Starts with an array-based layout using child indices 2i+1 and 2i+2 and shows the waste of using Maybe to mark empty slots. Switches to core Dict to avoid filler, then to record-based pointers (recursive type required) with full insert and remove, and finally to a compact union-node type. Builds working insert and remove for pointer versions and shows the union-node is simplest and most readable.

AI-written summary · about

" chapters (6)

1. 0:00Introduction to talk
2. 1:37Array-based approach
3. 5:14Dict-based approach
4. 6:18Pointer-based approach
5. 7:43Simplified node structure
6. 9:12Comparison and summary

" related talks

• 01h 32mAlgorithms for Trees - Foldable, Applicative, TraversableSteve Downey · C++Now 2026
• 47mPurely Dysfunctional Data StructuresGrzegorz Piwowarek · JDD 2019
• 14mThe Extensibility ProblemRobin Heggelund Hansen · Oslo Elm Day 2019
• 29mRepresenting Data Structures with Invariants in Haskell: the cases of BST and AVLNicolas Rodriguez, Alberto Pardo, Marcos Viera · TyDe 2025
• 48mPurely Functional Data StructuresGrzegorz Piwowarek · GeeCON 2019
• 32mFunctional implementation of Finger Trees in JavaScriptVlad Patryshev · Scale By the Bay 2020
• 48mFunctional data structures in JavaOleg Šelajev · Voxxed Days Zurich 2017
• 48mPurely functional data structures demystifiedMohit Thatte · Functional Conf 2014