Fmjrlhm2nexd5j1my0zw
SkillsCast

Meetings With Remarkable Trees

13th December 2018 in London at Business Design Centre

There are 50 other SkillsCasts available from Scala eXchange London 2018

Please log in to watch this conference skillscast.

Https s3.amazonaws.com prod.tracker2 resource 41088130 skillsmatter conference skillscast o9nohu

Everybody knows the classic cons list. Clojeurs brag about their bitmapped vector tries. Haskell weenies took it up a notch with their impossible finger trees. Rustaceans turned back the clock and gave us simple arrays again.

All of these have shortcomings. Hickey tries are magically indexable but the only other thing you can do to them is add things to the end. Finger trees are absurdly flexible but you can’t index them efficiently. And so the search goes on…

And today, you’re going to learn about the ultimate list data structure: the RRB tree ('relaxed radix balanced tree'). It is an improved version of the tried-and-tested Hickey trie and has achieved the impossible: every basic operation is efficient - push and pop on either end, index lookup, split and join. RRB trees pull no punches.

Watch as Bodil shares diagrams with brightly coloured boxes in an enthusiastic effort to explain why RRB trees are amazingly exciting.

YOU MAY ALSO LIKE:

Thanks to our sponsors

Meetings With Remarkable Trees

Bodil Stokke

Bodil works as a computer science researcher for a secretive think tank, and is a world renowned expert in varied fields such as pizza and persistent data structures. Contrary to popular rumour, she only has five fingers on each hand, but is still an Emacs user.

SkillsCast

Please log in to watch this conference skillscast.

Https s3.amazonaws.com prod.tracker2 resource 41088130 skillsmatter conference skillscast o9nohu

Everybody knows the classic cons list. Clojeurs brag about their bitmapped vector tries. Haskell weenies took it up a notch with their impossible finger trees. Rustaceans turned back the clock and gave us simple arrays again.

All of these have shortcomings. Hickey tries are magically indexable but the only other thing you can do to them is add things to the end. Finger trees are absurdly flexible but you can’t index them efficiently. And so the search goes on…

And today, you’re going to learn about the ultimate list data structure: the RRB tree ('relaxed radix balanced tree'). It is an improved version of the tried-and-tested Hickey trie and has achieved the impossible: every basic operation is efficient - push and pop on either end, index lookup, split and join. RRB trees pull no punches.

Watch as Bodil shares diagrams with brightly coloured boxes in an enthusiastic effort to explain why RRB trees are amazingly exciting.

YOU MAY ALSO LIKE:

Thanks to our sponsors

About the Speaker

Meetings With Remarkable Trees

Bodil Stokke

Bodil works as a computer science researcher for a secretive think tank, and is a world renowned expert in varied fields such as pizza and persistent data structures. Contrary to popular rumour, she only has five fingers on each hand, but is still an Emacs user.

Photos