Re: [Caml-list] Map.fold behavior changed

[Brian Hurt <bhurt@spnz.org>]

On Fri, 24 Feb 2006, Damien Doligez wrote:

> On Feb 24, 2006, at 14:29, EEK Cooper wrote:
>
>> Since the behavior was NOT unspecified, it was reasonable to assume that 
>> the
>> documentation suffered from a simple typo, and to expect the behavior not 
>> to
>> change.
>
> "It is documented to do something else, so we will assume that it's intended
> to do what it does, instead of what the documentation says."
>
> I don't think this is very reasonable.

OK, My stupid question was already answered.

There are times, however, when a specified traversal ordering is required. 
Since a map is defined as an ordered tree, having a fold_left and 
fold_right functions would not be hard to do:

let rec fold_left f init = function
 	| Empty -> init
 	| Node(l, v, d, r, _) ->
 		fold_left f (f (fold_left f init l) v d) r

let rec fold_right  f node init =
 	match node with
 		| Empty -> init
 		| Node(l, v, d, r, _) ->
 			fold_right f l (f v d (fold_right f r init))

These aren't checked to see if they even compile, but they're close.

I may take this opportunity to offer a red-black tree implementation of 
Map as a replacement, if people are interested.  The advantage a 
red-black tree is that it uses one less word of memory per element in a 
map.

Brian