Have you read your PFDS today?

Purely Functional Data Structures
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

When a C programmer needs an efficient data structure for a particular problem, he or she can often simply look one up in any of a number of good textbooks or handbooks. Unfortunately, programmers in functional languages such as Standard ML or Haskell do not have this luxury. Although some data structures designed for imperative languages such as C can be quite easily adapted to a functional setting, most cannot, usually because they depend in crucial ways on assignments, which are disallowed, or at least discouraged, in functional languages. To address this imbalance, we describe several techniques for designing functional data structures, and numerous original data structures based on these techniques, including multiple variations of lists, queues, double-ended queues, and heaps, many supporting more exotic features such as random access or efficient catenation.

In addition, we expose the fundamental role of lazy evaluation in amortized functional data structures. Traditional methods of amortization break down when old versions of a data structure, not just the most recent, are available for further processing. This property is known as persistence, and is taken for granted in functional languages. On the surface, persistence and amortization appear to be incompatible, but we show how lazy evaluation can be used to resolve this conflict, yielding amortized data structures that are efficient even when used persistently. Turning this relationship between lazy evaluation and amortization around, the notion of amortization also provides the first practical techniques for analyzing the time requirements of non-trivial lazy programs.
 
Finally, our data structures offer numerous hints to programming language designers, illustrating the utility of combining strict and lazy evaluation in a single language, and providing non-trivial examples using polymorphic recursion and higher-order, recursive modules.

>>30

But even in these simple cases, it's stupid that you spend your time wrangling bytes instead of teaching the machine how to do it for you. Have fun reinventing the wheel every single time.

You assume too much about me. 60% of my time is devoted to meta linguistic abstraction. The difference between me and you is you depend on prepackaged abstractions that fit one and only one paradigm and introduce overhead, while I have the freedom to engineer my abstractions and how they target the machine I'm using. You force yourself to choose from a limited set of abstractions while I'm free to invent my own.

>>31

When it matters, you can make the overhead disappear.

In theory yes, but in practice no.

This is an amusingly substanceless rebuttal. If you are so enlightened, would you care to sketch out an immutable, shared tree, with minimal memory overhead, and without nodes and branches? Or are you saving that for your master's thesis? Or HIBT?

Using garbage collected nodes allows you to use a shared data structure with the most generic user interface. All your program has to worry about is managing references, which would be a concern in C using a gc library or reference counting, and built in to the language in others. If you restrict the user interface, you can do better. If you really study how your program is utilizing a shared data structure, you'll likely find the interface is overkill, and you can manage with a substitute in which lifetimes of objects can be anticipated. You could say I use these concepts but then optimize their use away at compile time.