Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Map.fold behavior changed
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2006-02-24 (15:43)
From: Brian Hurt <bhurt@s...>
Subject: Re: [Caml-list] Map.fold behavior changed

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