The way I've done it so far is seems to be working, and I've implemented standard types (their introduction and elimination rules) and few functions on them. The two main problems I've run into is memory leaking and portability.
Since the constructors of an algebraic data type should return const data, it's a bit difficult to free them without violating the type system. I haven't decided yet if I'll end up violating the type system or just drop that const. I think the latter makes more sense, since we're trusting C as little as possible in the first palce. Everything actually might as well be done in void pointers but I think there's some value in using types where possible for documentation's sake.
About portability. The main thing here that I ran into was that there's no real standard and portable way of doing closures or anonymous functions in C yet. Right now, what I'm doing is using nested functions, which works in GCC and clang, but I have no idea if they'd work in MSVC or any of the other compilers out there like pcc and lcc. OS X has blocks, but I figure if they're using gcc too, why not stick with nested functions. As far as I can tell, I won't have the problem of having nested functions returning before their parent does because of the eliminator model.
The libCello (http://libcello.org/) author has been able to successfully model typeclasses in C, so I will be picking that up as soon as I get around to it.
I pushed some of the code to GitHub just now for this post: https://github.com/guerrilla/libalgae
I'm glad to hear other people had the same idea. If anyone has any suggestions, please let me know, as I wouldn't mind some collaboration on this.
It's not only that purity is safe and beautiful. It's also in many cases much easier to understand, because it's about writing functions that express transformations. These transformations should make sense in a conceptual way.
When you distill your domain concepts (see "Domain-Driven Design") and write pure functions on domain data, the result is remarkably clear, testable, and debuggable, no matter which language.
Previously I would have been (prematurely) concerned with the efficiency of in-place updates, but since I'm not writing high-performance CPU-bound software, I don't care about that anymore until the profiler tells me to.
The best code in the system, IMO, consists of small stateless singletons with clear dependencies and non-modifying operations. This code often comes out of test-driven development and has tests that read like specifications.
The nice thing about Haskell is that it conceptually mallocs a fresh array to return, but then optimizes away the intermediate array in a lot of cases.
Speculative guesses as to what might stand in the way:
1. The lack of a purity-tracking mechanism like Haskell's may make programming in this style in C more complex and error-prone.
2. The fact that C compilers don't expect you to use this programming style may mean they don't optimize common operations in the way Haskell does; for example, if you do manipulations on large arrays in a functional rather than imperative style, Haskell will optimize away a lot of the temporary arrays, but C compilers may not.