Subj : Re: any function to handle this kind of counting?
To   : comp.programming
From : Jon Harrop
Date : Sun Jul 31 2005 03:10 pm

Peter Ammon wrote:
> Jon Harrop wrote:
>> 1. Stability (many relevant bits of OCaml's stdlib have been formally
>> proven correct using theorem provers and will have been used by many more
>> people than a "home grown" C implementation).
> 
> I'd wager that more eyes have looked at something like the GLib C data
> structure library than at OCaml.

I'll wager that formally proving something correct improves stability more
than having "eyes looking at it".

>> 2. Generality (what happens if you want to combine two difference C
>> programs which use two different "home grown" set implementations?).
> 
> If you want a library to support some task, you're going to find a lot
> more options in C than in OCaml.

Incompatible options, yes.

> A data structure impedance mismatch is easier to deal with than a language
> mismatch. 

You're probably going to end up copying the data structures in both cases.

>> 3. Efficiency (a "home grown" set implementation in C is unlikely to
>> match the performance of OCaml's set implementation).
> 
> Doubtful.  OCaml is very fast, but it still targets the same instruction
> set as C, and there are very fast C libraries as well.

No, my statement is true. Instruction sets are basically irrelevant. The
point is that an optimiser can do a lot better when it has more information
to act upon, i.e. in a higher-level language.

Specifically in the context of sets, the OCaml stdlib implementation will
return the union of two non-overlapping sets in O(1) time. That is
substantially faster than the O(n) of the STL set_union and all other
imperative set implementations that I have heard of.

>> 4. Capability (OCaml's built-in hash function can traverse any data
>> structure).
> 
> I don't understand what you mean by this.

The GC must be able to traverse any data structure using only information
available at run-time (OCaml strips out as much run-time type information
as possible in order to evade run-time type checking). OCaml also comes
with several functions (e.g. polymorphic comparison operators) that use
this capability to traverse any data structure in order to compare, hash
and so forth.

> For the record, here's how I'd do it in Cocoa/Objective-C, using a hash
> table:
> 
> NSMutableDictionary* dict = [NSMutableDictionary dictionary];
> NSEnumerator* enumer = [input objectEnumerator];
> NSString* string;
> while ((string = [enumer nextObject]))
> [dict setObject:[NSNumber numberWithInt:1 + [[dict objectForKey:string]
> intValue]] forKey:string];
> 
> Certainly nothing approaching "hundreds of lines!"  If anything, it's
> shorter than the OCaml approach.

That's also very nice. I can't understand it and I don't know if it is
correct (e.g. does it compute the same result as my OCaml?).

-- 
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

.