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.

>>15
See encourages the programmer to stay within reasonable constraints for performance. Haskell encourages the programmer to avoid thinking about performance, and forces a model that incurs overhead, while the programmer hopes the compiler is clever enough to optimize away the overhead, and at the end of the day it turns out it isn't.

If you want a thread safe malloc you can write your own. You can use pure functional data structures in C by just allocating things and not modifying them. And in parts of the program where a different model is more useful, you can do that instead. It's not a big deal to go between the two. They can, and should coexist.

>>17
the programmer hopes the compiler is clever enough to optimize away the overhead, and at the end of the day it turns out it isn't.
99% of the time the overhead doesn't matter, because on a computer capable of running an OS, you don't need to care. (Embedded applications, by your logic, will do better to be entirely in ASM rather than C, because of performance.) If the overhead does become a problem, you can tune the fuck out of it[1].

If you want a thread safe malloc you can write your own.

Sure, just bang one out over the weekend. It's not like there are many malloc implementations already.

You can use pure functional data structures in C by just allocating things and not modifying them.

That's immutable, not functional. And while you're doing that, you can enjoy writing your own garbage collector to go with it, and for every new allocation you can convince yourself you're doing it for performance.

Sometimes, I don't believe that people can believe what they are saying. This is one of those times, and you are one of those people.

[1] http://book.realworldhaskell.org/read/profiling-and-optimization.html